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

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

問７５「直角三角形を作るときに1通りの折り曲げ方しか存在しない鉄線の長さの総数」
ある長さの鉄線を折り曲げたときに1通りの直角三角形を作る最短の長さは12 cmである.
他にも沢山の例が挙げられる.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

それとは対照的に, ある長さの鉄線 (例えば20cm) は整数長さで折ることができない.
また2つ以上の折り曲げ方があるものもある. 2つ以上ある例としては, 
120cmの長さの鉄線を用いた場合で, 3通りの折り曲げ方がある.

120 cm: (30,40,50), (20,48,52), (24,45,51)

Lを鉄線の長さとする. 
直角三角形を作るときに1通りの折り曲げ方しか存在しないような
L ≦ 1,500,000 の総数を答えよ.

－－－－－


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

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

def f(n):
	M = [0 for i in xrange(1, n+1)]
	for i in xrange(1, n):
		for j in xrange(1, i):
			if 2*i*(i+j)>n: break
			a, b, c = i*i-j*j, 2*i*j, i*i+j*j
			if gcd(c, a)>1: continue
			if gcd(c, b)>1: continue
			s = a+b+c
			for k in xrange(s, n, s): M[k] += 1
	L = [i for i, j in enumerate(M) if j==1]
	return len(L)

n = 1500000
print f(n)

直角三角形の直角を挟む辺をa、b、斜辺をcとして、
ピタゴラスの定理「a2 + b2 = c2」が成り立つかを総当りでチェックすると、
１分ルールに全然間に合いません。

まず考えたことは、最大公約数が1の既約なa,b,cの組を探し、この整数倍の組を消しこむ方法です。
例えば(3,4,5)に基づいて(6,8,10)などをチェックし探すことから外します。

次に考えたことは偶数奇数の絞込みです。
・aもbも偶数の場合
　(2m)2 + (2n)2 = c2から、c2は偶数、つまりcも偶数になってしまい、
　a,b,cは既約でないので、これは成立しません。
・aもbも奇数の場合
　(2m+1)2 + (2n+1)2
= 4m2 + 4m + 4n2 + 4n + 2
= 4(m2 + n2 + m + n) + 2  = c2
ここでc2が4で割ったときに余り2になるかというと、
　cが偶数ならば、c=2s、c2 = (2s)2 = 4s2、なのでc2は4で割りきれ余り0
　cが奇数ならば、c=2s+1、c2 = (2s+1)2 = 4(s2+s)+1、なのでc2は４で割ると余り1
つまり、c2は4で割って余り2になることはありえないので、これも成立しません。
よって、a,bは奇数と偶数の組です。偶数同士や奇数同士ではありません。
そこで、a2 + b2 = c2 より、偶数の２乗と奇数の２乗の和を求めると、
　(2m)2 + (2n+1)2
= 4m2 + 4n2 + 4n + 1
= 4(m2 + n2 +n) + 1  = c2
２乗して奇数ということは、cは必ず奇数です。

以上より直角を挟む辺a,bは奇数と偶数の組で、斜辺cは奇数です。
a,bは入れ替えても一般性を失わないので、a奇数、b偶数で固定します。

さらに、a2 + b2 = c2より、
b2 = c2 - a2
b2 = (c+a)(c-a) ...(1)

a, b, cは既約で、(1)の左辺が平方数なので、
c+a、c-aは両方とも平方数を因子に持ちます。 ...(2)

また、bは偶数なので、b=2rとおくことができて
b2 = (2r)2 = 4r2 なので、
b2は4の倍数 ...(3)

a, cは両方とも奇数なので、c+aとc-aは両方とも偶数。
c+a=2p, c-a=2q ...(4)

上記(2), (3), (4)を総合すると、0<j<iの条件で
b2 = 4i2j2
c+a = 2i2
c-a = 2j2
とおくことができる。よって、
b = 2ij
(c+a)+(c-a) = 2i2 + 2j2
         2c = 2(i2 + j2)
          c = i2 + j2
(c+a)-(c-a) = 2i2 - 2j2
         2a = 2(i2 - j2)
          a = i2 - j2
以上より、
(a, b, c) = (i2-j2, 2ij, i2+j2), 0<j<i, cが斜辺。...(5)


１．関数gcd(a, b)
・ユークリッドの互除法でa,bの最大公約数を返します。
・問５では自分で自分自身を呼び出す再帰呼び出しをしていましたが、while文を使うことで再帰呼び出しなしにしました。
・必ずa>bとなるように呼び出しすことで大小を入れ替える部分をコメントアウトしました。

２．関数f(n)
・長さn以下の針金で各辺が整数の直角三角形を作るときに1通りの折り曲げ方しか存在しない長さの個数を返します。
・折り曲げパターン数リストMは、i番目の要素に周がiで各辺が整数の直角三角形が何通りあるかを格納します。初期値はすべての要素が0です。

