# The “Half Or Triple Plus One” algorithm

• Take the natural number $n$.
• If $n$ is even: divide it by 2 to get $\frac{n}{2}$.
• If $n$ is odd: multiply it by 3 and add 1 to obtain $3n+1$.
• Repeat the process indefinitely

# 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

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.