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

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

問７１「真既約分数を昇順に並べ上げよ」
nとdを正の整数として, 分数 n/d を考えよう. 
n<d かつ HCF(n,d)=1 のとき, 真既約分数と呼ぶ.

d ≦ 8について既約分数を大きさ順に並べると, 以下を得る:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
3/7のすぐ左の分数は2/5である.

d ≦ 1,000,000について真既約分数を大きさ順に並べたとき, 
3/7のすぐ左の分数の分子を求めよ.

－－－－－


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





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

def gcd(a, b):
	if a<b: a, b = b, a
	if b: return gcd(b, a%b)
	else: return a

def f(n, a, b):
	L = [0,0,1]
	s = 1.0*a/b
	for i in xrange(1, n+1):
		j = int(i*s)
		if not j: continue
		while gcd(i, j)>1:
			j -= 1
		u = s - 1.0*j/i
		if 0<u<L[2]: L = [j, i, u]
	return L

n, a, b = 1000000, 3, 7
print f(n, a, b)

１．gcd(a,b)
　「ユークリッドの互除法」を使用して最大公約数を返します。
　説明は問５を参照してください。

２．g(n,a,b)
　n以下の分母を持つ真規約分数を大きさ順に並べたときに、
　a/bのすぐ左の分数についての、分子、分母、その分数のa/bと差を返します。
　
　まず、基準値となるa/bを計算しsとします。
　1.0を掛けているのは整数型ではなく浮動小数点型で計算するためです。
　float関数で型変換するよりも速いです。
　ループ変数iは求める分数の分母で、jは分子です。
　分子は、分母と基準値を掛け、int関数で整数部をとることで算出します。
　jが0の場合、分数にならなので分母を１つ進めます。
　また、j/iが真既約分数にならない場合、真既約分数になるまでjを1つずつ小さい値にします。
　真既約分数の判定は、分母子の最大公約数が1であることとしました。
　こうして分数j/iが定まったところで、基準値との差分を求めuとします。
　uがここまで処理したうちの最小値ならば、分子j、分母i、差分uをリストLの値と差し替えてためます。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
[428570, 999997, 1.4285757138354782e-07]