PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 243 / 弾性

分子が分母より小さい正の分数を真分数と呼ぶ。任意の分母 d に対して真分数は d-1 個ある。たとえば, d = 12 では次のようになる。

1/12, 2/12, 3/12, 4/12, 5/12, 6/12, 7/12, 8/12, 9/12, 10/12, 11/12

約分できない分数を弾性分数(resilient fraction)と呼ぶことにしよう。さらに分母に対し,弾性(resilience)を真分数のうち弾性分数の比率と定義し,R(d)で表す。たとえば R(12) = 4/11 である。
ちなみに d = 12 は弾性が R(d) < 4/10 をみたす最小の分母である。

R(d) < 15499/94744 をみたす最小の分母 d を求めよ。

Problem 243 - Project Euler


とりあえず実験してみました。100以下の数についてプロットします。

f:id:variee:20170523171743p:plain

極小値が右下がりな感じがわかると思います。小さい方から5個取り出して,n を素因数分解してみました。

素数をたくさん含む方が有利らしいです。n の範囲を 2*3*5*7*11=2310 までに広げて同じことをやってみました。

一般化できそうなことがわかりました。

  1. n=2*3*5*7*11 で最小になる
  2. n=2*3*5*7*k (k<11) に対する値が最小値に続く

n の範囲が連続する素数までなら1.のタイプの数で最小になり,そうでないなら2.のタイプの数で最小になると思われます。

また,n を連続する素数の積に限定して調べてみると,10個目ではじめて条件をみたすことがわかりました。

以上で回答の方針が立ちます。連続する9個の素数の積からはじめて,その倍数について調べれば十分です。ループの回数は最大で
Prime[10]=29 回。これならすぐ終わるはずです。

最終的な結果はこうなりました。