Crossroad

Monday, 25 February 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 conjecture (Collatz Problem) www.j4.com...Collatz_Problem.htm:

Every whole number can be reduced to 1 by repeating the following steps.

  • Even: Divide by 2
  • Odd: Times 3 plus 1
The number 20 needs 7 steps to reach 1. Other numbers are more tricky. The number 9 for example needs a total of 19 steps. Does every number have a path leading to 1?

Diagram

www.onezero.org/collatz.html shows a interesting diagram that relates a number to the number of required steps. I haven't seen a diagram that shows the paths yet. So, I am proud to present the diagram below, visualising the paths.
  • Numbers run from left to right.
  • The steps required show from top to bottom.
  • A line connecting two numbers represents one step.
Step Number
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 

Do all paths end at 1?

The diagram above shows that all paths for numbers up to 17 end in 1. Yet, I haven't seen a convincing proof yet for all numbers.

However, the conjecture has not been proven wrong either. All numbers checked so far have a path leading to 1 (computrain.nl/...).

Multipowers

It's easy to check the multi powers of two (4, 8, 16, 32, 64, 128, ...). They are at the bottom of the diagram, at the highway towards 1. The path for all odd numbers ends on this highway with 16 -> 8 -> 4 -> 2 -> 1.

The number of steps leading to one seems a bit unpredictable, but roughly speaking it is a logaritmic function (home.mira.net/~greg...). That should not be a big surprise. Lots of other paths run parallel to the highway, consist of multiples of multi powers of 2. The path 80 -> 40 -> 20 -> 10 -> 5 for example is a fivefold. Every number is the start of a parallel highway.

Crossroads

An endless number of paths can only end up in one point through sufficient bifurcations, looking bottom to top. 5 divides at 10 into 3 and 20.

There are many bifurcations, 1/6 of all numbers (6n+4): 4, 10, 16, ...

Prediction

Ulam's conjecture will be proven,
  • not by crunching numbers till eternity using brute force,
  • but by showing that there are sufficient crossroads.
Till next week,
Nut