Vermoeden van Collatz

Het vermoeden van Collatz is een vermoeden uit de getaltheorie dat de volgende iteratie bestudeert:

Neem een willekeurig geheel getal n.

 Als n even is
   Deel n door 2
 Als n oneven is
   Vermenigvuldig n met 3 
   Tel er 1 bij op

Het vermoeden van Collatz zegt nu dat welk getal je ook kiest, als je dit proces lang genoeg herhaalt, wordt n uiteindelijk altijd 1. Dit vermoeden is voor het eerst geformuleerd door Lothar Collatz in 1937. Tot op heden is het vermoeden nog niet bevestigd of weerlegd.

Inhoud 1 Wiskundige notatie 2 Voorbeelden 3 Optimaliseringen 4 Aanwijzingen 5 Opmerkelijkheden

[bewerk] Wiskundige notatie

De wiskundige notatie is als volgt:

We beginnen met het definiëren van een functie:

Nu maken we een rij a waarin we de functie f steeds herhalen. In wiskundige notatie ziet dit er als volgt uit:

Nu is het vermoeden als volgt:

[bewerk] Voorbeelden

Als voorbeeld nemen we n = 12, De rij a ziet er nu als volgt uit: 12, 6, 3, 10, 5, 16, 8, 4, 2, 1.

Nemen we n = 15 dan krijgen we een veel langere rij: 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

[bewerk] Optimaliseringen

• Als n deelbaar is door 4, moet je n delen door 4.

Verklaring:n is even. Deel n door 2 en hij is weer even. Je moet n weer door 2 delen.

• Algemener: Alle factoren 2 in de priemontbinding kunnen verwijderd worden.

Verklaring:Zolang n een factor 2 heeft, is het even en dient het door 2 gedeeld te worden. Hierdoor wordt het aantal factoren 2 één minder.

• Als n oneven is, vermenigvuldig je met 3/2 en tel je er 1/2 bij op.

Verklaring:n is oneven. vermenigvuldig n met 3, 3n blijft nu oneven. Tel 1 bij 3n op, nu wordt 3n+1 even en moet je door 2 delen.

• We hoeven alleen te bewijzen dat

Verklaring: Als we kunnen bewijzen dat er voor elke n een getal p voorkomt in de rij waarvoor geldt p < n, dan zal er een getal q voorkomen dat kleiner is dan p, en weer een getal kleiner dan q, net zolang tot je bij 1 komt.

• Dit hoeft alleen bewezen te worden voor getallen 3 mod 4.

Verklaring: Getallen 0 of 2 mod 4 worden meteen kleiner, omdat je ze door 2 deelt. Getallen 1 mod 4 worden na 3n+1 0 mod 4 en ze zijn nu deelbaar door 4. 3/4n+1/4 < n (voor n > 1)

• Bij hogere modulo's vallen er meer getallen uit, zoals n = 3 mod 16.

Verklaring: n = 3 mod 16, 3n+1 = 10 mod 16, 3/2n+1/2 = 5 mod 8, 9/2n+5/2 = 0 mod 8 9/16n+5/16 < n. Voor n mod 1024 blijven er slechts 64 mogelijkheden over. (Dit is 6.25%) voor n mod 1024² blijft er slechts 2% over.

[bewerk] Aanwijzingen

Er is een aantal aanwijzingen dat het vermoeden van Collatz waar is.

Voor alle getallen onder 4.81 * 10¹⁷ is gecontroleerd dat ze aan het vermoeden voldoen. Het probleem met het controleren is dat het alleen het vermoeden kan weerleggen. Als het vermoeden waar is kan er geen bewijs voor gevonden worden op deze manier.

Daarnaast geldt dat als je naar alle oneven getallen kijkt, dat ieder getal gemiddeld 3/4 is van het getal ervoor, en dat als je het lang genoeg blijft herhalen, het getal dus steeds kleiner wordt.

[bewerk] Opmerkelijkheden

Er zijn getallen n te creëren die p-1 keer door 2 gedeeld moeten worden en de p-de keer met 3 vermenigvuldigd moeten worden en met 1 verhoogd moeten worden. Deze getallen zijn van de vorm 2^{p − 1} mod 2^p. Bij deling door 2 worden ze 2^{p − 2} mod 2^{p − 1}. Dit herhaal je net zo lang tot ze 2⁰ mod 2¹ worden.

Ook kan je getallen maken die p-1 keer met 3 moeten worden vermenigvuldigd en 1 verhoogd.

• n = 2^{p − 1} − 1 mod 2^p. Dit is een oneven getal.
• Vermenigvuldigd met 3 wordt 2^{p − 1} − 3 mod 2^p.
• Plus 1: 2^{p − 1} − 2 mod 2^p.
• Gedeeld door 2:2^{p − 2} − 1 of 2^{p − 2} − 1 + 2^{p − 1} = 3 * 2^{p − 2} − 1 mod 2^p

Dit is gelijk aan: 2^{p − 2} − 1 mod 2^{p − 1} Waar eerst p stond staat nu p-1. Blijf dit herhalen tot er 0 overblijft. Dan is 2⁰ − 1 mod 2¹ en dit betekent dat p even is.

Het opmerkelijkste hieraan is dat deze getallen slechts 1 uit elkaar liggen.