Friday, June 3, 2011

The Collatz conjecture

The Collatz conjecture is a famous unsolved problem in number theory. Start with any
positive integer n. Repeat the following steps:
  • If n = 1, stop.
  • If n is even, replace it with n/2.
  • If n is odd, replace it with 3n + 1

The unanswered question is, does the process always terminate?

Let to see a script that generate the sequence of number involved by the algorithm:

import sys
from pylab import *

# take n from the command line
n = int(sys.argv[1])

i = 0
old_n = n
while n > 1:
 if n%2 == 0: # if n is even
  n = n/2
  n = 3*n+1
 i += 1;
 plot([i-1, i],[old_n,n],'-ob')
 old_n = n

title('hailstone sequence for '+sys.argv[1]+', length is '+str(i))
The script will plot the sequence:
$ python 25

The Collatz conjecture is is also known as the 3n + 1 conjecture, the Ulam conjecture, Kakutani's problem, the Thwaites conjecture, Hasse's algorithm, or the Syracuse problem; the sequence of numbers involved is referred to as the hailstone sequence or hailstone numbers, or as wondrous numbers.



  1. Your description of the problem is different from what your implementation would suggest. You say n even -> replace with n=2. I guess your implementation is right.

    Just found this blog, by the way. Good work!

  2. Thank you Fredrik, It was a mistake in the text. I just fixed it.


Note: Only a member of this blog may post a comment.