Project Euler Problem 14 Solution

Posted by Abhi Desai on June 5, 2016

Project Euler is “a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.” A list of the problems can be found here.


Problem 14 states the following:

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)

n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?


Here’s my solution in Python:

def collatz(a): # returns length of Collatz sequence starting with 'a'
    num=1
    while a!=1:
        if a%2==0:
            a=a/2
        else:
            a=3*a+1
        num+=1
    return num

maxCollatz=0
for x in range(1,1000000):
    xCollatz=collatz(x)
    if xCollatz>maxCollatz:
        print(str(x)+":"+str(xCollatz))
        maxCollatz=xCollatz

You can run the code on repl.it.