プロジェクトオイラー Problem14

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

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

Problem 14
正の整数に以下の式で繰り返し生成する数列を定義する。
n → n/2 (n が偶数)
n → 3n + 1 (n が奇数)

13からはじめるとこの数列は以下のようになる。
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

13から1まで10個の項になる。
この数列はどのような数字からはじめても最終的には 1 になると考えられているが、まだそのことは証明されていない(コラッツ問題)
さて、100万未満の数字の中でどの数字からはじめれば一番長い数列を生成するか。

注意: 数列の途中で100万以上になってもよい


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

def g(n, i=1):
	if n==1: return i
	if n%2: return g(n*3+1, i+1)
	else: return g(n/2, i+1)
	
def f(n):
	a = b = 0
	for i in xrange(n-(1-n%2), n/3, -2):
		j = g(i)
		if b<j: a, b = i, j
	return a, b
	
a, b = f(1000000)
print a, ", len =",b

－－－－－

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

１．g(n, i=1)
・nで始まるコラッツ数列が1になるまでの要素数を返します。
・引数iは何番目かという順番値です。初期値は1です。
・if n==1: return i
　1から先のコラッツ数列は、1→4→2→1→・・・と振動しますので、1になったら終了です。
　このif文は、nが1の場合に処理を終了させるための設定です。
・if n%2: return g(n*3+1, i+1)
　else: return g(n/2, i+1)
　コラッツ数列の定義です。
　%演算子は割り算の余りを求める演算子です。
　奇数は余りが1(論理判定でTrue)で、現在値を3倍して1加え、順番値も次に進めます。
　偶数は余りが0(論理判定でFalse)で、現在値を2で割り、順番値も次に進めます。
このように、関数内で自分自身の関数を呼び出す記述を「再帰」といいます。
問題文にもあるように必ず1になることは証明はされていませんが、
いつかは1になるという想定です。

なお、コラッツ数列は大学入試センター試験にも出題されています。
平成23年度(2011年度)　数学Ⅱ数学Ｂ　第6問（大学入試センターの公式サイト）
問題(pdf) 解答(pdf)
公式サイトには過去3年分だけ載っているので、そのうちリンク先が消えるかもしれません。

２．f(n)
・iから始めて1になるまでのコラッツ数列のうち、最大項数を求めます。
・a = b = 0
　最大項数のときの開始値aとその最大項数bとし、0クリアしておきます。
・for i in xrange(n-(1-n%2), n/3, -2):
　コラッツ数列の開始値として、n-(1-n%2)から n/3まで, 2ずつ減らしていきます。
・「n-(1-n%2)」はnを超えない最大奇数です。
　%演算子は割り算の余りなので、(1-n%2)はnが偶数なら1で奇数なら0となり、この値をnから引くことで、偶数ならn-1で奇数ならnとなります。
　コラッツ数列の定義から、奇数の後は約3倍に増え、偶数の後は1/2に減るので、 最大項数になるような初項は必ず奇数だからです。
　また、奇数の後は約3倍に増えるため、n/3より小さい値は最大項数になることはありません。
・j = g(i)
　iから始めて1になるまでのコラッツ数列の項目数をjにセットします。
・if b<j: a, b = i, j
　そしてここまでの最大項数より大きければ、そちらを保存します。


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


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