Project Euler Problem 14 Solution: Longest Collatz sequence

Project Euler Problem 14 Statement

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.

Solution

collatz_conjecture

The numbers in the Collatz sequence are often refered to as hailstone numbers and the algorithm to generate them is the hailstone calculator. Here is Python implementation for a fast hailstone calculator for starting numbers up to five million:

cx = [0, 1] + [0]*5000000
    def d(n):
        if n>5000000: return d((3*n + 1)//2 if n&1 else n//2) + 1
        if not cx[n]: cx[n] = d((3*n + 1)//2 if n&1 else n//2) + 1
        return cx[n]

This function is called for every number from two to five million and the path lengths placed in to the cache (cx). Two optimization have been incorporated to meet HackerRank's run time limitation.

Many paths merge with others creating a directed graph that always terminate at one (assumed, but not yet proven). A cache is checked to see if its length is there from a previous calculation.
For every odd starting number we multiply by three and add one which will be an even number. So we can combine both steps at once by calculating (3n+1)/2. This cuts the calculation time by 25%.

It became apparent, after testing many numbers, that the lengths were simply a collection of discrete points over the domain. By looking at this set, 9 has the longest chain until 18. Then 18 has the longest chain until 19, and 19 until 25. Here is the set of starting numbers that produce the longest sequence up to 5,000,000:

{1, 2, 3, 6, 7, 9, 18, 19, 25, 27, 54, 55, 73, 97, 129, 171, 231, 235, 313, 327, 649, 654, 655, 667, 703, 871, 1161, 2223, 2322, 2323, 2463, 2919, 3711, 6171, 10971, 13255, 17647, 17673, 23529, 26623, 34239, 35497, 35655, 52527, 77031, 106239, 142587, 156159, 216367, 230631, 410011, 511935, 626331, 837799, 1117065, 1126015, 1501353, 1564063, 1723519, 2298025, 3064033, 3542887, 3732423}

This set is utilized to answer the queries from the HackerRank platform quickly. It takes about 4 seconds to generate the set above.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 14

HackerRank wants the starting number, 1 ≤ N ≤ 5×10⁶ with the longest chain. Up to 10,000 starting numbers are tested.

Python Source Code

c = [1]
def collatz(_):
    cx = [0, 1] + [0] * 5000000
    def d(n):
        if n > 5000000: return d((3*n + 1)//2 if n&1 else n//2) + 1
        if not cx[n]: cx[n] = d((3*n + 1)//2 if n&1 else n//2) + 1
        return cx[n]
    m=0
    for n in range(2, 5000001):
        q = d(n)
        if q>=m: c.append(n); m=q
    return c[::-1]

c = collatz(0)
for _ in range(int(input())):
    i = int(input())
    print (min(c, key=lambda x:x>i))

Last Word

Directed graph showing the orbits of small numbers under the Collatz map.

This is a directed graph showing the orbits of small numbers from 1 to 25 under the Collatz map. As each path progresses the nodes can exceed 25 as is the case with 15. The hailstone calculator presented above looks for paths already calculated and uses that length instead of re-calculating the complete path. In this example, the longest path is 25 with 24 nodes.