|
1
|
|
|
""" |
|
2
|
|
|
Project Euler Problem 14: Longest Collatz Sequence |
|
3
|
|
|
================================================== |
|
4
|
|
|
|
|
5
|
|
|
.. module:: solutions.problem14 |
|
6
|
|
|
:synopsis: My solution to problem #14. |
|
7
|
|
|
|
|
8
|
|
|
The source code for this problem can be |
|
9
|
|
|
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem14.py>`_. |
|
10
|
|
|
|
|
11
|
|
|
Problem Statement |
|
12
|
|
|
################# |
|
13
|
|
|
|
|
14
|
|
|
The following iterative sequence is defined for the set of positive integers: |
|
15
|
|
|
|
|
16
|
|
|
.. math:: |
|
17
|
|
|
|
|
18
|
|
|
n &\\rightarrow \\frac{n}{2} \\; \\; \\; & \\mbox{(n is even)} \\\\ |
|
19
|
|
|
n &\\rightarrow 3n + 1 \\; \\; \\; & \\mbox{(n is odd)} |
|
20
|
|
|
|
|
21
|
|
|
Using the rule above and starting with :math:`13`, we generate the following sequence: |
|
22
|
|
|
:math:`13 \\rightarrow 40 \\rightarrow 20 \\rightarrow 10 \\rightarrow 5 \\rightarrow 16 \\rightarrow 8` |
|
|
|
|
|
|
23
|
|
|
:math:`\\rightarrow 4 \\rightarrow 2 \\rightarrow 1` |
|
24
|
|
|
|
|
25
|
|
|
It can be seen that this sequence (starting at :math:`13` and finishing at :math:`1`) contains :math:`10` terms. |
|
|
|
|
|
|
26
|
|
|
Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at :math:`1`. |
|
|
|
|
|
|
27
|
|
|
|
|
28
|
|
|
Which starting number, under one million, produces the longest chain? |
|
29
|
|
|
|
|
30
|
|
|
.. note:: once the chain starts the terms are allowed to go above one million. |
|
31
|
|
|
|
|
32
|
|
|
Solution Discussion |
|
33
|
|
|
################### |
|
34
|
|
|
|
|
35
|
|
|
This solution simply uses an exhaust coupled with memoisation to avoid re-computing the same value over and over. |
|
|
|
|
|
|
36
|
|
|
|
|
37
|
|
|
The search space is iterated, and any partial results (that may form the tail of subsequent sequences) will be cached |
|
|
|
|
|
|
38
|
|
|
along with the associated chain length. |
|
39
|
|
|
|
|
40
|
|
|
Upon completion, search for the largest chain. |
|
41
|
|
|
|
|
42
|
|
|
Solution Implementation |
|
43
|
|
|
####################### |
|
44
|
|
|
|
|
45
|
|
|
.. literalinclude:: ../../solutions/problem14.py |
|
46
|
|
|
:language: python |
|
47
|
|
|
:lines: 50- |
|
48
|
|
|
""" |
|
49
|
|
|
|
|
50
|
|
|
from typing import Dict |
|
51
|
|
|
|
|
52
|
|
|
from lib.numbertheory import is_even |
|
53
|
|
|
|
|
54
|
|
|
|
|
55
|
|
|
def collatz(n: int, d: Dict[int, int]) -> int: |
|
|
|
|
|
|
56
|
|
|
""" Compute the Collatz sequence starting at :math:`n` |
|
57
|
|
|
|
|
58
|
|
|
The length of a Collatz sequence starting at :math:`n` can be computed by iterating the Collatz map until it reaches |
|
|
|
|
|
|
59
|
|
|
:math:`1`. While this would be sensible for a single :math:`n`, performing this for many values of :math:`n` will |
|
|
|
|
|
|
60
|
|
|
result in a lot of redundant calculations. |
|
61
|
|
|
|
|
62
|
|
|
Consider the following two overlapping Collatz sequence: |
|
63
|
|
|
|
|
64
|
|
|
.. math:: |
|
65
|
|
|
|
|
66
|
|
|
64 \\rightarrow 32 \\rightarrow 16 \\rightarrow 8 \\rightarrow 4 \\rightarrow 2 \\rightarrow 1 \\\\ |
|
|
|
|
|
|
67
|
|
|
10 \\rightarrow 5 \\rightarrow 16 \\rightarrow 8 \\rightarrow 4 \\rightarrow 2 \\rightarrow 1 |
|
|
|
|
|
|
68
|
|
|
|
|
69
|
|
|
Observe the coalescence of these two sequences when they both reach the value :math:`16`. These two sequences |
|
|
|
|
|
|
70
|
|
|
provide the lengths of Collatz sequences starting at: :math:`1,2,4,5,8,10,16,32` and :math:`64`. |
|
71
|
|
|
|
|
72
|
|
|
By caching all results as we go we can avoid re-computing the tail of any coalescing sequences. |
|
73
|
|
|
|
|
74
|
|
|
:param n: the start of the Collatz sequence |
|
75
|
|
|
:param d: a dictionary of existing solutions |
|
76
|
|
|
:return: the length of the Collatz sequence starting at :math:`n` |
|
77
|
|
|
|
|
78
|
|
|
.. note:: the dictionary :math:`d` will be updated with any partial results computed. |
|
79
|
|
|
""" |
|
80
|
|
|
|
|
81
|
|
|
try: |
|
82
|
|
|
return d[n] |
|
83
|
|
|
except KeyError: |
|
84
|
|
|
if is_even(n): |
|
85
|
|
|
d[n] = 1 + collatz(n // 2, d) |
|
86
|
|
|
else: |
|
87
|
|
|
d[n] = 1 + collatz(3 * n + 1, d) |
|
88
|
|
|
return d[n] |
|
89
|
|
|
|
|
90
|
|
|
|
|
91
|
|
|
def solve(): |
|
92
|
|
|
""" Compute the answer to Project Euler's problem #14 """ |
|
93
|
|
|
|
|
94
|
|
|
upper_bound = 1000000 # search limit |
|
95
|
|
|
|
|
96
|
|
|
# Apply the recursive to find the maximal length chain |
|
97
|
|
|
d = {1: 1} |
|
|
|
|
|
|
98
|
|
|
for i in range(1, upper_bound, 1): |
|
99
|
|
|
collatz(i, d) |
|
100
|
|
|
|
|
101
|
|
|
# Identify the largest chain |
|
102
|
|
|
v = list(d.values()) |
|
|
|
|
|
|
103
|
|
|
k = list(d.keys()) |
|
104
|
|
|
answer = k[v.index(max(v))] |
|
105
|
|
|
|
|
106
|
|
|
return answer |
|
107
|
|
|
|
|
108
|
|
|
|
|
109
|
|
|
expected_answer = 837799 |
|
|
|
|
|
|
110
|
|
|
|
Loading history...
This check looks for lines that are too long. You can specify the maximum line length.