Project Euler problem 14

Source code available on GitHub.

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

    \begin{align*} n &\to n/2\ (n\textrm{ is even}) \\ n &\to 3n + 1\ (n\textrm{ is odd}) \end{align*}

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

    \[ 13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 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?  \footnotesize \textbf{NOTE:} Once the chain starts the terms are allowed to go above one million.

This is a really interesting problem. Before even thinking about what we’re going to have to do later on, let’s just make a quick function to determine the next number in a Collatz sequence:

def nextCollatz(n):
    if n % 2 == 0:
        return int(n/2)
    else:
        return 3*n+1

This quite literally is nothing more than the rule given in the question. Next, we want to generate the whole sequence given a particular starting number:

def CollatzSequence(n):
    sequence = [n]
    while True:
        n = nextCollatz(n)
        sequence.append(n)
        if n == 1:
            break
    return sequence

We’re just appending the next term (using the function nextCollatz(n) we just defined) endlessly until we reach 1, and then we return that whole list.

Now we have to find which starting number under a million produces the longest chain. Starting at 999,999 and decreasing the starting number each time rather than the other way round, because it seems plausible that a higher starting number will result in longer sequences on average, we keep calculating the length of each Collatz sequence and if it’s longer than the longest so far, we store both the starting number and the sequence length:

def longestCollatz(cap): # Returns the number below 'cap' which generates the longest Collatz sequence, and its length
    longest = 0
    for i in range(cap-1,1,-1):
        length = len(CollatzSequence(i))
        if length > longest:
            longest = length
            longestAt = i
    return longestAt

That’s all there is to it: we print off the answer and we’re done.

def nextCollatz(n):
    if n % 2 == 0:
        return int(n/2)
    else:
        return 3*n+1

def CollatzSequence(n):
    sequence = [n]
    while True:
        n = nextCollatz(n)
        sequence.append(n)
        if n == 1:
            break
    return sequence

def longestCollatz(cap): # Returns the number below 'cap' which generates the longest Collatz sequence, and its length
    longest = 0
    for i in range(cap-1,1,-1):
        length = len(CollatzSequence(i))
        if length > longest:
            longest = length
            longestAt = i
    return longestAt

print(longestCollatz(1000000))

Leave a Reply

Your email address will not be published. Required fields are marked *