Samuel Kováčik
KTF FMFI UK
Collatzova hypotéza
Prvý krát som sa o Collatzovej hypotéze (domnienke) dozvedel na stránke svojho obľúbeného XKCD. Hypotéze hovorí zhruba toto : vyber si hocijaké prirodzené číslo a opakuj tento postup : ak je párne, predel ho 2, ak nepárne, prenásob 3 a pripočítaj 1. Ak toto zopakuješ dosť veľa krát, dostaneš sa do 1 (pre ľubovoľné počiatočné číslo). Čiže napríklad 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1. Alebo 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 →... pokračuje ako v predošlom príklade. Skáče to divoko, hore, dole, ale (asi) vždy sa nakoniec dostane do 1 (testované po rádovo 10^18, čiže miliardu miliard). Dokázať, že to platí všeobecne je tuhý oriešok, o čom svedčí aj fakt, že Paul Erdős za jeho riešenie ponúkol 500$ (kľúčová nie je suma, ale osoba, ktorá ju ponúka).
Kód programu, čo vykonáva tento cyklus vyzerá jednoducho, napríklad tento nám spočíta, za koľko krokov sa dostaneme do čísla 1 ak začneme číslom 77


int k=77, d=0;
while(k!=1)
{if(k%2==0){k=k/2;}
else{k=3*k+1;}
d++;}
System.out.print(d);


Doplnením takéhoto jednoduchého programu môže človek objaviť kopu zaujímavého, napríklad na wikipédii je graf, ktorý hovorí k akej maximálnej hodnote sa počas sekvencie číslo dostane. Mňa ale najviac dostalo toto : graf, ktorý ukazuje, koľko cyklov potrebuje dané číslo, aby sa dostalo do 1. Fascinuje ma, že aj napriek tomu, že na prvý pohľad je celý proces veľmi náhodný (číslo 8 ide do 1 na 3 kroky, číslo 7 na 16), sa čísla spájajú do skupín a tieto skupiny ako keby ležali na spoločných krivkách, čo je veľmi prekvapivé a aj zaujímavé. Je tam toho dosť na vyskúšanie, ak chete, tu je môj java zdrojový kód.

PS1: To, že to platí pre prvých 1 000 000 000 000 000 000 čísiel ešte neznamená, že to musí platiť pre všetky, viď napríklad Mertensova hypotéza, kde sa zistilo, že prvý protipríklad sa takmer určite nachádza ešte pred číslom e^(10^65), zdroj je tu.

PS2: Moje nové obľúbené tričko.

Koľko krokov potrebuje prvých 10 000 čísiel. Photo One
Koľko krokov potrebuje prvých 100 000 čísiel. Photo One
Rozloženie (štatistické) počtu krokov pre prvých 100 000 000 čísiel.
Photo One
Kontakt
Miestnosť : F 132
Email: samuel.kovacik[zavináč]gmail.com