ciąg Goulda

Trójkąt Pascala, wiersze od 0 do 7. Liczba nieparzystych liczb całkowitych w wierszu i jest i -tą liczbą w ciągu Goulda.

Samopodobny kształt piłokształtny sekwencji Goulda

Sekwencja Goulda to sekwencja liczb całkowitych nazwana na cześć Henry'ego W. Goulda , która liczy, ile liczb nieparzystych znajduje się w każdym rzędzie trójkąta Pascala . Składa się tylko z potęg dwójki i zaczyna się:

1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, ... (sekwencja A001316 w OEIS )

Na przykład szósta liczba w sekwencji to 4, ponieważ w szóstym rzędzie trójkąta Pascala znajdują się cztery liczby nieparzyste (cztery pogrubione liczby w sekwencji 1 , 5 , 10, 10, 5 , 1 ).

Dodatkowe interpretacje

n $-$ ta wartość w sekwencji (począwszy od $n = 0$ ) daje najwyższą potęgę 2, która dzieli środkowy współczynnik dwumianu ${2n} {n}}}$ tbinom licznik ${\ Displaystyle 2 ^ {n} / n!}$ (wyrażony jako ułamek w najniższych wartościach).

Trójkąt Sierpińskiego generowany przez Regułę 90 , lub przez zaznaczenie pozycji liczb nieparzystych w trójkącie Pascala . Sekwencja Goulda zlicza liczbę żywych komórek w każdym rzędzie tego wzoru.

Sekwencja Goulda podaje również liczbę żywych komórek w $n-$ tej generacji automatu komórkowego Reguły 90 , zaczynając od pojedynczej żywej komórki. Ma charakterystyczny rosnący piłokształtny , który może być użyty do rozpoznania procesów fizycznych, które zachowują się podobnie do Reguły 90.

Powiązane sekwencje

Logarytmy binarne (wykładniki potęg dwóch) ciągu Goulda same tworzą ciąg liczb całkowitych,

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, ... (sekwencja A000120 w OEIS )

w którym $jako$ $-$ liczbę niezerowych bitów w binarnej reprezentacji liczby $n$ , czasami zapisywanej w notacji matematycznej Równoważnie, $n-$ tą wartością ciągu Goulda jest

{\ Displaystyle 2 ^ {\ #_ {1} (n)}.}

Biorąc sekwencję wykładników modulo dwa, otrzymujemy sekwencję Thue-Morse'a .

Sumy cząstkowe ciągu Goulda,

0, 1, 3, 5, 9, 11, 15, 19, 27, 29, 33, 37, 45, ... (sekwencja A006046 w OEIS )

policz wszystkie liczby nieparzyste w pierwszych $n$ rzędach trójkąta Pascala. $...$ rosną proporcjonalnie do ze stałą proporcjonalności 1, okresowo jako funkcja $log n$ .

Konstrukcja rekurencyjna i samopodobieństwo

Pierwsze $2 wartości i$ w sekwencji Goulda można skonstruować rekurencyjnie konstruując pierwsze $2 i - 1$ wartości, a następnie łącząc podwójne wartości pierwszych $2 i - 1 .$ Na przykład połączenie pierwszych czterech wartości 1, 2, 2, 4 z ich liczbami podwójnymi 2, 4, 4, 8 daje pierwsze osiem wartości. Z powodu tej konstrukcji podwajającej pierwsze wystąpienie każdej potęgi dwóch $2 i$ w tej sekwencji jest na pozycji $2 i - 1$ .

Sekwencja Goulda, sekwencja jej wykładników i sekwencja Thue-Morse'a są wszystkie samopodobne : mają tę właściwość, że podciąg wartości na parzystych pozycjach w całym ciągu jest równy oryginalnej sekwencji, właściwość, którą dzielą również z innymi sekwencje takie jak sekwencja dwuatomowa Sterna . W sekwencji Goulda wartości na pozycjach nieparzystych są dwukrotnie większe niż ich poprzednicy, podczas gdy w sekwencji wykładników wartości na pozycjach nieparzystych to jeden plus ich poprzednicy.

Historia

Sekwencja została nazwana na cześć Henry'ego W. Goulda , który badał ją na początku lat 60. Jednak fakt, że $te$ liczby są potęgami dwójki, gdzie wykładnik $n$ -tej liczby jest równy liczbie jedynek w binarnej reprezentacji n , był już znany JWL Glaisherowi w 1899 roku.

Udowodnienie, że liczby w ciągu Goulda są potęgami dwójki, zostało podane jako problem w konkursie matematycznym Williama Lowella Putnama w 1956 roku .