The Simplest Open Problem In Mathematics

The Collatz Conjecture was posed in 1937 by Lothar Collatz, two years after he received his Ph.D. It remains open to this day.

“Mathematics may not be ready for such problems.” — Paul Erdős.

“This is an extraordinarily difficult problem, completely out of reach of present day mathematics.” — Jeffrey Lagarias

What’s the conjecture about?

The Collatz Conjecture states that any natural number will resolve into 1 after applying these conditions iteratively:

If the number is even, divide it by 2.
If the number is odd, multiply it by 3 and add 1.

Sounds simple enough right? Let’s go through some examples, assuming we picked n = 5:

5 is odd so we multiply it by 3 and add 1: 5*3 + 1 = 16
16 is even so we divide it by 2: 16/2 = 8
8 is even so we divide it by 2: 8/2 = 4
4 is even so we divide it by 2: 4/2 = 2
2 is even so we divide it by 2: 2/1 = 1
We have reached the number 1 after 5 iterations.
Also note that in order for us to get to 1 with n=5 we had to climb up to 16.

Some numbers require a lot more iterations, for example if we have picked n=3331 we would have to perform 180 iterations before getting to 1 and while doing so, we would climb up to 250504.

Visualizing the problem

In case you’ve pondered how is the number of iterations is distributed or how is the max value of each number is distributed, I got you covered.

#Iterations on numbers from 1 to 10,000
Same graph but with numbers up to 100,000 including the maximum lines.

The maximum number of iterations on the above graph is 350 and we get that value for n=77031.

The maximum number we ‘climb’ up to while applying each number.

These graphs were created by the following code, feel free to tweak it

import matplotlib.pyplot as plt
%matplotlib inline

def collatz(x, b=False):
  if x % 2 == 0:
    if b:
        print(f'{x} is even, {x}/2 = {x/2}')
    return x / 2
    if b:
        print(f'{x} is odd, {x}*3 + 1 = {x*3 + 1}')
    return 3*x + 1

def compute_iterations(x, b=False):
  iter = 0
  y = x
  max = y
  while y != 1:
    y = collatz(y, b)
    if y > max: max = y
    iter += 1
  print(f'{x} required {iter} iterations')
  return (x, iter, max)

def graph_collatz():
    x_axis, y_axis, max_axis, m, m_x = get_data()
    plt.plot(x_axis, y_axis, 'b.')
    plt.plot(x_axis, [m for i in range(1, len(y_axis)+1)], 'r--')
    plt.plot([m_x for i in range(1, len(x_axis)+1)], y_axis, 'r--')
    plt.ylabel('Number of iterations')

def graph_max_collatz():
    x_axis, y_axis, max_axis, m, m_x = get_data()
    plt.plot(x_axis, max_axis, 'r-')
    plt.ylabel('Max number while getting to 1')
def get_data():
    collatz = [compute_iterations(i) for i in range(1, 100000)]

    x_axis = [a for (a, b, c) in collatz]
    y_axis = [b for (a, b, c) in collatz]
    max_axis = [c for (a, b, c) in collatz]

    m = max(y_axis)
    m_x = x_axis[y_axis.index(m)]
    return x_axis, y_axis, max_axis, m, m_x


Lastly, here’s a tree of all numbers that require less than 20 iterations before getting to 1.

The tree of all numbers having fewer than 20 iterations, from Wikipedia.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: