2012年8月19日日曜日

Project Euler - Probrem 49

Project Euler(プロジェクト オイラー)の問題をpythonでやってみます。

出典: Project Euler(日本語 翻訳サイト)
   ProjectEuler.net(英語サイト)

Problem 49
項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ。

  • (i)3つの項はそれぞれ素数である。
  • (ii)各項は他の項の置換で表される。
1, 2, 3桁の素数にはこのような性質を持った数列は存在しないが、4桁の増加列にはもう1つ存在する。
それではこの数列の3つの項を連結した12桁の数を求めよ。


-----

私の解答例は以下です。畳んでいます。
def p(n):
	L = [0,0]+[1]*(n-1)
 i = 2 while i*i<=n: while not L[i]: i += 1 for j in xrange(i+i, n+1, i): L[j] = 0 i += 1 return [i for i in xrange(n+1) if L[i]] def f(n): import itertools A = [] P = [i for i in p(10**n) if len(str(i))==n] for i in P: L = set(["".join(j) for j in itertools.permutations(str(i), n)]) M = sorted([int(j) for j in L if int(j) in P]) for j in xrange(len(M)-1): for k in xrange(j+2, len(M)): s, t = divmod(M[j]+M[k], 2) if (not t) and (s in M): v = int(str(M[j])+str(s)+str(M[k])) if v not in A: A.append(v) break return A L = f(4) for s in L: if s!=148748178147: print s


2つの関数を使っています。

1.関数p(n)
・n以下の素数リストを返します。problem37と同じです。

2.関数f(n)
・import itertools
 pythonの標準モジュール「itertools」をインポートします。

・A = []
 P = [i for i in p(10**n) if len(str(i))==n]
 初期設定です。
 戻り値用リストAは空リストです。
 リストPは、n桁の素数のリストです。
 内包表記です。
 **演算子は累乗で、10**nでn桁の最大値+1になります。
 まずfor文で0からn桁の最大値を1つずつループ変数iとします。
 次に後ろのif文へiを渡し、str関数で文字型にしてlen関数で文字列長を取得しこれがnの場合に限り、for文の前に渡し、そのままリストにためます。

・for i in P:
 n桁素数リストPから1つずつループ変数iとします。

・L = set(["".join(j) for j in itertools.permutations(str(i), n)])
 リストLは、素数iの構成数字を並び替えた値のリストです。
 標準モジュールitertoolsの関数permutations(t, n)は、文字列tの構成文字列から繰り返しを許さずにn個を選んで組にして返します。
 例えば、t="13",n=2ならば、("1","3")("3","1")を返します。

 ここでは、str関数で文字型にした素数iから
 n桁の「繰り返しを許さない順列タプル」を生成し、
 for文で1つずつループ変数jとして、
 このタプルjを区切り文字無しで連結してリストLにためます。
 例の場合、["13", "31"]となります。

・M = sorted([int(j) for j in L if int(j) in P])
 リストMは、素数iの構成数字を並び替えてさらに素数だった値のリストです。
 内包表記です。
 まずfor文で上記リストLから1つ取り出して要素jとします。
 そして後ろのif文へ渡し、int関数で数値にしたあと素数表Pにあるか判定し、素数の場合、for文の前に渡し、int関数で数値型にしてリストにためます。
 後で差を見るのでsorted関数で小さい順に並べなおしておきます。

・for j in xrange(len(M)-1):
  for k in xrange(j+2, len(M)):
 ループ変数jは求める等差数列のうち最小値に相当する値の、リストMでの位置です。
 ループ変数kは求める等差数列のうち最大値に相当する値の、リストMでの位置です。
 つまり、3項の等差数列の最小値と最大値の候補を、M[j]とM[k]とします。

・s, t = divmod(M[j]+M[k], 2)
 divmod関数は第1引数÷第2引数を計算し、整数の商と余りのタプルを返します。
 ここでは(M[j]+M[k])÷2の商と余りを計算し、それぞれs,tとします。
 商sは3項の等差数列の2番目の項、余りtは商sが整数として存在すれば余り0(論理的にFalse)になります。

・if (not t) and (s in M):
  v = int(str(M[j])+str(s)+str(M[k]))
  if v not in A: A.append(v)
  break
 (not t)で上記sが整数として存在し、(s in M)で上記sがリストMにあることをチェックします。
 このような条件が満たされる場合、3項の等差数列が存在することになるので、問題に合うように3項の値を文字型にして小さい順に連結しvとします。
 上記vが戻り値用リストAに無ければ追加します。

・return A
 このようにしてたまった戻り値リストAを呼び出し元に返します。

3.関数の外
・L = f(4)
 for s in L:
  if s!=148748178147: print s
 問題に合う関数fの戻り値を受け取り、さらに「148748178147」以外の値を表示します。
 


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

0 件のコメント:

コメントを投稿