Problem 014
正の整数に以下の式で繰り返し生成する数列を定義する.
$ n → n/2 $ ( $ n $ が偶数)
$ n → 3n + 1 $ ( $ n $ が奇数)13からはじめるとこの数列は以下のようになる.
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
13から1まで10個の項になる. この数列はどのような数字からはじめても最終的には 1 になると考えられているが, まだそのことは証明されていない(コラッツ問題)さて, 100万未満の数字の中でどの数字からはじめれば最長の数列を生成するか.
注意: 数列の途中で100万以上になってもよい
Answer 014 (Python)
import sys
from multiprocessing import Pool
class Problem14:
CASH = {}
def main(self, n):
result = 1
num = 1
for i in range(2, n):
count = p.collatzNumCount(i)
self.CASH[i] = count
if result < count:
num = i
result = count
print(num, result)
def collatzNumCount(self, n):
i = 0
while(n != 1):
if n in self.CASH:
i += self.CASH[n]
return i
n = self.collatzNum(n)
i += 1
return i
def collatzNum(self, n):
if n % 2 == 0:
return self._collatzEven(n)
else:
return self._collatzOdd(n)
def _collatzOdd(self, n):
return 3 * n + 1
def _collatzEven(self, n):
return n / 2
if __name__ == '__main__':
num = 1000000
if len(sys.argv) == 2:
num = sys.argv[1]
p = Problem14()
p.main(int(num))
(参考) Project Euler とは
Project Euler はプログラミングで数学の問題を解くサイトです。問題は600問以上あるので、勉強に使うのも良し、楽しむのも良しです。
サイトに登録すれば、解答を submit することができ、その場であっているか判定してくれます。
また、問題だけであれば、日本語に翻訳された Wiki もあるのでそちらを見ながらやると捗ると思います。