プロジェクトオイラー Problem26

「プロジェクト　オイラー」の問題をpythonでやってみます。

出典： Project Euler （日本語翻訳サイト）
参考： サイエンスもの置き場　プロジェクトオイラーを遊び倒すガイド（初級編）

Problem 26
単位分数とは分子が1の分数である。
分母が2から10の単位分数を10進数で表記すると次のようになる。
1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1
0.1(6)は 0.166666... という数字であり、1桁の循環節を持つ。
1/7 の循環節は6桁ある。
d < 1000 なる 1/d の中で循環節が最も長くなるような d を求めよ。


私の解答例は以下です。
－－－－－

def f(n):
	L = [0, 0]
	for d in xrange(1, n):
		a, M = 1, []
		while True:
			a, b = divmod(a, d)
			if not b:
				t = 0
				break
			elif b in M:
				u = M.index(b)
				t = len(M)-u
				break
			else:
				M.append(b)
				a = b*10
		if L[1]<t: L = [d, t]
	return L
	
d, t = f(1000)
print "d =", d, ", digit of recurring cycle =", t

－－－－－

１．関数f(n)
・n未満の正の整数dについて、1/dの小数部の循環桁数が最長であるd、およびそのときの循環桁数をリストにして返却します。
・やり方は割り算の筆算の要領で、余りが0か過去にでた同じ余りの値になるまで、余りの値の右に0を付加（余りの値を10倍）して割り算を続けるという方法です。

・L = [0, 0]
　上記の返却リストの初期化です。0クリアしておきます。
・for d in xrange(1, n):
　ループ変数dは、n未満の正の整数です。
・a, M = 1, []
　筆算の要領で1桁ずつ割り算していきます。
　aはそのときの割られる数、リストMはそのときの余りを貯めます。
　初期値はそれぞれ、1と空のリストです。
・while True:
　無限ループです。1/dは無限小数ではなく、割り切れるか循環小数かが確定するまで、割り算の筆算の要領で処理を続けます。
・a, b = divmod(a, d)
　divmod関数は割り算の商と余りを同時に返します。a÷dの商がaで、余りがbです。

・if not b:
　論理式では0以外はTrueです。Falseということは余りbが0、つまり割り切れたので循環小数桁数は0です。
　ループ終了で次のn未満の正の整数の処理へ進みます。
・elif b in M:
　 u = M.index(b)
　 d = len(M)-u
　余りbが余りリストMにあるので、今後は同じ割り算を繰り返すことになり循環小数の循環部分が一周しました。
　余りbが、余りリストMの何番目かを求めて、uとします。
　u番目よりも前は循環部分より前の固定値なので、ここまでの割り算回数（余りの個数）から差し引いて循環小数桁数を求めます。
　こうしてループ終了で次のn未満の正の整数の処理へ進みます。
・else:
　 M.append(b)
　 a = b*10
　上記の２つのケース以外は、循環小数かどうか未定です。割り算をもう1桁進めます。
　まず、余りbを、余りリストに追加します。
　そして、余りbを10倍して次の割られる数とします。
　割り算の筆算で余りの数字の右に0を書き足して割り算を続けるのと同じです。

・if L[1]<t: L = [d, t]
　循環小数桁数が今までの値を超えたら、分母の数字とその循環小数桁数をリストLに差し替えます。
・指定した範囲の1/nをすべて処理し、結果リストLを戻します。

２．関数の外
・上記の関数fに指定の値1000を渡せば、[解答の分母, その循環桁数]のリストが求められます。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
d = 983 , digit of recurring cycle = 982

（追記）
・20120715
　ソースコード部分にSyntaxHighlighterを導入。