プロジェクトオイラー 問１１９

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

問１１９「数字べき乗和」
512 という数は興味深い数である.
というのも, 各桁の和を何乗かしたものに等しくなっているからである:
5 + 1 + 2 = 8, 8³ = 512 である.
この特性を持つ他の数は例えば 614656 = 28⁴である.
この数列の第 n 項を a_n と定義し, また 2 桁以上であるとしよう.
a₂ = 512, a₁₀ = 614656 となる.
a₃₀ を求めよ.


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



私の回答例は以下の通りです。

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, ")"

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

１．関数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 )

プロジェクトオイラー 問１１８

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

問１１８「パンデジタル素数集合」
1 から 9 の全ての数字を使い, 自由につなげることで 10 進数の数字を作り,複数の集合を作ることができる.
集合 {2,5,47,89,631} は面白いことに全ての要素が素数である.
1 から 9 の数字をちょうど 1 個ずつ含み, 素数の要素しか含まない集合はいくつあるか?



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



私の回答例は以下の通りです。

def h(n):
 if n<2: return 0
 if n<4: return n
 if (not n%2): return 0
 for i in xrange(3, int(n**.5)+1, 2):
  if not n%i: return 0
 return n

def f(L, Lc=[], d=0, cnt=0):
 if d==9:
  return [], cnt+1
 bk = Lc[:]
 for i in xrange(len(L)):
  Lc = bk[:]
  s = 0
  for j in L[i:]: s = s*10 + j

  if Lc and Lc[0]<s: continue
  if h(s):
   Lc.insert(0, s)
   Lc, cnt = f(L[:i], Lc, d+len(L)-i, cnt)
  return Lc, cnt

import itertools
L0 = [i for i in xrange(1, 10)]
v = 0
for t in itertools.permutations(L0):
 L, c = f(t)
 v += c
print "cnt:", v

1から9までの数字の順列を発生させ、その１つひとつについて、素数だけの要素に分解していきます。
ただし、その分解できた要素の順番が異なっていても１つとして数えるため、要素が昇順に並んでいるパターンだけの件数を数えます。
総当たりですが１分ルールは守れるのでよしとします。

１．関数f(n)
・リストLの要素を左から素数で区切り、累積用リストLcに格納していきます。
　dは確定した全要素の合計桁数で、cntは全素数要素のパターン数です。
　最終的に必要な値は件数だけですが、この関数を回帰呼び出しで使えるようにするために、戻り値は累積用リストLcと求める件数とします。

・回帰呼び出しなので、最初は終了条件の記述が鉄則です。
　確定した全要素の合計桁数が9ならば、1～9の数字の全部を使い切っていて、累積用リストLcに求めるパターンが格納されているので、空の累積用リストとカウンタcntを+1して戻ります。

・累積用リストLcのバックアップを取ります。
　左から1桁ずつ区切って要素を確定していく中で、区切り方が条件に合わない場合に直前状態に戻すためです。

・for j in L[i:]: s = s*10 + j
　位置iから右側を切り取り L[i:]とし、
　jのforループ中で、1けたずつ取り出して10倍しながら足していき数値化しsとします。

・if Lc and Lc[0]<s: continue
　重複を避けるため、全要素が昇順になる場合だけ採用し、それ以外は次へ。

・if h(s):
　　Lc.insert(0, s)
　　Lc, cnt = f(L[:i], Lc, d+len(L)-i, cnt)
　関数hで数値sの素数判定します。
　素数ならば、累積用リストLcに右から追加します。
　そしてリストLの位置iから左側L[:i]について、当関数fを再起呼び出しして、さらに素数の要素があるか探索します。
　 
２．関数h(n)・問１１１の素数判定を改良しました。
　2未満に素数は無く、2と3は素数。ここまではif文で直接判定します。
　その後は偶数を外し、3から先の奇数の倍数を外します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
44680