SUMit Roostersoftware > Wekelijkse Noot > Februari 2002 > Splitsing

Splitsing

Maandag, 25 februari 2002

Februari 2002

Splitsing

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.

Stap	Getal
xix									9
xviii																							28
xvii														14	15
xvi							7																					46
xv																				22	23
xiv											11																					70
xiii																									34	35
xii																	17																	106
xi																													52	53
x																						26														160
ix												12	13																				80
viii						6																					40
vii			3															20	21																128
vi										10																					64
v					5																			32
iv																16
iii	1							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