2016年2月29日月曜日

プロジェクトオイラー 問119

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。


問119「数字べき乗和」
512 という数は興味深い数である.
というのも, 各桁の和を何乗かしたものに等しくなっているからである:
5 + 1 + 2 = 8, 83 = 512 である.

この特性を持つ他の数は例えば 614656 = 284である.
この数列の第 n 項を an と定義し, また 2 桁以上であるとしよう.
a2 = 512, a10 = 614656 となる.
a30 を求めよ.



注意!!!
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。




私の回答例は以下の通りです。
def f(n):
 c = 0
 for d in xrange(2, n+2):
  for i in xrange(d, 9*d+1):
   for j in xrange(2, d+1):
    a = i**j
    t = [int(k) for k in str(a)]
    if d==len(t) and i==sum(t):
     c += 1
     if c==n: return a, i, j
    
n = 30
s, i, j = f(n)
print s,"( =", i, "**", j, ")"


小さい数値から順に各桁を和を累乗して元の数になるかチェックすると、
とても1分ルールに間に合いません。
そこで、べき乗した数値を順に用意して元の数との桁数一致と各桁和をチェックします。


1.関数f(n)
・問題の数列の第n項の値を返します。
 数列aの第1項から順にチェックして第n項を検出したときに処理を終了します。


・for d in xrange(2, n+2):
 ループ変数dは求める値の桁数です。
 取り得る値の範囲は、2桁以上で、第n項ではたかだかn+1桁です。


・for i in xrange(d, 9*d+1):
 ループ変数iは、求める値a=i**jのときのiであり、また題意によりaの桁数和でもあります。
 取り得る値の範囲はaが全桁1の数値ならばd、全桁9の数値ならば9*dなのでこの間です。


・for j in xrange(2, d+1):
 ループ変数jは求める値a=i**jのときのj、べき乗です。
 取り得る値の範囲は2乗以上なので最低2、べき乗数はたかだかaの全体桁数以内です。


・a = i**j
 t = [int(k) for k in str(a)]
 aは候補の値で、tは候補aの各桁の値リスト


・if d==len(t) and i==sum(t):
 桁数一致、かつ元の数字=数字のべき乗の桁数和が一致するかをチェックし、
 成り立てば件数カウンタcを+1し、その件数が限度nになれば終了です。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
248155780267521 ( = 63 ** 8 )