Úvod
Tento článok bude o Collatzovej domnienke (1) (Collatz conjecture). Tento problém je tiež známy pod názvami 3n + 1 problém, Ulamov problém (podľa Stanisława Ulama), Kakutanov problém (podľa Šizua Kakutaniho), Thwaitov problém (podľa sira Bryana Thwaitesa), Hassov algoritmus (podľa Helmuta Hasseho) alebo tiež ako Syrakuský problém. Collatzovú hypotézu doposiaľ nikto uspokojivo matematicky nedokázal.
Jeffrey Lagarias v roku 2010 uviedol, že Collatzova domnienka „je mimoriadne zložitý problém, ktorý je úplne mimo dosahu súčasnej matematiky“.
Pred ním podobný výrok vyslovil
Paul Erdős
(zhruba: matematika nie je pripravená na takéto problémy).
YouTube dokument (2) o tejto domnienke/hypotéze si môže čitateľ pozrieť napr. tu:
Definícia
Zadefinovanie tejto domnienky je triviálne (riešenie nie). Domnienka môže byť zhrnutá nasledovne. Zoberme akékoľvek kladné celé číslo n. Ak je n párne číslo, vydelíme ho dvoma, získame tak n/2. Ak je n nepárne číslo, vynásobí sa tromi a pripočíta sa jednotka, tj 3n + 1. Tento postup sa ďalej opakuje. Domnienka je taká, že nezáleží na tom, aké počiatočné číslo n je zvolené – výsledná postupnosť vždy nakoniec dôjde k číslu 1.
(1.0) Zdrojový kód/aplikácia
Pre vyskúšanie si tejto hypotézy si môže čitateľ stiahnuť zdrojový kód v Pythone, resp. aplikáciu - collatz.exe.
obr. 1 Aplikácia na výpočet Collatzovej hypotézy - verzia 1.0.
verzia 1.0 :
stiahnuť kód z GitHub: collatz.py
alebo stiahnuť ".exe" súbor: collatz.rar (komprimované WinRar, velkosť:72MB)
verzia 1.1: (vypíše aj maxima, kivy app)
stiahnuť kód z GitHub: collatz1.py
alebo stiahnuť ".exe" súbor: collatz1.rar (komprimované WinRar, velkosť:80MB)
POPIS: Algoritmus obsahuje výpočet pre rôzne čísla - n s vykreslením priebehu. V prípade, že zadáme interval vypočíta sa pre všetky čísla - n z intervalu dosiahnute maximum a vykreslí priebeh týchto maxím.
obr.2 Aplikácia na výpočet Collatzovej hypotézy - verzia 1.1.
Možná cesta k riešeniu (náčrt)
A) Žiadne celé číslo(integer) sa z hľadiska pravdepodobnosti nemôže dostať k nekonečnu (vrchol), pretože existuje pravdepodobnosť limitne blížiaca sa k p=1, že postupnosť C(n): 3n + 1 , resp. n/2 časom nutne narazí na zostupnú líniu (2,4,8,16,32...) - 2^x. Dalo by sa to formulovať čiste matematicky korektne s dôkazom z hľadiska pravdepodobnosti. B) Nevieme vylúčiť, že sa vývoj nedostane do slučky opakujúcej sa sekvencie čísiel, čím by postupnosť neskončila na 1. Empiricky sa preverili čísla zhruba do 2 ^ 68. Všetky skončili na 1. Tu môže dôjsť ku komplikácii v zmysle, že prečo nemôže sekvencia C(n) klesnúť na hodnotu ktorú už dosiahla. Pretože ak by klesla na úroveň, ktorú už dosiahla vznikla by slučka opakujúcich sa čísiel. Z hľadiska pravdepodobnosti sa preverilo veľa čísiel a k žiadnej slučke algoritmus nedošiel. Teda by mal existovať dôvod, prečo tomu tak je. Teda niekde na pozadí by sa možno dal odvodiť princíp, prečo k slučke nemôže dôjsť.Postupnosť 3n-1
Pre test postupnosti 3n-1 si čitateľ môže stiahnuť aplikáciu.
obr.3 Aplikácia na výpočet postupnosti 3x-1
verzia 1.1: (vypíše aj maxima, kivy app)
stiahnuť kód z GitHub: collatz1_3x-1.py
alebo stiahnuť ".exe" súbor: collatz1_3x-1.rar (komprimované WinRar, velkosť:80MB)
Program vypíše maxima aj posledné číslo postupnosti, teda >1, =1. Pokiaľ narazí na opakujúcu sa sekvenciu skončí pri >1. Pri preskúmavaní intervalu zobrazí len maxima na grafe. Pokiaľ by sa graf nezobrazil znamená to (okrem výpočtovej náročnosti vstupu), že program nenašiel periódy pre všetky čísla z intervalu, resp. neskončil na 1. To by znamenalo, že sa program zacyklil. To sa však z krátkych testov intervalov čísiel nestalo.
Analýza postupnosti:
Na rozdiel od originálnej postupnosti 3n+1, postupnosť 3n-1 dôjde z testov vždy k nejakej perióde opakujúcich sa čísiel, alebo skončí v 1 pokiaľ skôr narazí na zostupnú postupnosť 2^n. Tu je veľmi zaujímavé práve to, že tu vznikajú často periódy opakujúcich sa čísiel a postupnosť teda neklesne na 1. Oproti pôvodnej postupnosti 3n+1, kde nedošlo k perióde ani pre jedno číslo z intervalu od 1- 2 ^ 68 (testy). Toto je veľmi dôležité zistenie. Dôvod nepoznám, ale tu je priestor pre zistenie dôvodu.
Testy programom sekvencie 3n-1
Algoritmus našiel 2 opakujúce sa sekvencie, okrem zostupnej línie
2^n
, zapíšme si to nasledovne:(1) - je zostupná línia 2^n [...32,16,8,4,2,1]
(2) - je opakujúca sa sekvencia čísiel [ 5,14,7,20,10]
(3) - je opakujúca sa sekvencia čísiel [ 17,50,25,74,37,110,55,164,82,41,122,61,182,91,272,136,68,34]
Krátky test pre interval <3,1000> výpis nižšie:
V tomto intervale nenašiel inú opakujúcu sa sekvenciu.
Pre interval <3,10 000 000> znova nenašiel inú sekvenciu ako (1),(2),(3). Zdá sa, že to bude platiť smerom k nekonečnu a teda to, že existujú len dve opakujúce sa sekvencie (2),(3) pre sekvenciu 3x-1
Analýza opakujúcich sa sekvencii
Záver analýzy:
Sekvencie pre fractal 1 a 2 sú jedine možné. Pre rovnicu (1.0) však neexistuje nezáporné, celočíselné riešenie. Zdá sa nepravdepodobné, že by existoval pre rovnicu (1.1) iný jednoduchý vyhovujúci fraktál z dôvodu testu intervalu <3, 10 000 000>. No aj testy obrovských čísiel nebudú postačovať v zmysle matematického dôkazu. Treba hľadať iný spôsob ako dokázať, že pre rovnicu (1.1) existujú dve sekvencie a pre rovnicu (1.0), že neexistuje žiadna. Tento prístup, ktorý bol použitý vedie na metódu vytvárať všetky kombinácie fraktálov z ktorých by algoritmus vytváral všeobecné rovnice (viď.1.4 a 1.6) a hľadal všeobecné riešenie, čo nebude jednoduchá úloha. Zároveň množstvo fraktálov (vzorov sekvencii) je nekonečné, takže by musela existovať možnosť ako z nekonečných kombinácii rôznych fraktálov vyselektovať spočítateľnú množinu fraktálov (pokiaľ je to možné).Zdroje:
(1) Collatz conjecture(2) https://www.youtube.com/watch?v=094y1Z2wpJg