PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 193 / 平方因子を含まない数

正の整数 n が任意の素数の2乗によって割り切れないとき,n を「平方因子を含まない(squarefree)」と呼ぶ。1, 2, 3, 5, 6, 7, 10, 11 は平方因子を含まないが,4, 8, 9, 12 は含む。

2^50 未満で平方因子を含まない数はいくつあるか?

Problem 193 - Project Euler

brute force

平方因子を含むかどうか調べる関数 SquareFreeQ を使います。ためしに1〜12を調べてみましょう。問題文通りの結果になります。


次は1以上2^50未満について調べます。コードは第187問とほぼ同じです。

variee.hatenadiary.com

結果はこちら。数時間放置しましたが,答えが返ってこなかったのでabortしました。さすがに 2^50 個もの数について調べるのは無理だったみたいです。


2^10=1024で実験

2^10=1024で実験してみましょう。問題文の「未満」を「以下」に変えても答えに影響ないので,以後こちらで考えます。squarefree な数は624個です。


これを手計算で求めるとなると,不適なものを除外していくでしょう。以下,[ ] はガウス記号です。

  • 2^2の倍数は [2^10/2^2] 個,3^2の倍数は [2^10/3^2] 個,……
  • (2*3)^2の倍数は [2^10/(2*3)^2] 個,……

これらを2^10=1024から引いたり足したりしたものが答えです。

(相異なる k 個の素数の積)^2 で割りきれる数の個数を N(k)であらわすと,こうなります(包除原理)。

1024-{N(1)-N(2)+N(3)-...}

メビウス関数を使おう

上と同じことを2^50という巨大な数に対して行うため,メビウスのμ関数を使います。μ(n) は次のような値をとります。

  • n=1のとき,1
  • n が1以外の平方数で割り切れるとき,0
  • n が相異なる k 個の素因数に分解されるとき,(-1)^k

包除原理では+と-が交互にあらわれますが,μ関数を使うと単純にμ(k) [2^10/k^2] の和として処理できます。無事1分におさまりました。