// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (12 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 14 Solution

Project Euler 14 Solution

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

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<=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.

Project Euler 14
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.
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)
download arrowUse 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.
|837799|

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”

  1. 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 ?

    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

Post a comment