・for i in xrange(1, n):
for j in xrange(1, i):
if 2*i*(i+j)>n: break
a, b, c = i*i-j*j, 2*i*j, i*i+j*j
　上記(5)のまま、プログラミングしました。
　停止条件は３辺の和がnを超えたときなので、
　a+b+c = (i2-j2)+2ij+(i2+j2) = 2i2+2ij = 2i(i+j) > n です。

・if gcd(c, a)>1: continue
　if gcd(c, b)>1: continue
　a, b, cが既約でない、つまり最大公約数が1より大きい場合は、次の候補へ。

・s = a+b+c
　for k in xrange(s, n, s): M[k] += 1
　a, b, cの３辺和をsとして、sからsごとの値kが、sの整数倍の長さの針金であり、直角三角形の折り曲げ方が1つあるということで、折り曲げパターン数リストMのk番目の値を+1します。
　
・L = [i for i, j in enumerate(M) if j==1]
　return len(L)
　折り曲げパターン数リストMは、針金長ごとの折り曲げパターン数を格納してあるので、その要素が1のものだけの場合、リストLに格納します。内包表記で記述しています。
　そして、len関数でリストLの要素数を求め呼び出し元へ返します。


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

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

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

問７４「60個の循環しない項を持つ階乗列となる数を特定せよ」

145は各桁の階乗の和が145と自分自身に一致することで有名である.

1! + 4! + 5! = 1 + 24 + 120 = 145

169の性質はあまり知られていない. これは169に戻る数の中で最長の列を成す.
このように他の数を経て自分自身に戻るループは3つしか存在しない.

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

どのような数からスタートしてもループに入ることが示せる.
例を見てみよう.

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

69から始めた場合, 列は5つの循環しない項を持つ.
また100万未満の数から始めた場合最長の循環しない項は60個であることが知られている.

100万未満の数から開始する列の中で, 60個の循環しない項を持つものはいくつあるか?

－－－－－


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

def h(n):
	c = 1
	for i in xrange(2, n+1): c *= i
	return c

def g(n, d): return sum([d[s] for s in str(n)])

def f(n, m):
	d = {}
	for i in xrange(10): d[str(i)] = h(i)
	N = []
	for i in xrange(n):
		s, M = i, []
		while (s not in M) and (i<=s):
			M.append(s)
			s = g(s, d)
		t = len(M)
		if s<i: t += N[s]
		N.append(t)
	return sum([1 for i in N if i==m])

n = 1000000
print f(n, 60)

１．関数h(n)
・nの階乗値を返します。再帰呼び出しは使わず単純ループで掛け算します。
・再帰呼び出しにした場合、n≧1000で「maximum recursion depth exceede」エラーになるので、再帰呼び出しの深さの限界値をsys.setrecursionlimit()で設定する必要があります。

２．関数g(n, g)
・数字nの各桁の階乗値の和を返します。
・dは1桁数字の階乗値を持つ辞書です。但し、キーは文字型です。
・数字nを文字型にして一文字ずつ階乗値辞書から階乗値を取得し、最後にsum関数で合計します。

３．関数f(n, m)
・n未満の数字のうち、循環しない各桁階乗和をmもつものの個数を返します。
・辞書dとして、関数gで使用する階乗値辞書を作っておきます。
・リストNには、i番目の要素に数字iの循環しない各桁階乗和の個数を入れます。
・ループ変数iはn未満の数を昇順に１つずつとります。
・sは各桁階乗和の計算対象の候補です。初期値はループ変数iです。
・リストMには、各桁階乗和を１つずつ進めながら循環部分になるまで持ちます。
・whileループで、計算対象候補sがすでにリストMにあれば循環部分突入なので終了です。
　また計算対象候補sがループ変数i未満なら、その先の循環部分までの個数はリストNにあるのでやはりループは終了です。
・tで各桁階乗和をためたリストMの個数を求め、さらに計算対象候補sがループ変数i未満だった場合はそれ以降の循環部分に達するまでの個数を足します。
・上記の状態のtが数字iでの、循環しない各桁階乗和の個数です。リストNに追加しておきます。

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

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

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

問７３「真既約分数をソートした集合内の1/3と1/2の間に何個の分数があるか?」

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
1/3と1/2の間には3つの分数が存在することが分かる.

では, d ≦ 12,000 について真既約分数をソートした集合では,
1/3 と 1/2 の間に何個の分数があるか？

－－－－－


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




最初に考えた方法は、
分子候補と分母候補の二重ループ内で、
ユークリッドの互除法でその分母子の最大公約数が1の分数を真既約分数として
カウントアップする方法です。
　しかしこの方法では私のＰＣでは１分半かかり１分ルールを守れませんでした。
が、自力ではここまでだったのでそのまま書いておきます。

def gcd(a, b):
	#if a<b: a, b = b, a
	while b: a, b = b, a%b
	return a
def f(n, x1, x2, y1, y2):
	c = 0
	for i in xrange(2, n+1):
		a, b = i*x1//x2+1, i*y1//y2
		if i*y1%y2>0: b += 1
		for j in xrange(a, b):
			if gcd(i, j)==1: c += 1
	return c

s = f(12000, 1, 3, 1, 2)
print s

