Sekwencja Gijswijta

W matematyce sekwencja Gijswijta (nazwana na cześć Dion Gijswijt przez Neila Sloane'a ) jest samoopisującą się sekwencją , w której każdy termin liczy maksymalną liczbę powtarzających się bloków liczb w sekwencji bezpośrednio poprzedzającej ten termin.

Sekwencja zaczyna się od:

1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 1, ... (sekwencja A090822 w OEIS )

Sekwencja jest podobna w definicji do sekwencji Kolakoskiego , ale zamiast liczyć najdłuższy ciąg pojedynczych wyrazów, sekwencja liczy najdłuższy ciąg bloków wyrazów o dowolnej długości. Sekwencja Gijswijta znana jest z niezwykle powolnego tempa wzrostu. $na 220. członie$ a pierwsze 5 pojawia się w pobliżu .

Definicja

Proces generowania terminów w sekwencji można zdefiniować, patrząc na sekwencję jako serię liter w alfabecie liczb naturalnych :

${\ Displaystyle a (1) = 1}$ i
${\ Displaystyle a (n + 1) = k}$ $,$ gdzie jest największą liczbą naturalną taką, że ${\ Displaystyle a (1) a (2) a (3) ... a (n)}$ można zapisać w postaci ${\ Displaystyle xy ^ {k}}$ dla niektórych słów ${ \ displaystyle x}$ i ${\ displaystyle y}$ , przy czym ${\ displaystyle y}$ ma niezerową długość.

Sekwencja jest niezależna od zasady. Oznacza to, że jeśli zostanie znaleziony ciąg 10 powtarzających się bloków, następnym wyrazem w sekwencji będzie pojedyncza liczba 10, a nie 1, po którym następuje 0.

Wyjaśnienie

Sekwencja zaczyna się od 1 z definicji. 1 w drugim członie reprezentuje wtedy długość 1 bloku jedynek, który znajduje się bezpośrednio przed nim w pierwszym członie. 2 w trzecim członie reprezentuje długość 2 bloku jedynek, które są w pierwszym i drugim członie. W tym momencie sekwencja maleje po raz pierwszy: 1 w czwartym członie reprezentuje długość 1 bloku 2s w 3. członie, jak również długość 1 bloku „1, 2” obejmującego drugi i trzeci semestr. Nie ma bloku dowolnej powtarzającej się sekwencji bezpośrednio poprzedzającej czwarty wyraz, który byłby dłuższy niż 1. Blok dwóch jedynek w pierwszym i drugim wyrazie nie może być brany pod uwagę w czwartym wyrazie, ponieważ są one oddzielone inną liczbą w trzecim wyrazie .

1 w piątym członie reprezentuje długość 1 „powtarzających się” bloków „1” i „2, 1” oraz „1, 2, 1” i „1, 1, 2, 1”, które bezpośrednio poprzedzają piąty człon. Żaden z tych bloków nie powtarza się więcej niż raz, więc piąty wyraz to 1. 2 w szóstym wyrazie reprezentuje długość powtarzanego bloku jedynek bezpośrednio prowadzącego do szóstego wyrazu, a mianowicie tych w czwartym i piątym wyrazie. 2 w siódmym członie reprezentuje 2 powtórzenia bloku „1, 1, 2” obejmujące wyrazy 1-3, a następnie 4-6. To „słowo z trzema cyframi” pojawia się dwa razy bezpośrednio przed siódmym wyrazem - więc wartość siódmego wyrazu wynosi 2.

2 w ósmym członie reprezentuje długość powtarzanego bloku 2 bezpośrednio prowadzącego do ósmego członu, a mianowicie dwójek w szóstym i siódmym członie. 3 w dziewiątym członie reprezentuje trzykrotnie powtórzony blok pojedynczych dwójek bezpośrednio prowadzący do 9 członu, a mianowicie dwójki w szóstym, siódmym i ósmym członie.

Nieruchomości

Tylko ograniczone badania skupiły się na sekwencji Gijswijta. W związku z tym bardzo niewiele zostało udowodnionych na temat sekwencji, a wiele otwartych pytań pozostaje nierozwiązanych.

Poziom wzrostu

Biorąc pod uwagę, że 5 pojawia się dopiero około $, techniki wyszukiwania siłowego$ 4. Udowodniono jednak, że ciąg zawiera każdą liczbę naturalną. Dokładne tempo wzrostu nie jest znane, ale przypuszcza się, że rośnie superlogarytmicznie , przy pierwszym wystąpieniu dowolnego naturalnego $w$ pobliżu ${\ Displaystyle 2 ^ {2 ^ {3 ^ {4 ^ {5 ^ {. ^ {. ^ {. {n-1}}}}}}}}}$ .

Średnia wartość

Chociaż wiadomo, że każda liczba naturalna występuje w skończonej pozycji w sekwencji, przypuszczano, że sekwencja może mieć skończoną średnią . Aby zdefiniować to formalnie w nieskończonej sekwencji, w której zmiana kolejności terminów może mieć znaczenie, przypuszcza się, że:

{\ Displaystyle \ lim _ {n \ do \ infty} {\ Frac {1} {n}} \ suma _ {i = 1} ^ { n}a(i)<\infty }

Podobnie gęstość dowolnej liczby naturalnej w sekwencji nie jest znana.

Struktura rekurencyjna

Sekwencję można podzielić na oddzielne sekwencje „blokowe” i „klejowe”, których można użyć do rekurencyjnego tworzenia sekwencji. $Na$ $odpowiednio$ możemy zdefiniować pierwszy blok Razem możemy zobaczyć, jak tworzą początek sekwencji:

{\ Displaystyle B_ {1} B_ {1} S_ {1} = 1,1,2}

Następnym krokiem jest rekurencyjne budowanie sekwencji. Zdefiniuj ${\ Displaystyle B_ {2} = B_ {1} B_ {1} S_ {1}}$ . Zauważając ${2} = 2,2,3 }$ że sekwencja zaczyna się od $zdefiniować$ ciąg kleju co daje:

{\ Displaystyle B_ {2} B_ {2} S_ {2} = 1,1,2,1,1, 2,2,2,3}

Przypisaliśmy do określonej sekwencji, która daje właściwość, że $B_ { 2}B_{2}S_{2}}$ ${ \ Displaystyle B_ {2} B_$ występuje również na początku sekwencji.

Ten proces można kontynuować w nieskończoność z ${\ Displaystyle B_ {n + 1} = B_ {n} B_ {n} S_ {n}}$ . Okazuje się, $1$ możemy odkryć ciąg kleju $,$ zauważając, że i że zatrzyma się, gdy osiągnie pierwsze 1 podążaj za ${\ Displaystyle B_ {n} B_ {n}}$ . Udowodniono również, że sekwencję Gijswijta można budować w ten sposób w nieskończoność - to znaczy, że $}$ { $}$ mają zawsze skończoną długość dla dowolnego $n$ .

Sprytna manipulacja sekwencjami kleju w tej rekurencyjnej strukturze może zostać wykorzystana do wykazania, że sekwencja Gijswijta zawiera wszystkie liczby naturalne, oprócz innych właściwości sekwencji.

Zobacz też

Linki zewnętrzne

Pierwsze 50 milionów warunków
OEIS A091579 (długości bloków przyrostków powiązanych z A090822) — (długości sekwencji kleju)

OEIS A090822 (sekwencja Gijswijta)