Stern czy Brocot? A może jeden i drugi?

https://xpil.eu/omd 📋

Wszyscy znają ciąg Fibonacciego, prawda? Startujemy od zera i jedynki, a potem dodajemy dwa ostatnie elementy żeby dostać kolejny: 0, 1, 1, 2, 3, 5, 8, 13, 21, 33, ...

Ciąg ten ma mnóstwo interesujących właściwości, ale dziś zrobimy coś dziwnego. Mianowicie zbudujemy ciąg odrobinę kojarzący się z ciągiem Fibonacciego, ale jednak inny.

Startujemy od 1,1.

1+1=2, mamy 1, 1, 2. Zapisujemy go sobie jako [1, 1], 2 (a więc robimy dwuelementowe okienko wokół dwóch pierwszych elementów).

Teraz, uwaga, bierzemy drugą liczbę z okienka i dopisujemy ją na koniec: [1, 1], 2, 1.

Przesuwamy teraz okienko o jedną pozycję w prawo: 1, [1, 2], 1. Liczymy sumę elementów w okienku i dopisujemy ją na koniec: 1, [1, 2], 1, 3. I zaraz potem dokładamy drugą liczbę z okienka: 1, [1, 2], 1, 3, 2.

Powtarzamy tę operację w nieskończoność. Za każdym razem przesuwamy okienko oczko w prawo i dopisujemy na końcu sumę liczb w okienku i zaraz za nią drugą liczbę z okienka.

Pierwszy tysiąc elementów wygląda tak: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6, 1, 7, 6, 11, 5, 14, 9, 13, 4, 15, 11, 18, 7, 17, 10, 13, 3, 14, 11, 19, 8, 21, 13, 18, 5, 17, 12, 19, 7, 16, 9, 11, 2, 11, 9, 16, 7, 19, 12, 17, 5, 18, 13, 21, 8, 19, 11, 14, 3, 13, 10, 17, 7, 18, 11, 15, 4, 13, 9, 14, 5, 11, 6, 7, 1, 8, 7, 13, 6, 17, 11, 16, 5, 19, 14, 23, 9, 22, 13, 17, 4, 19, 15, 26, 11, 29, 18, 25, 7, 24, 17, 27, 10, 23, 13, 16, 3, 17, 14, 25, 11, 30, 19, 27, 8, 29, 21, 34, 13, 31, 18, 23, 5, 22, 17, 29, 12, 31, 19, 26, 7, 23, 16, 25, 9, 20, 11, 13, 2, 13, 11, 20, 9, 25, 16, 23, 7, 26, 19, 31, 12, 29, 17, 22, 5, 23, 18, 31, 13, 34, 21, 29, 8, 27, 19, 30, 11, 25, 14, 17, 3, 16, 13, 23, 10, 27, 17, 24, 7, 25, 18, 29, 11, 26, 15, 19, 4, 17, 13, 22, 9, 23, 14, 19, 5, 16, 11, 17, 6, 13, 7, 8, 1, 9, 8, 15, 7, 20, 13, 19, 6, 23, 17, 28, 11, 27, 16, 21, 5, 24, 19, 33, 14, 37, 23, 32, 9, 31, 22, 35, 13, 30, 17, 21, 4, 23, 19, 34, 15, 41, 26, 37, 11, 40, 29, 47, 18, 43, 25, 32, 7, 31, 24, 41, 17, 44, 27, 37, 10, 33, 23, 36, 13, 29, 16, 19, 3, 20, 17, 31, 14, 39, 25, 36, 11, 41, 30, 49, 19, 46, 27, 35, 8, 37, 29, 50, 21, 55, 34, 47, 13, 44, 31, 49, 18, 41, 23, 28, 5, 27, 22, 39, 17, 46, 29, 41, 12, 43, 31, 50, 19, 45, 26, 33, 7, 30, 23, 39, 16, 41, 25, 34, 9, 29, 20, 31, 11, 24, 13, 15, 2, 15, 13, 24, 11, 31, 20, 29, 9, 34, 25, 41, 16, 39, 23, 30, 7, 33, 26, 45, 19, 50, 31, 43, 12, 41, 29, 46, 17, 39, 22, 27, 5, 28, 23, 41, 18, 49, 31, 44, 13, 47, 34, 55, 21, 50, 29, 37, 8, 35, 27, 46, 19, 49, 30, 41, 11, 36, 25, 39, 14, 31, 17, 20, 3, 19, 16, 29, 13, 36, 23, 33, 10, 37, 27, 44, 17, 41, 24, 31, 7, 32, 25, 43, 18, 47, 29, 40, 11, 37, 26, 41, 15, 34, 19, 23, 4, 21, 17, 30, 13, 35, 22, 31, 9, 32, 23, 37, 14, 33, 19, 24, 5, 21, 16, 27, 11, 28, 17, 23, 6, 19, 13, 20, 7, 15, 8, 9, 1, 10, 9, 17, 8, 23, 15, 22, 7, 27, 20, 33, 13, 32, 19, 25, 6, 29, 23, 40, 17, 45, 28, 39, 11, 38, 27, 43, 16, 37, 21, 26, 5, 29, 24, 43, 19, 52, 33, 47, 14, 51, 37, 60, 23, 55, 32, 41, 9, 40, 31, 53, 22, 57, 35, 48, 13, 43, 30, 47, 17, 38, 21, 25, 4, 27, 23, 42, 19, 53, 34, 49, 15, 56, 41, 67, 26, 63, 37, 48, 11, 51, 40, 69, 29, 76, 47, 65, 18, 61, 43, 68, 25, 57, 32, 39, 7, 38, 31, 55, 24, 65, 41, 58, 17, 61, 44, 71, 27, 64, 37, 47, 10, 43, 33, 56, 23, 59, 36, 49, 13, 42, 29, 45, 16, 35, 19, 22, 3, 23, 20, 37, 17, 48, 31, 45, 14, 53, 39, 64, 25, 61, 36, 47, 11, 52, 41, 71, 30, 79, 49, 68, 19, 65, 46, 73, 27, 62, 35, 43, 8, 45, 37, 66, 29, 79, 50, 71, 21, 76, 55, 89, 34, 81, 47, 60, 13, 57, 44, 75, 31, 80, 49, 67, 18, 59, 41, 64, 23, 51, 28, 33, 5, 32, 27, 49, 22, 61, 39, 56, 17, 63, 46, 75, 29, 70, 41, 53, 12, 55, 43, 74, 31, 81, 50, 69, 19, 64, 45, 71, 26, 59, 33, 40, 7, 37, 30, 53, 23, 62, 39, 55, 16, 57, 41, 66, 25, 59, 34, 43, 9, 38, 29, 49, 20, 51, 31, 42, 11, 35, 24, 37, 13, 28, 15, 17, 2, 17, 15, 28, 13, 37, 24, 35, 11, 42, 31, 51, 20, 49, 29, 38, 9, 43, 34, 59, 25, 66, 41, 57, 16, 55, 39, 62, 23, 53, 30, 37, 7, 40, 33, 59, 26, 71, 45, 64, 19, 69, 50, 81, 31, 74, 43, 55, 12, 53, 41, 70, 29, 75, 46, 63, 17, 56, 39, 61, 22, 49, 27, 32, 5, 33, 28, 51, 23, 64, 41, 59, 18, 67, 49, 80, 31, 75, 44, 57, 13, 60, 47, 81, 34, 89, 55, 76, 21, 71, 50, 79, 29, 66, 37, 45, 8, 43, 35, 62, 27, 73, 46, 65, 19, 68, 49, 79, 30, 71, 41, 52, 11, 47, 36, 61, 25, 64, 39, 53, 14, 45, 31, 48, 17, 37, 20, 23, 3, 22, 19, 35, 16, 45, 29, 42, 13, 49, 36, 59, 23, 56, 33, 43, 10, 47, 37, 64, 27, 71, 44, 61, 17, 58, 41, 65, 24, 55, 31, 38, 7, 39, 32, 57, 25, 68, 43, 61, 18, 65, 47, 76, 29, 69, 40, 51, 11, 48, 37, 63, 26, 67, 41, 56, 15, 49, 34, 53, 19, 42, 23, 27, 4, 25, 21, 38, 17, 47, 30, 43, 13, 48, 35, 57, 22, 53, 31, 40, 9, 41, 32, 55, 23, 60, 37, 51, 14, 47, 33, 52, 19, 43, 24, 29, 5, 26, 21, 37, 16, 43, 27, 38, 11, ...

