Het vermoeden van Collatz

In de wiskunde kom je soms rare dingen tegen. Zo zijn er de getallen π (ongeveer 3.14) en φ (ongeveer 1.61), waarvan de exacte grootte na jarenlang zoeken nog steeds niet bekend is.
Zo zijn er ook stellingen in de wiskunde waarvan iedereen op zijn klompen aanvoelt dat ze juist zouden kunnen zijn, maar waarvan tot nu toe (oktober 2024) niemand heeft kunnen aantonen dat ze juist (of onjuist) zijn.
Een voorbeeld uit de getaltheorie is bekend als "Het vermoeden van Collatz", naar de Duitse wiskundige Lothar Collatz (1910 - 1990), die dit vermoeden in 1937 voor het eerst voorstelde.

Collatz is niet de enige die zich hiermee heeft bezighouden. Je kunt dit ook tegenkomen met de namen Ulam vermoeden, Kakutani's probleem, Thwaites' vermoeden, Hasse's algoritme, Syracuse probleem, hagelsteen getallen en gewoon 3N+1.

Het vermoeden van Collatz is dat elke reeks gehele positieve getallen, waarvan het eerste element willekeurig wordt gekozen en die is opgebouwd volgens een bepaald voorschrift (lees: algoritme) altijd eindigt op 1.
Het voorschrift luidt:
    º Kies het eerst element n0 ≥ 0.
    º Als ni is oneven: ni+1 = 3ni + 1;
    º Als ni is even: ni+1 = ni / 2;

Merk op dat de uitkomst van 3ni + 1 altijd een even getal is, en daardoor altijd gevolgd wordt door ni / 2.
Als je de regels toepast op een willekeurig positief, geheel getal, komt de reeks altijd uit op 16 8 4 2 1.

Als je de regels toepast op ni = 1, wordt ni+1 = 3ni + 1 = 4.
Vervolgens wordt ni+1 = ni / 2 = 2,
daarna wordt ni+1 = ni / 2 = 1,
daarna wordt ni+1 = 3ni + 1 = 4, enzovoort.
Er ontstaat een lus, die zich eindeloos herhaalt.

Voorbeeld: Begin de reeks met n0 = 3:
n0 = 3 (oneven) ⇒ n1 = 3×3+1 = 10 (even) ⇒ n2 = 10/2 = 5 (oneven) ⇒ n3 = 3×5+1 = 16 (even) ⇒ n4 = 16/2 = 8 (even) ⇒ n5 = 8/2 = 4 (even) ⇒ n6 = 4/2 = 2 (even) ⇒ n7 = 2/2 = 1 (stop)
Er zijn 7 stappen nodig om 1 te bereiken. Dit wordt de stoptijd genoemd.

De stoptijd en de startwaarde zijn niet evenredig met elkaar. Een hogere startwaarde betekent niet noodzakelijk dat de stoptijd ook hoger wordt. Dat komt doordat reeksen (gedeeltelijk) aan elkaar gelijk zijn. Vergelijk de reeks met startwaarde 5 maar eens met de reeks met startwaarde 3 uit het voorbeeld:
n0 = 5 (oneven) ⇒ n1 = 3×5+1 = 16 (even) ⇒ n2 = 16/2 = 8 (even) ⇒ n3 = 8/2 = 4 (even) ⇒ n4 = 4/2 = 2 (even) ⇒ n5 = 2/2 = 1 (stop)
Er zijn 5 stappen nodig om 1 te bereiken. De stoptijd is 5.

Het volgende tabelletje illustreert de stoptijd in vergelijking met een paar start­waarden.

Hiernaast zie je het verloop van de reeks met startwaarde 27. Zoals je ziet loopt de waarde een paar keer heel ver weg van de startwaarde: 7288 in stap 67 en 9232 in stap 77. De daling naar 1 begint pas echt na stap 88.

Het verloop van de reeks bevat veel snelle stijgingen en dalingen, zoals hagelstenen in een onweerswolk, die uiteindelijk allemaal naar beneden vallen. Althans dat denken we, want voor het vermoeden van Collatz is er nog steeds geen sluitend bewijs …

De grafiek vertoont overeenkomsten met de beweging van de aandelenkoersen op de beurs, met het verschil dat het bedoeling is dat de aandelenkoersen een stijgende tendens vertonen en de reeksen van Colatz een dalende tendens. Beide grafieken vertonen hetzelfde gedrag als van de Brownse beweging. Dat betekent dat de fluctuaties willekeurig zijn.

Als je dieper ingaat op de formules en je bedenkt dat er even veel even als oneven getallen zijn, zou je een stijgende tendens verwachten in plaats van een dalende. Dat omdat oneven getallen ruwweg met 3 worden vermenigvuldigd, en even getallen worden gedeeld door twee. Maar omdat een oneven getal na 3n+1 altijd even is, en dus gedeeld wordt door twee, wordt een oneven getal ruwweg vermenigvuldigd met 1,5. Dat verklaart de dalende tendens.

Een paar opvallende ideeën om de (on)juistheid van het vermoeden van Collatz te bewijzen zijn:

• Probeer zoveel mogelijk getallen, en kijk of het vermoeden klopt, of niet. Sinds 2022 is voor —bij mijn weten— 2⁶⁸ = 295 147 905 179 352 825 856 getallen het vermoeden nagegaan, geen ervan was onjuist. Maar er zijn meer getallen …
• Elke reeks komt uit op 16 8 4 2 1. Er wordt, met andere technieken dat de brute force benadering, ook gezocht of er getallen zijn waarvan de reeks uitmondt in een andere eindloze lus dan 4 2 1, wat de onjuistheid van het vermoeden zou bewijzen. Een dergelijke lus is nog niet gevonden.

De beroemde wiskundige Paul Erdös heeft over het vermoeden van Collatz gezegd: "De Wiskunde is nog niet rijp voor dit soort vragen.". Dat kan ons er niet van weerhouden om er een beetje mee te spelen. Als je op de knop hiernaast klikt, komt er een applicatie waar je een startwaarde invoert en die vervolgens een lijst geeft met de berekende waarden en daar een grafiek van tekent.
De applicatie geeft de stoptijd, de hoogste waarde in de reeks en de stap waar dat optreedt.
De hoogst mogelijke waarde van n₀ is 9 999 999 999 999 998. Daarboven ontspoort het rekenproces, doordat de omzetting van string naar getal dan fout gaat.
De code van de applicatie kun je downloaden om zelf aan door te ontwikkelen.

Downloaden:
 
Druk op de knop:  File: voorb756.zip, 2520 bytes.