The following iterative sequence is defined for the set of positive integers:
Using the rule above and starting with \(13\), we generate the following sequence: \[13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 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.
We'll need to check every term between one to one million, but we can save some time with memoization. Suppose we've already made the sequence shown in the example, and now we want to find the length of the chain starting with \(80\). Then the second term is \(40\), and we've seen that the chain starting with \(40\) has \(9\) terms; therefore, the chain starting with \(80\) contains \(10\) terms, and we didn't even need to recalculate the last \(8\) of them. Whenever my code generates a new chain, it stores the chain length for each of its elements to avoid unnecessary recomputation.
def p14(cap = 1000000):
chainlens = [0 for i in range(cap)]
chainlens[1] = 1
maxlen, res = 0, 0
for i in range(2, cap):
if chainlens[i] != 0: # found this i in a previous chain
continue
chain = [i]
while chain[-1] >= cap or chainlens[chain[-1]] == 0:
if chain[-1] % 2 == 0:
chain.append(chain[-1] // 2)
else:
chain.append(3 * chain[-1] + 1)
L = chainlens[chain[-1]]
for j in range(len(chain) - 1):
if chain[j] < cap:
chainlens[chain[j]] = L + len(chain) - 1 - j
if chainlens[chain[j]] > maxlen:
maxlen = chainlens[chain[j]]
res = chain[j]
return res