Visualization of Collatz Conjecture using Python

Visualization of Collatz Conjecture using Python

  August 10, 2020    Roy John

---

The Collatz Conjecture

The Problem

The Collatz conjecture (a.k.a the hailstone problem or the $3n + 1$ problem) was proposed by Lother Collatz in 1937. Although the problem on which the conjecture is based is really simple that even a fourth-grader can easily understand it, the behaviour of the conjecture makes it exceedingly difficult to prove(or disprove). 

First of all, lets define the Collatz map. Let $T : \mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ be defined by

The conjecture is that for every positive integer $n$, there exists a $k$ such that  $T^k(n) = 1$.

Let us consider an example.

As mentioned above, the conjecture states that this is true for any positive integer n. But what makes this problem interesting is that even after 60  years since its proposal nobody has been able to prove (or disprove) it. Mathematicians say the "Mathematics is yet not ready to tackle such problems." So far the conjecture has been checked for all starting values up to $87 \times 2^{60}$. All initial values tested so far eventually end up in 1.

Program

#Program to check the Collatz conjecture for a given range of numbers.

def collatz(x):

    a = [x]

    while x!=1:

        if x % 2 == 0:

            x = x/2

        else:

            x = 3*x + 1

        a.append(x)

    if a[len(a)-1] == 1:

        return("Yes")

    else:

        return("No")

for i in range(1,100000):

    print(i,collatz(i))

This program checks the conjecture for the first 100000 positive integers, all of which returns to be true.

Visualization

Now, what we are really interested is on the visualization of the problem. We try to visualize the problem with the aid of Python programs and try to find some patterns that may arise in the figures.

• Stopping time
  Python program to compute the stopping time $k$ for each $n$ and plot them against $n$ in a graph.
  
  Program
  #Program to compute the stopping time for each n and to plot it in a graph.
  import matplotlib.pyplot as plt
  def collatz(x):
      a = [x]
      while x != 1:
          if x % 2 == 0:
              x = x/2
          else:
              x = 3*x + 1
          a.append(x)
      return(a)
  x=[]
  y=[]
  for i in range(1,10000):
      a = collatz(i)
      x.append(i)
      y.append(len(a))
  plt.plot(x,y,"o")
  plt.show()
  
  We can see a pattern in the obtained graph.
  
  
  
  
• The highest value in the iteration
  For each $n$, the composition of the function $T$ yields an upper bound. For example, 16 in the case of n = 6. Let's plot the graph of this largest value obtained in the iteration for each n and try to figure out some patterns from the graph.|
  Program
  #Highest value in the iteration
  import matplotlib.pyplot as plt
  def collatz(x):
      a = [x]
      while x != 1:
          if x % 2 == 0:
              x =x/2
          else:
              x = 3*x + 1
          a.append(x)
      return(a)
  b = []
  c = []
  for i in range(1,1000):
      c.append(max(collatz(i)))
      b.append(i)
  plt.plot(b,c,"o")
  plt.show()

From the graph, it is evident that for the first 1000 positive integers the highest value obtained in the iteration for almost all $n$'s is bounded in the y-axis. For some $n$ they wander off to large numbers.

The Feather

Now let's get back to the feather we discussed earlier. Let's make a directed graph for the conjecture. It somewhat looks like this:

Now starting from 1 move upward along the graph. An edge incident to an even number should be curved slightly towards the right and the one incident to an odd number should be curved slightly towards the left. Lose the numbers on the graph and colour the graph according to your imagination. This yields the feather.