Jak widać powyższa sekwencja ma ogólną tendencję wzrostową - i nic dziwnego, w końcu nie wykonujemy tu żadnych działań zmniejszających typu odejmowanie, pierwiastkowanie czy dzielenie - ale poza tym wygląda raczej dość chaotycznie. Czemuż więc o niej piszę?

Zróbmy teraz coś dziwnego: zacznijmy między kolejne elementy powyższego ciągu wstawiać... kreskę ułamkową: \(\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}, \frac{1}{4}, \frac{4}{3}, \frac{3}{5}, \frac{5}{2} ...\)

I teraz danie główne dzisiejszego wpisu: powyższy (nieskończony) ciąg ułamków zawiera, uwaga, każdą dodatnią liczbę wymierną zapisaną w postaci ułamka nieskracalnego, bez powtórzeń.

Innymi słowy ciąg ów zawiera wszystkie istniejące dodatnie ułamki nieskracalne!

Jeszcze innymi słowy: jeżeli dwie dowolne liczby naturalne a i b są względnie pierwsze, to jest gwarantowane, że ułamek \(\frac{a}{b}\) pojawi się w tej sekwencji dokładnie raz.

Magia.

Zjawisko powyższe znane jest od dawna pod nazwą sekwencji / drzewa Sterna-Brocota, można sobie o nim poczytać tutaj.

A jeżeli ktoś chce się dowiedzieć jak wyliczyć kolejne elementy tego ciągu za pomocą komputera, tu są przykłady [klik]

https://xpil.eu/omd 📋