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
 else:
  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))
show()
The script will plot the sequence:
$ python collatz.py 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.

References

2 comments:

  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!

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

    ReplyDelete

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