Select Page

Project Euler 14 Problem Statement

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

nn/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_conjectureThe Python program listed in the Afterthoughts section shows the hailstone calculator for determining values in the Collatz chain for a number, N. The d function determines the length of the chain and the purpose of the program is to determine the longest length for a set of consecutive numbers below some limit, L. It became apparent that the lengths were simply a collection of discrete points over the domain.

So, when challenged by HackerRank Project Euler 14 with more aggressive limits (N<=5,000,000), and running ten thousand test cases in fewer than 10 seconds it became obvious that building a table was the best way to go.

There are fragments of this sequence in the OEIS but a problem was the requirement to find the maximum starting value when the same chain length is shared by other starting numbers.

For example 35497 is not found in these on-line sequences and for an N=34555 the starting number for the longest chain returned is 34239. Well it seems the 35497 shares the same number of terms and is the greater of the two. 35497 is the correct response.

This required going backwards through a range of numbers (say 107) and finding the stopping points and taking these maximums into consideration. That result is the list shown in the Python source code below.

HackerRank version

HackerRank Project Euler 14 increases the upper limit to 5,000,000 and runs 10,000 test cases.

Python 2.7 Source

Last Word

Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A006877: In the '3x+1' problem, these starting values set new maximums for number of steps to reach 1.
Simple, concise, and fast Hailstone (Collatz) generator

L = 1000000
hailstone = lambda n: 3*n + 1 if n%2 else n//2

def d(n, _={1:1}):
    if n not in _: _[n] = d(hailstone(n)) + 1
    return _[n]

print max(range(1, L), key=d)