プロジェクトオイラー 問５７

プロジェクトオイラーの問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索してください。

問５７「2の平方根の連分数展開を調べあげよ」
2の平方根は無限に続く連分数で表すことができる.
 √ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...
最初の4回の繰り返しを展開すると以下が得られる.
1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...
次の3つの項は99/70, 239/169, 577/408である.
第8項は1393/985である.
これは分子の桁数が分母の桁数を超える最初の例である.

最初の1000項を考えたとき, 分子の桁数が分母の桁数を超える項はいくつか?

－－－－－


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






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

def g(n):
	if n<1: return 1, 1
	a, b = g(n-1)
	return a+b*2, a+b

def f(n):
	import sys
	sys.setrecursionlimit(n+10)
	u = 0
	for i in xrange(n+1):
		a, b = g(i)
		if len(str(a))>len(str(b)): u += 1
	return u

n =1000
print f(n)

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

１．関数g(n)
・問題文の第n項の値を、分子と分母で返します。
・問題文から、
　L1 = 1 + 1/2
　L2 = 1 + 1/(2 + 1/2)
　L3 = 1 + 1/(2 + 1/(2 + 1/2))
　L4 = 1 + 1/(2 + 1/(2 + 1/(2 + 1/2)))
　・・・

「1+(1/x)」のxの部分に1世代前の値が入るようにして再帰関数を作ります。
　L0 = 1
　L1 = 1 + 1/2 ... (A)
　　 = 1 + 1/(1 + L0)
　　
　L2 = 1 + 1/(2      + 1/2)
　　 = 1 + 1/(1 + (1 + 1/2)) ...(B)
　　 = 1 + 1/(1 +  L1)
　　
　L3 = 1 + 1/(2      + 1/(2      + 1/2))
　　 = 1 + 1/(1 + (1 + 1/(1 + (1 + 1/2))))...(C)
　　 = 1 + 1/(1 + L2)

・・・というようになります。
ポイントは、各世代の第1項が1なので入れ子になる「1+(1/x)」のx自身も第1項は1からはじめることです。
問題文ではこの部分は2なので1+1に分けて式変形します。
(B)全体を「1+(1/x)」と見ると、そのxの部分が「1+(A)」です。
(C)全体を「1+(1/x)」と見ると、そのxの部分が「1+(B)」です。

次に、1世代前の値の分母子から、当世代の値の分母子を求めておきます。
1世代前の値がa/b、つまり分子a、分母bだとすると、当世代の値は、
　　1 + 1 / (1 + a/b)　 かっこ内を分母bで通分して、
　= 1 + 1 / ((a+b) / b)　第2項の分母子をb倍して、
　= 1 + (b / (a+b))　　　全体を分母(a+b)で通分して、
　= ((a+b) + b) / (a+b)　整理して
　= (a+b*2) / (a+b)　　　以上より、分子a+b*2、分母a+b　になります。
　
以上をふまえて、
・if n<1: return 1, 1
　g(n)は１世代前の自分自身を呼び出す再帰関数なので、
　世代さかのぼりの終了条件として、nが1より小さくなったら、
　L0 = 1/1 で、分子1、分母1を返し、さかのぼりは終了します。

・a, b = g(n-1)
　1世代前の分子a、分母bを受け取ります。
　
・return a+b*2, a+b
　当世代の分子a+b*2、分母a+bを返します。

２．関数f(n)
・問題文に合う最初のn項までのうち、
　分子の桁数が分母の桁数を超える場合の件数を返します。

・import sys
　sys.setrecursionlimit(n+10)
　再帰呼び出しの深さの限界値を設定します。
　初期値は1000なので当問題では足りません。
　限界を超えたときのエラーメッセージは以下のとおりです。
　「RuntimeError: maximum recursion depth exceeded」
　ここでは上記エラーが発生しないように、
　引数nに余裕をもたせた値を再帰呼び出し深さ限界値として設定しています。
　
・u = 0
　求める件数のカウンターです。0クリアしておきます。

・for i in xrange(n+1):
　問題文にある項番号をループ変数iとして設定します。

・a, b = g(i)
　当世代の分子、分母をそれぞれa、bとして取得します。

・if len(str(a))>len(str(b)): u += 1
　分子a、分母bをそれぞれstr関数で文字型にしてlen関数で文字列長（桁数）を取得し、
　分子の桁数が分母の桁数を超える場合に、カウントアップします。

３．関数の外
・n =1000
　print f(n)
　問題に合うように引数1000を関数fに渡し、戻り値を表示します。
　

なお、関数g(n)の返り値の分子分母はその桁数違いを判定するので、
公約数が存在すのであれば約分して最も簡単な分数にしておく必要があります。
そこでこの分子分母に公約数が無いことを確認をしておきます。

まず、第1項のa=3,b=2には明らかに公約数が存在しません。
次に、
第n-1項の分子分母a,bに公約数が存在しない条件のもと、
第n項の分子分母a+b*2, a+bに公約数pが存在すると仮定すると、
公約数pを使用して、それぞれ以下のように表せます。
a+b*2 = pm ...(1)
a+b = pn ...(2)
ここで、
(1)-(2)より、
(a+b*2) - (a+b) = pm - pn
　b = p(m-n) ...(3)
(2)*2-(1)より、
(a+b)*2 - (a+b*2) = 2*pn - pm
　a = p(2*n-m) ...(4)
となって、(3)(4)よりa,bにも公約数pが存在することになり、
a,bに公約数が存在しないという条件と矛盾します。
以上より、a+b*2,a+bには公約数が存在しません。

なので、関数g(n)の返り値はそのまま桁数判定に使っています。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
153
（追記）
・20130129　ネタバレ注意の追記など