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で、全ての素数の平方で割り切れない確率は、
この逆数を取って、
これを展開すると、1とあとは全ての平方数の逆数となります。
これはオイラーが解決したバーゼル問題で、π2 / 6になります。すなわち求める割合は、
6 / π2 = 0.6079271018…
となります。1014まで求めてみましたが、素晴らしく合いました。