Project Euler -- Problem #14

I had some downtime this morning between projects. I have been working on some big projects including a new online store for work and migrating Blumetech to Amazon AWS. 

I needed a little break from my usual problem solving and instead stretch my brain a little on a Project Euler problem. 

I opted for Problem #14.

PROBLEM #14

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?

NOTE: Once the chain starts the terms are allowed to go above one million.

 

The problem looked challenging and interesting. How could every number regardless of starting point always reduce to 1?

Here is my solution written in Python:

def get_sequence(n):
    temp = n
    sequence = []
    while temp > 1:
        sequence.append(temp)
        if temp % 2 == 0:
            temp = temp / 2
        else:
            temp = (temp * 3) + 1
    sequence.append(temp)
    return sequence
    
if __name__ == "__main__":
    max_n = [0, []]
    max_range = 999999
    for n in xrange(max_range, 3, -2):
        result = get_sequence(n)
        if len(result) > len(max_n[1]):
            max_n[0] = n
            max_n[1] = result
    print ("Number: %s" % max_n[0])
    print ("Squence length: %s" % len(max_n[1]))
    print max_n[1]

The solution is simple brute force. The only optimization was skipping the even numbers. They are immediately divided by two and hence would not lead to the longest sequence.

Elapsed time was 12.4 seconds and there are 525 numbers in the sequence.

After writing the solution, I found some other interesting solutions on the web. Some of the most interesting use the imap function in itertools to reduce my for loop to a single line. I suspect that the imap approach is significantly faster.

I tested every number from 1 to 10,000,000. Sure enough all of their sequences ended in 1. That's weird. 

Here is the solution sequence displayed as a graph:

One thing to note is the two big picks. In most numbers that led to long sequences the two big peaks were present. 

FYI -- The solution for numbers under 10 Million is 8,400,511 with a sequence length of 686.