Ú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

Introduction

This article will be about the Collatz conjecture (1) (Collatz conjecture). This problem is also known by the names 3n + 1 problem, Ulam's problem (after Stanisław Ulam), Kakutani's problem (after Shizuo Kakutani), Thwaites' problem (after Sir Bryan Thwaites), Hasse's algorithm (after Helmut Hasse), or also as the Syracuse problem. The Collatz hypothesis has not yet been satisfactorily mathematically proven by anyone.

Jeffrey Lagarias stated in 2010 that the Collatz conjecture "is an extraordinarily difficult problem that is completely beyond the reach of current mathematics".

Before him, a similar statement was made by Paul Erdős (roughly: mathematics is not ready for such problems).

Readers can watch a YouTube document (2) about this conjecture/hypothesis here:

Definition

Defining this conjecture is trivial (the solution is not). The conjecture can be summarized as follows. Take any positive integer n. If n is an even number, divide it by two to get n/2. If n is an odd number, multiply it by three and add one, i.e., 3n + 1. This process is then repeated. The conjecture is that regardless of what initial number n is chosen – the resulting sequence will always eventually reach the number 1.

(1.0)

Source Code/Application

To test this hypothesis, readers can download the source code in Python or the application - collatz.exe.

Fig. 1 Application for calculating the Collatz hypothesis - version 1.0.

Version 1.0:
Download code from GitHub: collatz.py
Or download ".exe" file: collatz.rar (compressed WinRar, size: 72MB)

Version 1.1: (also prints maxima, kivy app)
Download code from GitHub: collatz1.py
Or download ".exe" file: collatz1.rar (compressed WinRar, size: 80MB)

DESCRIPTION:
The algorithm contains calculations for various numbers - n with plotting of the progression. If we specify an interval, it calculates for all numbers - n from the interval the reached maximum and plots the progression of these maxima.

Fig. 2 Application for calculating the Collatz hypothesis - version 1.1.

---

Possible Path to Solution (Outline)

A) No integer can reach infinity (peak) from a probabilistic perspective, because there exists a probability approaching p=1 that the sequence C(n): 3n + 1 or n/2 will eventually hit a descending line (2,4,8,16,32...) - 2^x. This could be formulated purely mathematically correctly with proof from a probabilistic perspective.

B) We cannot rule out that the development does not get into a loop of repeating number sequences, whereby the sequence would not end at 1. Empirically, numbers up to approximately 2^68 have been verified. All ended at 1. Here, complications may arise in the sense that why the sequence C(n) cannot drop to a value it has already reached. Because if it dropped to a level it had already reached, a loop of repeating numbers would arise. From a probabilistic perspective, many numbers have been verified and the algorithm did not reach any loop. So there should be a reason why this is so. That is, somewhere in the background, a principle could perhaps be derived why a loop cannot occur.

---

Sequence 3n-1

For testing the sequence 3n-1, readers can download the application.

Fig. 3 Application for calculating the sequence 3x-1

Version 1.1: (also prints maxima, kivy app)
Download code from GitHub: collatz1_3x-1.py
Or download ".exe" file: collatz1_3x-1.rar (compressed WinRar, size: 80MB)

The program prints maxima and the last number of the sequence, i.e., >1, =1. If it encounters a repeating sequence, it ends at >1. When examining an interval, it displays only maxima on the graph. If the graph does not display, it means (besides computational complexity of the input) that the program did not find periods for all numbers from the interval, or did not end at 1. This would mean the program got stuck in a loop. However, this did not happen from short tests of number intervals.

Sequence Analysis:
Unlike the original sequence 3n+1, the sequence 3n-1 always reaches some period of repeating numbers from tests, or ends at 1 if it encounters the descending sequence 2^n earlier. What is very interesting here is that periods of repeating numbers often arise and the sequence therefore does not drop to 1. Compared to the original sequence 3n+1, where no period occurred for any number from the interval 1-2^68 (tests). This is a very important finding. I don't know the reason, but there is room here for finding the reason.

Tests by 3n-1 Sequence Program

The algorithm found 2 repeating sequences, besides the descending line 2^n, let's write it as follows:

(1) - is descending line 2^n [...32,16,8,4,2,1]

(2) - is repeating sequence of numbers [5,14,7,20,10]

(3) - is repeating sequence of numbers [17,50,25,74,37,110,55,164,82,41,122,61,182,91,272,136,68,34]

Short test for interval <3,1000> output below:

In this interval, no other repeating sequence was found.

---

For interval <3,10,000,000> again no other sequence was found than (1),(2),(3). It seems this will hold toward infinity and therefore only two repeating sequences (2),(3) exist for sequence 3x-1

Analysis of Repeating Sequences

Analysis Conclusion:

Sequences for fractal 1 and 2 are the only possible ones. For equation (1.0) however, there is no non-negative, integer solution. It seems improbable that there would exist for equation (1.1) another simple satisfying fractal due to testing interval <3, 10,000,000>. But even tests of huge numbers will not suffice in terms of mathematical proof. We need to find another way to prove that for equation (1.1) two sequences exist and for equation (1.0), that none exists. This approach that was used leads to a method of creating all combinations of fractals from which the algorithm would create general equations (see 1.4 and 1.6) and search for general solutions, which will not be a simple task. At the same time, the number of fractals (sequence patterns) is infinite, so there would have to be a way to select a countable set of fractals from infinite combinations of different fractals (if possible).

Sources:

(1) Collatz conjecture
(2) https://www.youtube.com/watch?v=094y1Z2wpJg