Project Euler 362(2)

http://projecteuler.net/index.php?section=problems&id=362

今日の昼休みに手計算でS(100)を求めていたらだんだんわかってきた。素数を求めるのにも1時間以上かかるのにと思っていたが、全然見当違いだった。でも1分以内は無理かな?
え、1010までのsquare freeの整数の個数を求めるのに0.1秒だ。


ところで、まったくの余談ですが、square freeの整数の割合はだいたい6割です。これはなぜかというと、4で割り切れない確率は3/4、9で割り切れない確率は8/9で、全ての素数の平方で割り切れない確率は、

 (\frac{2^2-1}{2^2})(\frac{3^2-1}{3^2})\cdots

この逆数を取って、

 (\frac{1}{1-2^{-2}})(\frac{1}{1-3^{-2}})\cdots
 = (1 + \frac{1}{2^2} + \frac{1}{2^4} + \cdots)(1 + \frac{1}{3^2} + \frac{1}{3^4} + \cdots)\cdots

これを展開すると、1とあとは全ての平方数の逆数となります。

 = 1 + \frac{1}{2^2} + \frac{1}{3^2} + \frac{1}{4^2} + \cdots

これはオイラーが解決したバーゼル問題で、π2 / 6になります。すなわち求める割合は、

6 / π2 = 0.6079271018…

となります。1014まで求めてみましたが、素晴らしく合いました。