Lua Implementation of Problem 14
View source code here on GitHub!
Solution
- solution()
- Returns:
The solution to problem 14
- Return type:
number
1-- Project Euler Problem 14
2--
3-- Problem:
4--
5-- The following iterative sequence is defined for the set of positive integers:
6--
7-- n → n/2 (n is even)
8-- n → 3n + 1 (n is odd)
9--
10-- Using the rule above and starting with 13, we generate the following sequence:
11-- 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
12--
13-- It can be seen that this sequence (starting at 13 and finishing at 1) contains
14-- 10 terms. Although it has not been proved yet (Collatz Problem), it is thought
15-- that all starting numbers finish at 1.
16--
17-- Which starting number, under one million, produces the longest chain?
18--
19-- NOTE: Once the chain starts the terms are allowed to go above one million.
20
21local function collatz_len(n, cache)
22 if cache[n] then
23 return cache[n]
24 end
25
26 local result
27 if n == 1 then
28 result = 0
29 elseif n % 2 == 0 then
30 result = 1 + collatz_len(math.floor(n / 2), cache)
31 else
32 result = 2 + collatz_len(math.floor((3 * n + 1) / 2), cache)
33 end
34
35 cache[n] = result
36 return result
37end
38
39return {
40 solution = function()
41 local max_seen = 0
42 local answer = 0
43 local cache = {}
44
45 for i = 1,999999 do
46 local result = collatz_len(i, cache)
47 if result > max_seen then
48 max_seen = result
49 answer = i
50 end
51 end
52
53 return answer
54 end
55}