Project Euler - Problem 55

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

出典： Project Euler（日本語 翻訳サイト）
　　　ProjectEuler.net（英語サイト）

Problem 55
47とその反転を足し合わせると, 47 + 74 = 121となり, 回文数になる.

全ての数が素早く回文数になるわけではない. 349を考えよう,
 1.349 + 943 = 1292
 2.1292 + 2921 = 4213
 3.4213 + 3124 = 7337
349は 3回の操作を経て回文数になる.

まだ証明はされていないが,
196のようないくつかの数字は回文数にならないと考えられている.
反転したものを足すという操作を経ても回文数にならないものを
Lychrel数と呼ぶ.
先のような数の理論的な性質により, またこの問題の目的のために,
Lychrel数で無いと証明されていない数はLychrel数だと仮定する.

更に, 10000未満の数については，常に以下のどちらか一方が成り立つと仮定してよい.
 1.50回未満の操作で回文数になる
 2.まだ誰も回文数まで到達していない

実際, 10677が50回以上の操作を必要とする最初の数である:
4668731596684224866951378664 (53回の操作で28桁のこの回文数になる).
驚くべきことに, 回文数かつLychrel数であるものが存在する. 最初の数は4994である.
10000未満のLychrel数の個数を答えよ.

注: 2007/04/24にLychrel数の理論的な性質を強調するために文面が修正された.

－－－－－


私の解答例は以下です。畳んでいます。

def g(n):
	s = str(n)
	for i in xrange(len(s)//2):
		if s[i]!=s[-(i+1)]: return False
	return True

def f(n):
	L = []
	for i in xrange(n):
		s = i
		for j in xrange(50):
			s += int("".join(list(str(s))[::-1]))
			if g(s): break
		else: L.append(i)
	return L

n = 10000
L = f(n)
print len(L)

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

１．関数g(n):
・回文数かどうかチェックします。
・s = str(n)
　引数nを文字型に変換し、文字列sとします。

・for i in xrange(len(s)//2):
　ループ変数iは、文字列sの真ん中まで、位置番号を1つずつ設定します。
　文字列sが奇数桁の場合、真ん中の文字はチェック対象外です。
　len関数で文字列sの長さを取得し、//演算子で割り算の商を求めています。

・if s[i]!=s[-(i+1)]: return False
　文字列sの前からi番目の文字と後ろからi番目の文字を比べ、
　違っていたらFalseを返し、同じならば位置iを1つ進めます。

・return True
　上記でFalseでループを抜けなかったので、前からと後ろからの同じ位置の文字がすべて同じで回文数なので、Trueを返します。

２．関数f(n)
　n未満のLychrel数のリストを返します。
・for i in xrange(n):
　ループ変数iには0から引数nまでの値を1つずつ設定します。

・for j in xrange(50):
　50回を限度に、以下の反転数累積とその回文数チェックをします。

・s += int("".join(list(str(s))[::-1]))
　数値sをstr関数で文字型にして、list関数で1文字ずつのリストにして、[::-1]で反転します。
　"".joinでその反転リストを結合して反転数文字列にして、int関数で数値に直して元の反転前の値に累積していきます。
リスト[開始位置:終了位置:刻み]なので、リスト[::-1]で反転リストになります。
・if g(s): break
　上記で計算した反転数累積値について、関数gにて回文数チェックをします。
　回文数ならば、問題に合わないのでループ変数iを次に進めます。

・else: L.append(i)
　for文のelse節は、forループが途中抜けせず最後まで回って要素が尽きた場合に処理します。
　ここでelse節に入るには、反転数累積を50回やっても1つも回文数にならなかったということで、まさにLychrel数なので、このようなiはリストLに追加します。

３．関数の外
・n=10000
　L = f(n)
　print len(L)
　問題に合うように10000未満の数値を対象にして、
　関数fで問題に合う数値のリストを取得し、len関数でその件数を取得し、表示します。
　

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