# 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

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.

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
else:
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.xlabel('Numbers')
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.xlabel('Numbers')
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)
print(m)
m_x = x_axis[y_axis.index(m)]
print(m_x)
print(max(max_axis))

return x_axis, y_axis, max_axis, m, m_x

graph_max_collatz()
``````

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.