Sekwencja Mosera – de Bruijna

Tabela dodawania dla gdzie oba

należą

do sekwencji Mosera – de Bruijna

która

łączy

krzywa sumy kolejność numeryczna

W teorii liczb sekwencja Mosera – de Bruijna jest ciągiem liczb całkowitych nazwanym na cześć Leo Mosera i Nicolaasa Goverta de Bruijna , składającym się z sum odrębnych potęg 4 lub równoważnie liczb, których reprezentacje binarne są niezerowe tylko w pozycjach parzystych.

Liczby te rosną proporcjonalnie do kwadratu liczb i są kwadratami dla zmodyfikowanej formy arytmetyki bez przenoszenia . Kiedy wartości w sekwencji są podwojone, wszystkie ich różnice są niekwadratowe. Każda nieujemna liczba całkowita ma unikalną reprezentację jako sumę elementu sekwencji i podwojonego elementu sekwencji. Ten rozkład na sumy można wykorzystać do zdefiniowania bijekcji między liczbami całkowitymi i parami liczb całkowitych, do zdefiniowania współrzędnych krzywej rzędu Z i do skonstruowania odwrotnych par liczb przestępnych z prostymi reprezentacjami dziesiętnymi.

Prosta relacja powtarzalności pozwala na obliczenie wartości sekwencji Moser – de Bruijn na podstawie wcześniejszych wartości i może być wykorzystana do udowodnienia, że sekwencja Moser – de Bruijn jest sekwencją 2-regularną .

Definicja i przykłady

Liczby w sekwencji Moser – de Bruijn są tworzone przez dodanie różnych potęg czterech. Sekwencja zawiera te liczby w posortowanej kolejności; zaczyna

0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, 256, ...

Na przykład 69 należy do tego ciągu, ponieważ równa się 64 + 4 + 1, czyli sumie trzech różnych potęg liczby 4.

Reprezentacje binarne i pokrewne

⁰ Inną definicją sekwencji Mosera – de Bruijna jest to, że jest to uporządkowana sekwencja liczb, której reprezentacja binarna ma niezerowe cyfry tylko na pozycjach parzystych. Na przykład 69 należy do ciągu, ponieważ jego reprezentacja binarna 1000101 ₂ ma cyfry niezerowe na pozycjach dla 2 ⁶ , 2 ² i 2 , z których wszystkie mają parzyste wykładniki. Liczby w sekwencji można również opisać jako liczby, których reprezentacja na podstawie 4 używa tylko cyfr 0 lub 1. W przypadku liczby w tej sekwencji reprezentację o podstawie 4 można znaleźć na podstawie reprezentacji binarnej, pomijając cyfry binarne na nieparzystych pozycjach, z których wszystkie powinny wynosić zero. Szesnastkowa reprezentacja tych liczb zawiera tylko cyfry 0, 1, 4, 5. Na przykład 69 = 1011 ₄ = 45 ₁₆ . Równoważnie są to liczby, których reprezentacje binarne i negabinarne są równe. Ponieważ w ich reprezentacjach binarnych nie ma dwóch kolejnych liczb niezerowych, sekwencja Mosera – de Bruijna tworzy podsekwencję liczb fibbinarnych .

Wykres liczby elementów sekwencji do podzielonej przez

\

displaystyle {\ sqrt {n}}}

w logarytmicznej skali poziomej n {\ displaystyle n

Z binarnych lub o podstawie 4 definicji tych liczb wynika, że rosną one w przybliżeniu proporcjonalnie do liczb kwadratowych . Liczba elementów w sekwencji Mosera – de Bruijna, które znajdują się poniżej danego progu, $jest$ $do$ , dotyczy również liczb kwadratowych. W rzeczywistości liczby w sekwencji Moser-de Bruijn są kwadratami dla wersji arytmetyki bez przenoszenia liczb binarnych, w której dodawanie i mnożenie pojedynczych bitów są odpowiednio wyłączne lub logiczne operacje koniunkcji .

W związku z twierdzeniem Furstenberga – Sárközy'ego o ciągach liczb bez różnicy kwadratów Imre Z. Ruzsa znalazł konstrukcję dla dużych zbiorów wolnych od różnic kwadratowych, która podobnie jak binarna definicja ciągu Mosera – de Bruijna ogranicza cyfry w naprzemienne pozycje w liczbach podstawowych. ${\ displaystyle b}$ Po zastosowaniu do podstawy konstrukcja Ruzsy generuje sekwencję Mosera – de Bruijna pomnożoną przez dwa, czyli zbiór, który ponownie jest wolny $kwadratów$ Jednak ten zestaw jest zbyt rzadki, aby zapewnić nietrywialne dolne granice twierdzenia Furstenberga – Sárközy'ego.

Unikalna reprezentacja jako sumy

$\ displaystyle x$ $}$ do sekwencji Sidon : sumy , gdzie oba należą do Mosera $+ 2y$ –de Bruijn, wszystkie są unikalne. Żadne dwie z tych sum nie mają takiej samej wartości. Co więcej, każdą liczbę $można$ przedstawić jako sumę, gdzie $}$ $displaystyle$ $x}$ i należą do sekwencji Moser – de Bruijn. Aby znaleźć sumę, która reprezentuje , oblicz bitową $displaystyle n}$ i $displaystyle$ ${$ \ z wartość binarna (wyrażona tutaj w systemie szesnastkowym ), która ma jedynki na wszystkich swoich parzystych pozycjach, i ustawia ${\ Displaystyle y = (nx) / 2}$ .

$Sekwencja Mosera – de Bruijna$ mają unikalne wyrażenie jako . Z tego powodu sekwencja była pierwotnie badana przez Mosera (1962) . Rozszerzając tę właściwość, De Bruijn (1964) znalazł nieskończenie wiele innych wyrażeń liniowych, takich jak $x + 2y}$ $\ displaystyle y}$ , które kiedy i ${$ oba należą do sekwencji Mosera – de Bruijna, jednoznacznie reprezentują wszystkie liczby całkowite.

Krzywa rzędu Z i formuła następnika

Rozkładając liczbę na $=$ $displaystyle n = x + 2y}$ $y}$ , a następnie stosując do y $displaystyle$ mapę zachowującą porządek Sekwencja Mosera – de Bruijna do liczb całkowitych (poprzez zastąpienie potęg czterech w każdej liczbie odpowiednimi potęgami dwóch) daje bijekcję od nieujemnych liczb całkowitych do uporządkowanych par nieujemnych liczb całkowitych. Odwrotność tej bijekcji daje uporządkowanie liniowe w punktach na płaszczyźnie o nieujemnych współrzędnych całkowitych, które można wykorzystać do zdefiniowania Krzywa rzędu Z.

W związku z tym zastosowaniem wygodnie jest mieć formułę do generowania każdego kolejnego elementu ciągu Moser-de Bruijn z jego poprzednika. Można to zrobić w następujący sposób. Jeśli jest elementem sekwencji, to następny element po $można$ uzyskać, wypełniając bity na nieparzystych pozycjach binarnej reprezentacji przez jedynki, $displaystyle$ $x}$ dodanie jednego do wyniku, a następnie maskowanie wypełnionych bitów. Wypełnianie bitów i dodawanie jednego można połączyć w jedną operację dodawania. Oznacza to, że następnym członkiem jest liczba podana przez formułę

{\ Displaystyle \ Displaystyle (x + {\ textrm {0xaaaaaaab}}) \ \ & \ {\ textrm {0x55555555}}.}

-1/3}

można zinterpretować odpowiednio jako liczby

displaystyle

-adyczne i .

Gra w odejmowanie

Golomb (1966) zbadał grę w odejmowanie , analogiczną do odejmowania kwadratu , opartą na tej sekwencji. $W$ grze Golomba dwóch graczy na zmianę usuwa monety ze stosu . W każdym ruchu gracz może usunąć dowolną liczbę monet należących do sekwencji Moser-de Bruijn. Wyciąganie jakiejkolwiek innej liczby monet jest niedozwolone. Zwycięzcą zostaje gracz, który usunie ostatnią monetę. Jak zauważa Golomb, „zimne” pozycje tej gry (te, w których przegrywa gracz, który ma wykonać ruch) są dokładnie pozycjami postaci gdzie $.$ do sekwencji Moser – $de$ Zwycięską strategią w tej grze jest rozłożenie aktualnej liczby monet na , gdzie $\$ $displaystyle x + 2y}$ i x $\ displaystyle x}$ i $displaystyle y}$ należą do sekwencji Moser – de Bruijn, a następnie (jeśli jest różna od zera), aby usunąć $displaystyle$ $x}$ monety, pozostawiając zimną pozycję drugiemu graczowi. Jeśli $zero$ , ta strategia nie jest możliwa i nie ma zwycięskiego ruchu.

