The 3n+1 problem

Consider the following function:

f(n)={n/2 if n even, 3n+1 if n odd}, n in N.

We ask what happens when we apply f continuously given a certain natural n.

For example, for n=3 we get the sequence: 3, 10, 5, 16, 8, 4, 2, 1. Will any number eventually stabilize on 1? If you try to program a trivial little program that shows you this sequence, you will be convinced that eventually all tried numbers go to 1.

Given that, define a sequence pn=period of n. So in the example above, p3=8. Now define another sequence as follows:

φm,n={1≤k≤m: pk=n}. So essentially, φm,n counts how many numbers have a given period n in the range 1≤k≤m.

Does φm,n converge? More specifically, does limm->∞φm,n  exist for given n? What about limn->∞pn?

The 3n+1 question or Collatz Conjecture is an unsolved problem. Given that, one would expect that the second question would be unsolved as well. It appears that φm,n diverges. The following are graph plots of φm,n versus pn. Successively they are φ200,n φ400,n φ800,n φ8000,n and φ20000,n. pn ranges on the graphs from 1 to 124, 143, 170, 261 and 278:

200

400

800

8000

20000

More on this on MathWorld.