Zagadka matematyczna z hakiem – rozwiązanie

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 :).

4 komentarze

  1. @xpil

    Zadałeś mi ćwieka:

    “w treści zadania pisze wyraźnie, że ciąg ma być rosnący”.

    Tymczasem to nie jest takie proste…

    Weźmy czysto teoretycznie, że pi=3,14314315… Teraz:
    s(1)=4
    s(2)=4
    s(3)=4
    I z rosnącego ciągu nici… A kuku.

    Jak napisałeś, w pi można zmieścić wszystko (nawet samą pi – to akurat nie jest prawdą, co łatwo udowodnić), więc dla już prawdziwego pi na pewno wystąpi sekwencja n+1 cyfr: C1…Cn, C{n+1}, która będzie na tej samej pozycji, co sekwencja ją poprzedzająca: C1..Cn (jak w powyższym przykładzie).

    Teraz weźmy rzeczywisty ciąg A112788. To jest to samo, tylko dla e (podstawa logarytmu naturalnego). Na marginesie – w tytule ciągu w OEIS jest szewski błąd – zamiast e napisano pi. Nie zmienia to jednak istoty rzeczy:
    5, 63, 919, 5504, 29170, 252475, 7910576, 7910576, …
    Spójrz na pozycje 7 i 8 – są identyczne. W e ten casus występuje na tyle szybko, że łatwo to wychwycić.

    Pytanie: dla jakiego n dzieje się to po raz pierwszy w pi?

    Poza konkursem: chciałem napisać albo do OEIS, albo do autora ciągu A112788 o tym błędzie, ale na stronie nie widzę takiej opcji. Może ktoś wie, jak ich powiadomić o potrzebie poprawki?

    1. No dobrze. Zamiast “rosnący” powinienem był napisać “niemalejący”. Co do znajdowania pi w pi, to napisałem, że “z dowolnie zadaną dokładnością”. Wiadomo, że *całej* Pi w Pi się drugi raz nie znajdzie, ale dla dowolnej (skończonej) dokładności – tak. Nie wiem jak “sprytnie” znaleźć pierwsze takie wystąpienie dla Pi, gdzie s(n) = s(n+1). Może któryś z Czytelników (obecnych lub przyszłych) ma jakiś pomysł?

      Co do korekt w OEIS: kiedyś był tam podany ogólny adres e-mail, ale jakiś czas temu go zdjęli. Teraz trzeba kontaktować się bezpośrednio z autorem sekwencji (link do autora jest po sekwencją, w tym przypadku: https://oeis.org/wiki/User:Zak_Seidov). Facet nie ma podanego e-maila, więc trzeba próbować przez FB lub TT (nie używam FB ani TT, więc dalej nie pomogę).

Leave a Comment

Komentarze mile widziane.

Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]