Zagadka matematyczna z hakiem – rozwiązanie

https://xpil.eu/1ba

Zagadka jest rekurencyjna.

Jak powszechnie wiadomo^{[citation needed]}, w rozwinięciu dziesiętnym liczby Pi można znaleźć wszystkie możliwe kombinacje cyfr. A zatem... można tam też znaleźć samą liczbę Pi, z dowolnie zadaną dokładnością!

Ciąg 10, 138, 2121, 3497, 88009, 176452 to nic innego jak pozycje w rozwinięciu dziesiętnym liczby Pi, na których można znaleźć kolejno coraz dłuższe rozwinięcia Pi (z pominięciem przecinka rzecz jasna). Tak więc trójkę znajdziemy na pozycji numer 10, 31 na pozycji 138, 314 na pozycji 2121, 3141 na pozycji 3497, 31415 na pozycji 88009, wreszcie 314159 na pozycji 176452.

Kolejnym poszukiwanym ciągiem jest oczywiście 3141592, który znajdziemy na pozycji numer 25198141 - i to jest poprawne rozwiązanie zagadki.

Jak tę liczbę znaleźć?

Ja posłużyłem się prościutkim kodem w Pythonie:

with open("pi.txt") as pif:
    pi=pif.readline().replace('.','')
print(pi.find('3', 1))
print(pi.find('31', 1))
print(pi.find('314', 1))
print(pi.find('3141', 1))
print(pi.find('31415', 1))
print(pi.find('314159', 1))
print(pi.find('3141592', 1))
print(pi.find('31415926', 1))
print(pi.find('314159265', 1))

Plik pi.txt ściągnąłem sobie stąd: https://stuff.mit.edu/afs/sipb/contrib/pi/ - zawiera on pierwszy miliard cyfr liczby Pi, dzięki czemu możemy sobie tam wyszukać również 31415926 (na pozycji 50366473), ale już nie 314159265.

Uwaga: powyższy kod zwróci ciąg wyników przesunięty o jeden w dół, bo numerowanie w komputerach zaczyna się na ogół od zera, nie od jedynki. Jednak w zagadce użyłem numerowania od jedynki, z dwóch powodów:

1. Ludzie naturalnie numerują od jedynki, nie od zera (na przykład ta lista dwóch podpunktów ma podpunkt numer 1 oraz podpunkt numer 2, prawda?)
2. Jeżeli użyłbym numerowania od 0, wtedy każdy mógłby sobie ten ciąg w trzy sekundy wyguglać w OEIS (opublikowany po raz pierwszy około 18 lat temu). Skąd o tym wiem? Bo w pierwotnej wersji zagadki miałem ponumerowane od zera i sobie sprawdziłem 🙂

Nota bene pomysł na zagadkę ukradłem z niedawnego wpisu na blogu Johna, w którym pokazuje on jak wyszukiwać Pi w Pi za pomocą Perla i wyrażeń regularnych. Tylko dla odważnych 🙂

---

A jak Wam poszło?

Prawdę mówiąc, aż za dobrze! Moi Czytelnicy mnie zawstydzili. Bo wydawało mi się, że trafiłem na oryginalny temat, na coś ciężkiego do wyszukania, na perełkę. Tymczasem przecież zarówno OEIS jak też inne (niż Google) wyszukiwarki całkiem bezproblemowo radzą sobie ze znalezieniem tego ciągu. Stąd też zaledwie w kilka godzin po opublikowaniu wpisu miałem już w powiadomieniach poprawne odpowiedzi od (w kolejności nadsyłania): Roziego, Rzasta, Buttera i Waldka, a nazajutrz również od Tywana i Krzyśka. Większość z nich wskazujące na https://oeis.org/A065593.

Rzast i Krzysiek jako jedyni nie przyznali się do używania wyszukiwarek. Rzast objaśnił rozwiązanie własnymi słowami (podając kolejne wartości ciągu aż do dziewiątego elementu!), a Krzysiek po prostu napisał, że to pozycja "3141592" w rozwinięciu dziesiętnym pi.

Ponadto Waldek - jako osobnik lubiący rozwiązania "pod prąd" - nadesłał też rozwiązanie alternatywne, w którym odpowiedzią jest liczba -562037. Jeżeli bowiem weźmiemy pewien skomplikowany wielomian i będziemy doń podstawiać kolejne liczby naturalne, dostaniemy w wyniku kolejne elementy naszego ciągu. Odpowiedź uznaję połowicznie: na plus, bo rozwiązanie jest "prostopadłe" do toku myślenia reszty tłumu, na minus, bo w treści zadania pisze wyraźnie, że ciąg ma być rosnący.

Tenże sam Waldek nadesłał też trzecie rozwiązanie: również oparte na wielomianie (jeszcze bardziej skomplikowanym od poprzedniego), który daje identyczne wyniki dla liczb 1-6 oraz... 25198141 dla siódemki 🙂 I tę odpowiedź zaliczam w całości, choć poniewczasie.

W konkursie udział wzięły też Ultra oraz Panna M, ale im mogę przyznać punkty wyłącznie za udział, ponieważ nie podjęły się rozwiązania zagadki i wysłały jedna 0, a druga 23424234. Jestem jednak przekonany, że Waldek i dla tych dwóch liczb potrafi znaleźć odpowiednie wielomiany :).

https://xpil.eu/1ba