プロジェクトオイラー
http://projecteuler.net/index.php
Q159.
自然数の各桁の和をとり、さらにそれが1桁になるまでそれを繰り返す。この値をDRと呼ぶ。例えば、467→17→8。自然数nを積の形に書いて、その因子のDRの合計の最大をmdrs(n)とする。1 < n < 1000000でのmdrs(n)の合計。
mdrs(n)を計算するのではなく、積の形を生成する。10未満ならこうなる。
[2] [2, 2] [2, 2, 2] [2, 3] [2, 4] [3] [3, 3] [4] [5] [6] [7] [8] [9]
実際には、積とDRの総和のタプルを生成して、0に初期化したmdrs[n]と大小比較して大きいほうを代入していく。
と、最初やっていたが、実際には、mdrsを順番に計算し、nを2つに分けてmdrs[d] + mdrs[n/d]の最大を計算したほうが速かった。キャッシュを効かせれば上の方法のほうが速くなるかもしれない。
from math import sqrtdef calc_mdrs(n):
mx = drs(n)
for d in xrange(2, int(sqrt(n + 0.5)) + 1):
if n % d == 0:
mx = max(mx, mdrs[d] + mdrs[n/d])
mdrs[n] = mxdef drs(n):
s = n % 10
while n >= 10:
n /= 10
s += n % 10
if s < 10:
return s
else:
return drs(s)N = 10 ** 6
mdrs = [ 0 ] * N
for n in xrange(2, N):
calc_mdrs(n)
print sum(mdrs)
