(14 votes, average: 5.00 out of 5)

## 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:

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.

#### 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 107) 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

Runs < 0.001 seconds in Python 2.7.

Use this link to get the Project Euler 14 Solution Python 2.7 source.

#### Afterthoughts

```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)
```
Project Euler 14 Solution last updated

## Discussion

### 2 Responses to “Project Euler 14 Solution”

However, for your solution for problem euler 14 you wrote :
“We proved empirically that the chain length of odd starting numbers was always equal to or larger than the previous even starting number”

See this :
for n in range(2000,2052):print(n,chain(n))

2000 113
2001 51
2002 144
2003 144
2004 113
2005 113
2006 43
2007 43
2008 69
2009 25
2010 69
2011 43
2012 69
2013 69
2014 95
2015 95
2016 113
2017 69
What evidence ?

Posted by guy | August 26, 2016, 8:16 AM
• Damn. Great question. I spent an hour trying to figure out what the hell I meant and just decided to rewrite the whole post.

Even more puzzling is why did it matter? I blame an intern. Case solved.

Happy Halloween!

Posted by Mike Molony | October 31, 2016, 5:03 PM