2013年1月26日土曜日

プロジェクトオイラー 問70

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


問70「φ(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)


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

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

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

1.関数p(n)
・n以下の素数リストを返します。問37と同じです。

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

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

0 件のコメント:

コメントを投稿