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

プロジェクトオイラーの問題を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

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

プロジェクトオイラーの問題を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
この集合は21個の要素をもつことが分かる.

d ≦ 1,000,000について, 真既約分数の集合は何個の要素を持つか.

－－－－－


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





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

def f(n):
	L = range(n+1)
	for i in xrange(2, n):
		if L[i]<i: continue
		for j in xrange(i, n+1, i):
			L[j] /= i
			L[j] *= i-1
	return sum(L[2:])

n = 1000000
print f(n)

分母nの真既約分数の個数は「nと互いに素なn未満の数」の個数と同じです。
これは問６９のトーティエント関数φ(n)の定義そのものです。
つまり求める真既約分数の個数は、φ(2)からφ(1000000)までの和です。

φ(n)の計算ですが、
「nと互いに素なn未満の数」は、言い換えれば、1からnまでのn個の数字の中から素因数で割り切れる数を外していき最後まで残った数字の個数です。

例えば
nの素因数に2があれば、1からnのうち、2,4,6,...のように偶数を外すので
個数はn*(1/2)個減り、残りはn*(1 - 1/2)=n*(1/2)になります。

nの素因数に3があれば、1からnのうち、3,6,9,...のよう3の倍数を外すので
個数はn*(1/3)個減り、残りはn*(1 - 1/3)=n*(2/3)になります。

このとき外す数からカウントすると、例えば6なら2の倍数と3の倍数で重複してカウントされてしまいます。そこで、残る数から考えると上記の累積値として求まります。

つまり、nの素因数が2,3,･･･,mの場合、素因数で割っていって残る数の個数φ(n)は、
　n*(1 - 1/2)*(1 - 1/3)*･･･*(1 - 1/m)
= n*(1/2)    *(2/3)    *･･･*(m-1)/m
となります。

そこで1からnまでの一つひとつの数字について、
素因数を求めて上記のようにφ(n)を計算し総和を求めてみましたが、
このロジックのまま実装すると１分ルールを守れませんでした。
素因数を何度も求める部分が重いようでした。

そこでさらにひと工夫です。
φ(n)をnの順に求めるのではなく素因数候補の方を順に反映していくようにしてみます。
つまり、mを素因数とするφ(i)すべてに対して、(m-1)/m倍を累積していきます。
素因数候補が2ならば、φ(2)から2刻みにφ(4), φ(6)･･･を途中計算として1/2倍します。
素因数候補が3ならば、φ(3)から3刻みにφ(6), φ(9)･･･を途中計算として2/3倍します。
素因数候補がmならば、φ(m)からm刻みにφ(m*2), ･･･を途中計算として(m-1)/m倍します。

１．関数f(n)
・φ(0)からφ(n)のリストLを返します。リストLのi番目の要素L[i]=φ(i)です。
・φ(n)の値のリストLとして、最初に、i番目の要素に値iをセットした値nまでのリスト[0, 1,..., n]を準備します。
・ループ変数iが素因数候補です。
　iを小さい値から順に処理したとき、
　L[i]==iならば、上記の(m-1)/mが反映されていないので素因数です。
　L[i]<iならば、すでにiより小さい値で(m-1)/mされてるので素因数ではありません。
・なお、(m-1)/m倍するとき、この分数を先に計算するとfloat型になります。
　int型のまま計算する方が処理時間が短くすむため、(m-1)倍と1/m倍は別々に計算しています。
・ループ変数jがφ(n)の引数nです。
・ループ処理がすべて終わったら、リストLの2番目以降の要素の和を求めます。


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

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

プロジェクトオイラーの問題を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]

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

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


問７０「φ(n) が n の置換となる n を調べ上げよ」
オイラーのトーティエント関数 φ(n) (ファイ関数とも呼ばれる) とは, 
n 未満の正の整数で n と互いに素なものの個数を表す. 
例えば, 1, 2, 4, 5, 7, 8 は9未満で9と互いに素であるので, φ(9) = 6 となる. 
1 は全ての正の整数と互いに素であるとみなされる. よって φ(1) = 1 である.

