## 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` → 3`n` + 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 presented by other Project Euler 14 problems hosted on other sites, 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^{7}) and finding the stopping points and taking these maximums into consideration. That result is the list shown in the Python source code below.

#### Project Euler 14 Solution

Runs < 0.001 seconds in Python 2.7.```
c = [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, 5649499, 6649279, 8400511, 11200681]
L = 1000000
print min(c[::-1], key=lambda x: x>L)
```

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

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose*define*to reveal the answer.

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

*Project Euler 14 Solution last updated*

Very nice your site

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 ?

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!