I was watching one of my favourite youtube channels Numberphile and came across a video which for convenience i have embedded into this post on the Collatz Conjecture. The Collatz Conjecture is named for Lothar Collatz who introduced the idea in 1937. It is a simple sequence which is defined as:
f(n)=
\begin{cases}
3n+1 &\text{if } odd (n \% 2\neq0) \\
\frac{n}{2} &\text{if } even (n \% 2 = 0)
\end{cases}This may look a bit daunting at first but it simply means that if n is even (there is no remainder when n is divided by 2) divide it by 2 and if it is odd times n by 3 and add 1. Putting this in structured English gives the algorithm:
if n % 2 = 0 then
return n/2
else
return (3*n)+1
To create the sequence we plug in this new value of n back into the function for example putting 10 into the function we would get the sequence:
f(10) = [10, 5, 16, 8, 4, 2, 1]
and putting 13 into the function give the sequence:
f(13) = [13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
Now you may have noticed that we stop the sequence when we hit 1, this is because 1 is odd so (3*1)+1 = 4 and we would end up in an endless loop so we make 1 the base case of the algorithm. So the altered algorithm would be:
if n = 1 then
return 1
else if n % 2 = 0 then
return n/2
else
return (3*n)+1
The moment i watched the Youtube video i immediately thought that would make a good Python program, so I immediately came up with the program in the second part of this project.
