If there’s one thing I learned from teaching, it’s that one of the most mind numbing activities is test proctoring. Most proctors aren’t allowed to use their smartphone, read a book, draw, or even sit. You are supposed to walk around and “actively proctor,” whatever that means. One of my coping tricks was to determine the collatz sequence of a random starting number, mentally.
A collatz sequence is a simple algorithm that creates a chain of numbers based on a starting ‘seed’ number. The rule is simple:
If n is even then:
n –> n/2
If n is odd then:
n –> 3n + 1
For example if you start with 5, an odd number, the next number would be
3*5 + 1 = 16
Since 16 is even, we divide it by two, so the next number is 8. So far our sequence is
5 –> 16 –> 8
Since 8 is even, we divide by two again, giving us 4. Divide that, and on and on until you reach 1. The overall sequence contains 6 numbers:
5 — > 16 –> 8 –> 4 –> 2 –> 1
This is called the collatz conjecture because it’s unproven whether or not any starting number will always reach one, like in the example above. Here is the question from Project Euler which I will try to solve.
Which starting number, under one million, produces the longest chain?
How I will approach this problem
- Write a helper function that will determine the next number in the sequence
- Write a function that will loop through every number keeping track of the number of iterations.
- Once the chain has finished, check if it has surpassed the last winner. If it has, then replace it as the current ‘leader’ .
First, the helper function to determine the next number:
def next_collatz(n) if (n%2 == 0) return n/2 else return 3*n+1 end end
Then, declare the variables to keep track of the current leader (longest)
longest = 0 counter = 1 winning_num = 0 x = 1
Construct the loop to go through all numbers less than one million
while counter < 1000000 x = counter chain = 1 while x > 1 x = next_collatz(x) chain+=1 end #print("N: ", counter, " Had a chain of: ",chain,"\n") if (chain > longest) longest = chain winning_num=counter end counter+=1 end
Print the winner!
print("longest: ",longest," winningnum: ",winning_num,"\n") #Note this is the number that produces the longest chain, not the length of chain