レジリエンス

Project Eulerの問題にチャレンジした感想等を投稿してます。今回の問題は
➞ Project Euler P243: Resilience

分母がdの真分数のうち既約分数の割合[これをResilience(反発力？)と呼ぶ]をR(d)としたときR(d) < 15499/94744 となる最小のdを求めよ。

というものです。若干英語が分かりづらいですが問題そのものはシンプル。ところでこの「レジリエンス」という言葉現在開催中のパラリンピックの放送で結構耳にします。「折れない心」という意味だそうですが、この問題では既約分数が多い分母をレジリエンスが高いと呼んでいるようです。

今を切り開く力　―パラアスリートがもつレジリエンス

オイラーのφ関数

既約分数になるということは分子は分母と互いに素になる必要があるので、その数というと正にオイラーのφ関数そのものということになります。従って

$\displaystyle \large R(d) = \frac{\phi(d)}{d-1}$

オイラーのφ関数の公式により$p_k$をnの素因数とすると。

$\displaystyle \large\phi(n)= n\prod_{k=1}^d(1-\frac{1}{p_k})$

例えばn=12とすると素因数は2と3なので以下のようになります。
$\displaystyle \phi(12)= 12 (1-\frac{1}{2})(1-\frac{1}{3})=4$

従って
$\displaystyle R(12)=\frac{\phi(12)}{11} = \frac{12}{11}(1-\frac{1}{2})(1-\frac{1}{3})=\frac{4}{11}$

この式をよく見るとR(d)の値を小さくするためにはなるべく、小さい数のべき乗でない素因数を増やしていけばよいことが分かります。試しに素数を2から増やしていってR(d)を求めてみると以下のようになり、素因数23までの積でかなりゴールに近づいているのが分かります。後はここからdの値を調整すればという感じです。

15499/94744 = 0.1635881955585578
6 {2: 1, 3: 1} 0.4
30 {2: 1, 3: 1, 5: 1} 0.27586206896551724
210 {2: 1, 3: 1, 5: 1, 7: 1} 0.22966507177033493
2310 {2: 1, 3: 1, 5: 1, 7: 1, 11: 1} 0.2078822000866176
30030 {2: 1, 3: 1, 5: 1, 7: 1, 11: 1, 13: 1} 0.19181457924006792
510510 {2: 1, 3: 1, 5: 1, 7: 1, 11: 1, 13: 1, 17: 1} 0.18052571061430847
9699690 {2: 1, 3: 1, 5: 1, 7: 1, 11: 1, 13: 1, 17: 1, 19: 1} 0.1710240400491191
223092870 {2: 1, 3: 1, 5: 1, 7: 1, 11: 1, 13: 1, 17: 1, 19: 1, 23: 1} 0.16358819608886738
6469693230 {2: 1, 3: 1, 5: 1, 7: 1, 11: 1, 13: 1, 17: 1, 19: 1, 23: 1, 29: 1} 0.15794722312636564