１．gcd(a,b)
・「ユークリッドの互除法」を使用して最大公約数を返します。
　説明は問５を参照してください。
　関数fから呼び出されるとき、既約分数の分母、分子の順でに引数にセットすれば、引数は必ずa>bなので、割る数と割られる数を入れ替える必要はなくなるため、最初の行はコメントアウトしました。

２．f(n, x1, x2, y1, y2)
・分母がn以下の真既約分数のうち、x1/x2より大きくy1/y2より小さいものの個数を返します。
・ループ変数iが分母、jが分子です。
・分母iは2からnの整数です。
・分子jの開始値aと終了値bは、それぞれ分母iのx1/x2倍とy1/y2倍になります。
　//演算子は商の整数部を示します。
　開始値はx1/x2より大きいということで、i*x1//x2は含まないので、開始値aを+1しておきます。
　終了値はy1/y2より小さいということで、j=i*y1//y2のときに、
　この真既約分数全体で丁度y1/y2と同じとき、
　つまりはi*y1/y2で余りがあって割り切れない場合は対象に含めます。
　そこで余りの%演算子を使った、i*y1//y2が0より大きければ終了値bを+1します。
・gcd関数で分母子の最大公約数が1の場合、その分数は真既約分数です。


自分のＰＣでも１分ルールを守りたかったのですがやり方を思いつかなかったので、ネット検索で以下のことがわかりましたので参考にしました。

・分母の最大値nを与えて昇順に並べた真既約分数の数列を「ファレイ数列」という。
・ファレイ数列の隣接する分数では以下の定理が成り立つ。
(定理1)小さい方からa/b, c/dが隣接する場合、bc-ad = 1。
(定理2)小さい方からa/b, c/d, e/fが隣接する場合、c/d = (a+e)/(b+f) 
証明はネット検索してください。

定理(2)はファレイ数列で連続する３つの分数の真ん中の分数は、
左右の分数の、分子の和／分母の和という、隣接３要素間の関係を簡潔に示しています。
これを使えば、連続する２つの分数からその１つ先の隣接する分数が計算でき、
ファレイ数列を指定範囲の分だけ生成して数えることができます。

上記を利用した解答例は以下です。畳んでいます。

def f(n, x1, x2, y1, y2):
	a, b, cnt = x1, x2, 0
	c = (n*a+1)//b
	while (b*c-1)%a: c -= 1
	d = (b*c-1)//a
	while (c, d)!=(y1, y2):
		cnt+=1
		k = (n+b)//d
		a, b, c, d = c, d, k*c-a, k*d-b
	return cnt

s = f(12000, 1, 3, 1, 2)
print s

１．f(n, x1, x2, y1, y2)
・分母がn以下の真既約分数のうち、x1/x2より大きくy1/y2より小さいものの個数を返します。

・５行目までで、範囲の最小値x1/x2の左隣の分数c/dを求めます。
　このまま範囲全体のループにしても解答は求まりますが、cをカウントダウンしているwhileループのループ回数が大きく処理が遅いので、最初の値を求めることだけに留めます。

・６行目のwhileループで、隣接するa/bとc/dからその１つ大きい分数を求め、
　分母子の組ごと１つずつ大きい方に進めて範囲の最大値y1/y2になるまで、
　件数をカウントアップします。

・最初の１つの分数から隣接する大きい値の分数を求める方法は以下です。
　以下の連立方程式を解きます。
　┌ bc-ad = 1（a,b,c,dは正の整数）(定理1)より。...(1)
　└ d≦n     （d, nは正の整数）...(2)

　(1)(2)より、
　d = (bc-1)/a ≦n、正の整数...(3)

　また、(1)より、bc ≦ an+1
　c ≦ (an+1)/b、正の整数...(4)
　分母子c, dはそれぞれの値が大きいほどその分数c/dはa/bとの差が小さくなります。
　なので、分子cはその最大値候補から1ずつ減らしたループの中で最初の整数条件を満たした値です。

　そこで、cは(4)より、(an+1)/bから1ずつ減らしたループで、
　停止条件は(3)より、(bc-1)/aが整数値かをその余りの有無で判定します。
　こうして分子cが決まれば、これを(3)に代入して分母dも決まります。
　これで、最初の分数、a/bとc/dが決まります。

・後は分母子c,dが、求める範囲の最大値y1/y2になるまで隣接分数を求めていきます。
　小さい方からa/b, c/d, e/fが隣接する場合、
　(定理2)より、c/d = (a+e)/(b+f)
　c/dが真既約分数なので、(a+e)/(b+f)の約分できる値をkとして、
　以下の連立方程式を解きます。
　┌ kc = a+e
　└ kd = b+f
　
　┌ e = kc-a ...(5)
　└ f = kd-b ≦ n（分母なので）...(6)
　(6)より、k ≦ (n+b)/d ...(7)
　
　これで、範囲の最小値x1/x2から１つずつ大きな分数を計算していき、
　範囲の最大値y1/y2になるまで個数をカウントアップします

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