Koniec końców
Kończąc długą beskidzką wycieczkę, schodziłem wąską drogą, wijącą się zalesionym i gęsto zakrzaczonym zboczem koło szczawnickiego przysiółka Gabańka, gdy nagle usłyszałem odgłos łamania gałęzi w zaroślach. Przystanąłem więc i zacząłem wypatrywać jakiegoś zwierzęcia. Tymczasem okazało się, że to człowiek – pan w podeszłym wieku, który po chwili wyszedł na drogę i zaczął mnie wypytywać com za jeden i co tu robię. Potem powiedział trochę o sobie (mieszka opodal, obchodzi swoje włości, ma 80 lat) i po krótkiej wymianie uwag na temat pogody i pięknych okoliczności przyrody dowiedziałem się, że nadchodzi… koniec świata. Miało o tym świadczyć m. in. to, że zwierzęta coraz śmielej zaglądają do ludzkich siedzib – np. wilki, które przy okazji zagryzły owce jednemu z sąsiadów oraz niedźwiedź, który innemu sąsiadowi zdewastował pasiekę. Koronnym argumentem było jednak widzenie, którego mój rozmówca doświadcza regularnie od kilkunastu lat i z którego wynika, że koniec świata nastąpi najpóźniej w roku 2020.
Usiłując zachować powagę rzuciłem nieśmiało, że przepowiedni końców świata było już wiele, ale jakoś żadna się nie sprawdziła. Rozmowa się jednak nie kleiła, bo dziadek niedosłyszał, a konieczność powtarzania i mówienia podniesionym głosem jest stresująca. Dochodząc do pierwszych szczawnickich domostw, zebraliśmy trochę śliwek w zdziczałym sadzie, a zaraz potem rozstaliśmy się z niejaką ulgą. Wracając do domu starałem się przypomnieć sobie, co wiem o współczesnych przepowiedniach apokalipsy.
Najgłośniejszą w ostatnich latach, czyli związany z kalendarzem Majów tzw. fenomen roku 2012, pamiętają chyba wszyscy. Media poświęcały wówczas rzekomej prognozie sprzed wieków wyjątkowo dużo miejsca. Temat jest zresztą bardzo obszernie opisany w polskiej Wikipedii. Za oceanem niemal równie głośno bywało o wizjach nawiedzonych etatowych wróżbitów, astrologów i parapsychologów – Davida Meade, Jeane Dixon, a zwłaszcza Harolda Campinga, który na przepowiedniach dorobił się fortuny. Podobnie jak wielu innych Camping formułował swoje przewidywania w oparciu o skomplikowane obliczenia, korzystając z informacji zawartych w Biblii, czym zasłużył sobie w roku 2011 na… Antynobla z matematyki. Co ciekawe, przed wiekami od takich bałamutnych obliczeń nie stronili nawet poważni matematycy. John Napier, „ojciec” logarytmów, wyznaczył koniec świata na rok 1700, a Jacob Bernoulli, zajmujący się m. in. rachunkami prawdopodobieństwa i różniczkowym, wieszczył, że katastroficzne spotkanie Ziemi z kometą nastąpi 5 kwietnia 1719 r. Natomiast data apokalipsy wyznaczona na podstawie Biblii przez Isaaca Newtona wciąż jest przed nami – to rok 2060.
Przed nami jest także inny rok końca świata, obliczony współcześnie przez angielskiego matematyka Simona Twiga, który twierdzi, że rok ostatni będzie rokiem… pierwszym, czyli będzie wyrażał się liczbą pierwszą. Twig, także biblista amator, zaczął rachunki od pewnej biblijnej liczby złożonej z dziesięciu różnych cyfr i zastosował jakoby ukryty w jednym z wersetów algorytm iteracyjny, polegający na powtarzaniu następującego cyklu kroków: odcinamy końcową cyfrę, mnożymy ją przez 4 i dodajemy do liczby pozostałej po odcięciu. Na przykład, z liczby 2018 po odcięciu 8, pomnożeniu przez 4 i dodaniu 32 do 201 otrzymujemy 233; w następnym kroku z 233 powstaje 35 itd. (warto zauważyć, że w tym przypadku algorytm prowadzi do pętli przed dotarciem do liczby jednocyfrowej: 35→23→14→17→29→38→35→…). Po jednym z kolejnych kroków Twig uzyskał wynik 325 złożony z cyfr będących kolejnymi liczbami pierwszymi i wówczas wybrał z poprzednich wyników najmniejszy, który był liczbą pierwszą – i właśnie ten wynik, jego zdaniem, oznacza rok apokalipsy. Który to rok?
I dodatkowa zagadka: od jakiej 10-cyfrowej liczby Twig mógł zacząć obliczenia? Możliwości jest bardzo wiele, ale znaleźć choć jedną nie jest łatwo.
Komentarze
Gdyby zadanie, polegające na określeniu daty końca świata było przedmiotem konkursu, należałoby dodać warunek, że rozwiązania, które wpłyną po roku, będącym rozwiązaniem, nie będą brane pod uwagę.
Na pewno 325?
Bo jakby to było 235, to wówczas zestaw prezentowałby się tak:
235
1999 (liczba pierwsza)
19951
199471
1994671
19946671
199466671
1994666671
Liczba 325 nie generuje żadnej liczby pierwszej, wszystkie są podzielne przez 13.
Pani Olu, i o to chodzi (koniec końców).
mp
Ach, tak! Dowcipniś z tego Twiga. I z Pana też 🙂
To może jeszcze podam dowód, że nie może być ani jednej liczby pierwszej w zestawie liczb zawierającym 325, a uzyskiwanym wg metody Twiga.
325 – jest podzielne przez 13
y – liczba podzielna przez 13
x – ostatnia cyfra liczby y
(y-x)/10 + 4x =
(y-x)/10 + (40x)/10 =
(y-x+40x)/10 =
(y+39x)/10
39x – liczba podzielna przez 13
a zatem liczba (y+39x) jest także podzielna przez 13, czyli nie jest liczbą pierwszą.
Jeśli zacznie się od 10-cyfrowej czy innej dowolnie dużej liczby podzielnej przez 13, to wszystkie liczby w zestawie będą podzielne przez 13. Z takim zestawem musimy mieć do czynienia w przypadku Twiga – świadczy o tym 325.
Coś mi się zdaje, że ten Simon Twig to postać fikcyjna, a wygenerowanie liczby 325 tym algorytmem jest niemożliwe, jeśli zacząć od liczby złożonej z 10 różnych cyfr.
To słuszne podejrzenie
mp
Znowu ta trójka!
Nasza funkcja iterowana F zachowuje podzielność argumentu przez 3. Rzeczywiście, oznaczmy R(x) = MOD(x;10). Nasza funkcja iterowana to:
F(x) = (x – R(x))/10 + 4R(x) (suma funkcji liniowej i „piły”)
czyli
10F(x) = x + 39R(x)
Zatem jeśli 3|x to 3|10F(x). Ale 3 i 2*5 są względnie pierwsze, więc 3|F(x) (zasadnicze twierdzenie arytmetyki).
Dowolna z 3 265 920 liczb dziesięcio-różnocyfrowych jest podzielna przez 3, więc wszystkie wyrazy ciągu iteracji takiej liczby także muszą być podzielne. Zatem 325 nie może tu wystąpić w żadnym kroku.
PS. Planuję wykonać własne, niezwykle skomplikowane obliczenia daty końca świata, korzystając z informacji zawartych w „Przygodach Koziołka-Matołka”.
Nie wiem, czy to dobrze, czy źle, ale koniec świata chyba nigdy nie nastąpi. A może to jednak błąd w zrozumieniu treści zadania (ale próbowaliśmy z koleżanką rozwiązać je niezależnie i oboje trafiliśmy na tę samą przeszkodę):
Każda 10-cyfrowa liczba złożona z różnych cyfr jest podzielna przez 3, ponieważ suma jej cyfr to 45 (1+2+3+4+5+6+7+8+9+0).
Każda iteracja prowadzi do kolejnej liczby podzielnej przez 3. Matematyk nie mógł uzyskać 325, a ‚po drodze’ nie mógł uzyskać liczby pierwszej.
Jeżeli wyrazimy pierwszą, 10-cyfrową liczbę jako x, a pierwszą 9-cyfrową iterację jako y, to możemy zauważyć, że:
x = 10n + k
y = n + 4k
Wiemy, że x jest podzielne przez 3. Zatem 10n+k = 9n + n + k jest również podzielne przez 3, a więc n+k też. I stąd 3 przypadki:
1) n podzielne przez 3 i k podzielne przez 3 -> y również podzielne przez 3
2) n = 3w + 1 oraz k = 3v + 2 -> y = 3w + 1 + 12v + 8 = 3w+ 12v + 9 (podzielne przez 3)
2) n = 3w + 2 oraz k = 3v + 1 -> y = 3w + 2 + 12v + 4 = 3w+ 12v + 6 (podzielne przez 3)
Ta reguła działa dla każdej kolejnej iteracji, dlatego liczba 8, 7, … 3-cyfrowa także musi być podzielna przez 3 zawsze, jeśli pierwsza, 10-cyfrowa liczba jest złożona z różnych cyfr.
Czyli pierwsze zdanie komentarza jest właściwe.
mp
Zaczynając od końca (325) mozemy zauwazyć, że:
liczb czterocyfrowych prowadzących do 325 może być 10 (każda z inną cyfrą na końcu)
3250, 3211, 3172, 3133, 3094, 3055, 3016, 2977, 2938, 2899
idąc dalej liczb 5-cio cyfrowych może być 100, 6-cio cyfrowych 1000 itd.
10 cyfrowych liczb prowadzących do 325 jest 10000000
mieszczą się one w zakresie: 2860000039 – 3250000000
Niestety:
1. nie ma wśród nich liczb różnocyfrowych
2. nie ma wśród wyników pośrednich liczb pierwszych
Albo źle zrozumiałem treść zadania… 🙁
kod testowy tu: http://cpp.sh/4i7vu
Pozdrawiam,
Tomasz
Wnioski są właściwe. Końca świata nie będzie (koniec końców).
mp
Dopisek. Można uzyskać w trakcie iteracji 325 jeśli zacząć od odp. liczby startowej. Jeśli od dziesięciocyfrowej, to oczywiście muszą być powtórki cyfr (czyli braki innych cyfr), np.:
3158704120
315870412
31587049
3158740
315874
31603
3172
325
Rozumiem, że algorytm odcinania, mnożenia i dodawania kontynuujemy do otrzymania liczby, której cyfry tworzą zbiór kolejnych liczb pierwszych jednocyfrowych czyli wszystkie podzbiory zbioru { 2, 3, 5, 7}
Nie, chodzi o rok, który jest liczbą pierwszą (niekoniecznie złożoną z cyfr 2, 3, 5, 7).
Może od razu dodam, że zadanie z Simonem Twigiem (matematyk Szymon Patyk) jest żartem, który zapewne i tak by Pan bez trudu odkrył.
mp
Mamy więc podwójne zabezpieczenie przed końcem świata:
1. Iteracja w przód zachowuje podzielność przez 3, więc wychodząc od liczby złożonej z dziesięciu różnych cyfr nie dojdziemy do 325.
2. Iteracja w tył zachowuje podzielność przez 13, więc wychodząc od 325 nie dojdziemy do liczby pierwszej.
Można odetchnąć 🙂