Splitsing

Maandag, 25 februari 2002
vii 20 / 2 = 10
vi 10 / 2 = 5
v 5 x 3 + 1 = 16
iv 16 / 2 = 8
iii 8 / 2 = 4
ii 4 / 2 = 2
i 2 / 2 = 1
Ulam's aanname (Collatz Problem) www.j4.com...Collatz_Problem.htm:

Elk geheel getal is tot 1 te herleiden door de volgende stappen te herhalen.

  • Even: Deel door 2
  • Oneven: Maal 3 plus 1
Het getal 20 gaat in zeven stappen naar 1. Andere getallen zijn lastiger. Het getal 9 bijvoorbeeld heeft wel 19 stappen nodig. Is er voor elk getal een pad naar 1?

Diagram

Op www.onezero.org/collatz.html staat een aardig diagram dat het verband toont tussen een getal en het aantal nodige stappen. Een diagram dat de paden toont heb ik nog nergens gevonden. Met trots presenteer ik daarom het diagram hieronder dat de paden visualiseert.
  • De getallen staan van links naar rechts.
  • De nodige stappen staan van boven naar beneden.
  • Een lijn tussen twee getallen is één stap.
StapGetal
xix 9  
xviii  28 
xvii  1415  
xvi 7   46 
xv  2223  
xiv 11   70 
xiii  3435  
xii 17   106 
xi  5253  
x  26  160
ix  1213   80 
viii  6  40 
vii 3   2021    128 
vi  10  64 
v 5   32 
iv  16 
iii1   8 
ii  4 
i 2 
 1 

Eindigen alle reeksen in 1?

Het diagram hierboven toont dat het pad voor alle getallen tot en met 17 in 1 uitkomen. Tot nu toe heb ik nog niet gehoord van een sluitend bewijs voor alle getallen.

Het tegendeel is echter ook nog niet aangetoond. Alle getallen die tot nu toe gecontroleerd zijn komen keurig op 1 uit (computrain.nl/...).

Veelmachten

Voor de veelmachten van twee (4, 8, 16, 32, 64, 128, ...) is het makkelijk. Ze zitten op de bodem van het diagram, op de snelweg richting 1. Het pad voor alle oneven getallen eindigt op deze snelweg met 16 -> 8 -> 4 -> 2 -> 1.

Het aantal stappen naar 1 lijkt wat onvoorspelbaar, maar ruwweg is het een logaritmische functie (home.mira.net/~greg...). Dat is niet zo verwonderlijk. Veel andere paden lopen parallel aan de snelweg, bestaan uit veelvouden van veelmachten van 2. Het pad 80 -> 40 -> 20 -> 10 -> 5 is bijvoorbeeld een vijfvoud. Elk getal is de start van een parallelle snelweg.

Splitsingen

Een oneindige hoeveelheid paden kan alleen maar in 1 punt eindigen door genoeg splitsingen, van beneden naar boven. 5 splitst via 10 naar 3 en 20.

Er zijn vele splitsingen, 1/6 van alle getallen (6n+4): 4, 10, 16, ...

Voorspelling

Ulam's vermoeden zal een keer bewezen worden,
  • niet door met brute force alle getallen tot in de oneindigheid te kraken,
  • maar door aan te tonen dat er genoeg splitsingen zijn.
Tot de volgende week,
Henk Jan Nootenboom