The 3n+1 problem and Benford’s law

This is the third, and last, of a series of posts on Benford’s law, this time looking at a famous open problem in computer science, the 3n + 1 problem, also known as the Collatz conjecture.

Start with a positive integer n. Compute 3n + 1 and divide by 2 repeatedly until you get an odd number. Then repeat the process. For example, suppose we start with 13. We get 3*13+1 = 40, and 40/8 = 5, so 5 is the next term in the sequence. 5*3 + 1 is 16, which is a power of 2, so we get down to 1.

Does this process always reach 1? So far nobody has found a proof or a counterexample. (But there has been progress.)

If you pick a large starting number n at random, it appears that not only will the sequence terminate, the values produced by the sequence approximately follow Benford’s law (source). If you’re unfamiliar with Benford’s law, please see the first post in this series.

Here’s some Python code to play with this.

from math import log10, floor

def leading_digit(x):
    y = log10(x) % 1
    return int(floor(10**y))

# 3n+1 iteration
def iterates(seed):
    s = set()
    n = seed
    while n > 1:
        n = 3*n + 1
        while n % 2 == 0:
            n = n / 2
        s.add(n)
    return s

Let’s save the iterates starting with a large starting value:

it = iterates(378357768968665902923668054558637)

Here’s what we get and what we would expect from Benford’s law:

|---------------+----------+-----------|
| Leading digit | Observed | Predicted |
|---------------+----------+-----------|
|             1 |       46 |        53 |
|             2 |       26 |        31 |
|             3 |       29 |        22 |
|             4 |       16 |        17 |
|             5 |       24 |        14 |
|             6 |        8 |        12 |
|             7 |       12 |        10 |
|             8 |        9 |         9 |
|             9 |        7 |         8 |
|---------------+----------+-----------|

We get a chi-square of 12.88 (p = 0.116) and so we get a reasonable fit.

Here’s another run with a different starting point.

it = iterates(243963882982396137355964322146256)

which produces

|---------------+----------+-----------|
| Leading digit | Observed | Predicted |
|---------------+----------+-----------|
|             1 |       44 |        41 |
|             2 |       22 |        24 |
|             3 |       15 |        17 |
|             4 |       12 |        13 |
|             5 |       11 |        11 |
|             6 |        9 |         9 |
|             7 |       11 |         8 |
|             8 |        6 |         7 |
|             9 |        7 |         6 |
|---------------+----------+-----------|

This has a chi-square value of 2.166 (p = 0.975) which is an even better fit.

See also: Benford’s law posts organized by application area