面白いことに, φ(87109)=79180 であり, 87109は79180を置換したものとなっている.

1 < n < 10 7 で φ(n) が n を置換したものになっているもののうち, 
n/φ(n) が最小となる n を求めよ.

－－－－－


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






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

def p(n):
	L = [0,0]+[1]*(n-1)
	i = 2
	while i*i<=n:
		while not L[i]: i += 1
		for j in xrange(i+i, n+1, i): L[j] = 0
		i += 1
	return [i for i in xrange(n+1) if L[i]]

def f(n):
	N = [n, n, []]
	P = p(n//2)
	w = int(n**(0.5))
	for i, u in enumerate(P):
		if w<u: break
		z = n//u
		for j in xrange(len(P)):
			if z<P[j]: break
		for v in P[j: i: -1]:
			s, t = u*v, (u-1)*(v-1)
			if sorted(str(s))==sorted(str(t)):
				a = 1.0*s/t
				if a<N[1]: N = [s, a, [u,v]]
				break
	return N
n = 10000000
print f(n)

問６９の発展問題ということで、同様にはなく、数学的に別の表現ができないかを考えます。
まず、問６９とは逆に、n/φ(n)を最小にするためには、nをなるべく小さくしφ(n)はなるべく大きくします。
また、問６９の検討を考慮すると、
・ｎよりもφ(n)が大きく効いてくるので、φ(n)を大きくする。
・φ(n)の最大値は、ｎが素数のときのφ(n)=n-1なので、なるべく大きな素数を持つ。

ここで、ｎとφ(n)が置換の関係との条件から、素数では問題に合わないことがわかります。
それは、nとn-1は必ず1文字は異なり、置換の関係にならないからです。

そこで素数２つの積で、φ(n)との置換の関係を満たすnということになります。
それは、nが複数の素数の積ならば、その因数である素数の倍数以外には割りきれないため、φ(n)が大きい値のままですみます。
また、この場合の因数として使用する素数の件数なるべく少ない方がよいということになります。

１．関数p(n)
・n以下の素数リストを返します。問３７と同じです。

２．関数f(n)
　ｎ未満の整数で、問題に合うｎ、n/φ(n)、ｎを構成する素数２つのリストを返します。
　候補の素数の範囲は、２つの素数の積がn未満ということから、n//2以下で十分です。
　素数候補のリストから、
　ループ変数uで小さい方から１つずつ取り出し、
　ループ変数vで大きい方から１つずつ取り出します。
　素数uと素数vの積とそのφ値をs,tとします。
　置換の関係のチェックはs,tを1文字ずつ取り出してそのソート状態が一致することとします。
　リストNに関係情報をためて、n/φ(n)の小さい値がきたら入替えます。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
[8319823, 1.0007090511248113, [2339, 3557]]

プロジェクトオイラー 問６９

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



問６９「n/φ(n) が最大となる n の値を求めよ」
オイラーのトーティエント関数, φ(n) [時々ファイ関数とも呼ばれる]は,
n と互いに素な n 未満の数の数を定める.
たとえば, 1, 2, 4, 5, 7, そして8はみな9未満で9と互いに素であり, φ(9)=6.

n	互いに素な数	φ(n)	n/φ(n)
2	1	1	2
3	1,2	2	1.5
4	1,3	2	2
5	1,2,3,4	4	1.25
6	1,5	2	3
7	1,2,3,4,5,6	6	1.1666...
8	1,3,5,7	4	2
9	1,2,4,5,7,8	6	1.5
10	1,3,7,9	4	2.5

n ≦ 10 では n/φ(n) の最大値は n=6 であることがわかる.
n ≦ 1,000,000で n/φ(n) が最大となる値を見つけよ.


－－－－－

まず、問題文のとおりにプログラミングしてみました。
n未満の整数を１つずつnとともに「エラトステネスのふるい」にかけることで
その最大公約数が1ならば互いに素と判定してカウントし、n/φ(n)を計算してみました。
でもこれではn=1,000,000どころか、n=10,000でさえ１分を超え、１分ルールを守れません。


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

#最大公約数を求める（エラトステネスのふるい）
def gcd(a, b):
	if a<b: a, b = b, a
	if b: return gcd(b, a%b)
	else: return a
#n未満でnと互いに素な数の個数
def g(n):
	if n: L = [i for i in xrange(n) if gcd(n, i)<=1]
	else: L = [0]
	return len(L)
def f(n):
	L = [float(i)/g(i) for i in xrange(n+1)]
	m = max(L)
	return L.index(m), m

問題文のまま実装したのではロジック改良でクリアできるレベルではないので、
プログラミング以前に、まずこの問題を数学的に別の表現に言い換えることを考えました。

n/φ(n)を最大値にするためには、nをなるべく大きくしφ(n)はなるべく小さします。

問題文中の表をよくみると、まずnが素数以外であることがわかります。
nが素数の場合、1以上n未満の整数はすべて互いに素なので
φ(n)=n-1になり、他の値と比べてnに対するφ(n)の値が明らかに大きすぎます。

さらに、nが偶数のときにφ(n)の値が小さいことがわかります。
理由は、nが偶数ならば、n未満の偶数すべてnとは互いに素にならないためです。
同様にnが3の倍数ならば、n未満の3の倍数はすべてnと互いに素になりません。
つまり、pを素数とすると、
nがpの倍数ならば、n未満のpの倍数はすべてnと互いに素にならずφ(n)にカウントされません。
また、nの素因数にpを持てば、pの倍数は因数として持たなくてよいです。
つまり、φ(n)の最小値となるnは、
n未満の素数すべてを素因数として１つずつ持つ値となります。

また、n/φ(n) の分母の値の増え方は１ずつですが、
nに素数因子を１つ持つごとのφ(n)の減り方は明らかに1個よりみ大きいので、
分子φ(n)の減少の方が分母nの増加よりも大きく効いてきます。

上記から、φ(n)が最小値となるnは、
素数を小さい順に掛け、その積がn未満の最大値になるような値となります。

ちなみに、問題文のn≦10では、素数は、2, 3, 5, 7,・・・なので、
2×3＝6で、n=6のときにn/φ(n) が最大値になります。



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

def h(n):
	if n%2 or n==2:
		for i in xrange(3, n, 2):
			if i*i>n: return n
			if not n%i: return 1
		return n
	return 1
 
def f(n):
	r = 1
	for i in xrange(n):
		r *= h(i)
		if r>n: return r//i

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

１．h(n)
　引数nが素数ならばその数を、素数以外ならば1を返します。
　問５８で作成した素数判定を修正し、素数自身または1を返却することで、
　呼び出し元で簡単に素数だけ掛け算できるようにしました。
　詳細は問５８を参照してください。
　
・if n%2 or n==2:
　「n%2」はnを2で割った余りで、論理的にTrueになるのは1の場合、つまり奇数です。
　if文の中は、nが2か奇数の場合の処理です。

・for i in xrange(3, n, 2):
　ループ変数iは3以上n未満の奇数です。2はループ変数の増分です。

２．f(n)
・r = 1
　求める数をクリアします。掛け算していくので初期値は1です。

・for i in xrange(n):
　ループ変数iは0以上n未満の整数です。

・r *= h(i)
　関数h(i)の戻り値を累積して掛け算していきます。

・if r>n: return r//i
　掛け算累積値がnを超えたら、最後に掛けた数で割って
　n未満の掛け算累積値を返します。

３．関数の外
・1,000,000を関数f(n)に渡し、戻り値を表示します。


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