The Collatz conjecture

The “Half Or Triple Plus One” algorithm

The conjecture

For every natural number n, the “Half Or Triple Plus One” algorithm will eventually lead to the number 1, at which point it will loop forever:

1 → 4 → 2 → 1

This implies two things:

  1. The algorithm always eventually decreases
  2. There are not cycles besides the 1 → 4 → 2 → 1 cycle

Your mission

  1. Understand this program which prints the “collatz sequence” for 27.
n = 27
while n > 1:
  print n
  if n % 2 == 0:
    n /= 2
  else:
    n = n*3 + 1

Note

The expression if x % 2 == 0: means the same thing as if x is even:.

  1. Modify the program so that it prints the collatz sequences for every number from 1 to 100.
  2. Modify your program so that it prints the number between 2 and 1000 with the longest collatz sequence.