题目
The following iterative sequence is defined for the set of positive integers:
- n → n/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.
解答
首先是定义一个函数，按照规则，数一下算到1的数目。这个本身是很简单的，但是考虑到要算的数很多，而且重复计算的很多，所以使用递归，并且缓存结果，这样会让计算变快。
def collatz(N, cache):
res = 1
if (N == 1):
return 1
if (N % 2 == 0):
x = int(N/2)
else:
x = int(3*N+1)
if cache.size <= x:
y = collatz(x, cache)
elif cache[x] == 0:
y = collatz(x, cache)
cache[x] = y
else:
y = cache[x]
return res + y
有了前面一个数的函数，就可以遍历N个数的。返回来缓存的向量。这样我们通过下标可以取任何一个计算过的数的数目。
def collatz2(N):
res = np.zeros(3*N + 2)
for i in range(1, N):
res[i] = collatz(i, res)
return res
那么答案就简单了，这个向量里哪个数目最大，对应的下标，就是相应的数字。
def solution14(N):
res = collatz2(N)
return np.argmax(res[:N])
1秒出结果。