Odwrotności dziesiętne

$x}$ stanowi podstawę przykładu liczby $niewymiernej$ z , że dziesiętne reprezentacje i mogą być jednocześnie $displaystyle$ być napisane prosto i wyraźnie. Niech $samą$ sekwencję Mosera – de Bruijna. potem dla

{\ Displaystyle x = 3 \ suma _ {n \ w E} 10 ^ {- n} = 3,300330000000000330033 \ kropki,}

liczba dziesiętna, której cyfry niezerowe znajdują się na pozycjach podanych przez sekwencję Mosera – de Bruijna, wynika z tego, że cyfry niezerowe jej odwrotności znajdują się na pozycjach 1, 3, 9, 11, ..., podanych przez podwojenie liczb w

{\ displaystyle E}

i dodanie jednego do nich wszystkich:

{\ Displaystyle {\ Frac {1} {x}} = 3 \ suma _ {n \ w E} 10 ^ {-2n-1} = 0,30300000303 \ kropki \.}

Alternatywnie można napisać:

{\ Displaystyle \ Displaystyle \ lewo (\ suma _ {n \ w E} 10 ^ {- n} \ prawej) \ lewo (\ suma _ {n \ w E} 10 ^ {-2n} \ prawej) = {\ ułamek {10}{9}}.}

Podobne przykłady działają również w innych bazach. Na przykład dwie liczby binarne , których niezerowe bity znajdują się na tych samych pozycjach, co niezerowe cyfry dwóch liczb dziesiętnych powyżej, są również niewymiernymi odwrotnościami. Te liczby binarne i dziesiętne oraz liczby zdefiniowane w ten sam sposób dla dowolnej innej podstawy przez powtórzenie pojedynczej cyfry niezerowej na pozycjach podanych przez sekwencję Mosera – de Bruijna są liczbami przestępnymi . Ich transcendencję można udowodnić na podstawie faktu, że długie ciągi zer w ich cyfrach pozwalają na dokładniejsze przybliżenie ich liczbami wymiernymi niż dopuszczałoby twierdzenie Rotha , gdyby były to liczby algebraiczne o mierze niewymierności nie mniejszej niż 3.

Funkcja generująca

{\ Displaystyle F (x) = \ prod _ {i = 0 }^{\infty }(1+x^{4^{i}})=1+x+x^{4}+x^{5}+x^{16}+x^{17}+\cdots ,}

którego wykładniki w postaci rozwiniętej są podane przez sekwencję Mosera – de Bruijna, jest zgodny z równaniami funkcyjnymi

{\ Displaystyle F (x) F (x ^ {2}) = {\ Frac {1} {1-x}}}

I

{\ Displaystyle F (x) = (1 + x) F (x ^ {4}).}

Na przykład tej funkcji można użyć do opisania dwóch odwrotności dziesiętnych podanych powyżej: jedna to

{\ Displaystyle 3F (1/10)}

} styl wyświetlania {\tfrac {3}{10}}F(1/100)}

a druga to . Fakt, że są one odwrotnościami, jest przykładem pierwszego z dwóch równań funkcjonalnych. Iloczyny cząstkowe formy iloczynu funkcji generującej można wykorzystać do wygenerowania zbieżności funkcji ciągłe rozszerzanie ułamkowe samych tych liczb, a także ich wielokrotności.

Powtarzalność i regularność

Sekwencja Mosera – de Bruijna jest zgodna z $S (0) = 0$ , która pozwala na $n-$ $Displaystyle$ wartość sekwencji (zaczynając od ) do ustalenia na podstawie wartości na pozycji ${\ Displaystyle \ lfloor n/2 \ rfloor}$ :