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