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.
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.
Here’s another run with a different starting point.
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.
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.
Using