Project Euler 14: Find the starting number, under one million, that produces the longest Collatz sequence.

Project Euler 14 Problem Description

Project Euler 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:

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.

Analysis

The 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<=10,000,000), and running thousands of trials in fewer than 5 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 10⁷) and finding the stopping points and taking these maximums into consideration. That result is the list shown in the Python source code below.

This program and method
solves all test cases for
Project Euler 14 on HackerRank

Project Euler 14 Solution

Afterthoughts

• 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)