PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 272 / モジュラー立方数2

正の整数 n に対し,C(n) を 1< x< n で x3≡1 mod n をみたす整数 x の数と定義する。

n=91 のとき,x は 8 つの値を取りうる。9, 16, 22, 29, 53, 74, 79, 81 であり,C(91)=8 である。

C(n)=242 をみたす正整数 n≤10^11 の合計を求めよ。

Problem 272 - Project Euler

検算用の式を作る1

PowerModList を使うと C(n) が作れます。まずは検算用に絶対に間違えようのないコードを書きました。


C(91)=8 の吟味

中国式剰余定理を使うと C(91)=8 になる理由がわかります。

 91=7\times 13,\, C(7)=3,\, C(13)=3

C(x) は C(pq)=C(p)C(q) (p, q は異なる素数)をみたします。3*3=9 個の整数から自明な1を除いて

C(91)=3\times 3-1=8

となるわけです。もう少し詳しく調べると次のことがわかります。

  • p が3で割って余り1の素数のとき, C(p^n)=3\quad (n\geqq 1)
  • p が3で割って余り2の素数のとき, C(p^n)=1\quad (n\geqq 1)
  •  C(3)=1, C(3^n)=3\quad (n\geqq 2)

3で割って余り1の素数を「よい素数」,余り2の素数を「悪い素数」と呼ぶことにしましょう。
242=3^5-1 なので,条件をみたす数は次のいずれかの形をしています。

  • (5種類のよい素数の積)x(悪い素数の積)
  • (5種類のよい素数の積)x(悪い素数の積)x3
  • (4種類のよい素数の積)x(悪い素数の積)x(2個以上の3の積)

条件をみたす数の最小値は

3^2\times 7\times 13\times 19\times 31=482391

また,よい素数は9268個ありました。

検算用の式を作る2

よい素数と9に注目して検算用の式その2を作りました。できればこれで brute force したかったのですが,10^10以上は「数が大きすぎて扱えない」エラーが出てしまいます。


本番その1

次の手順で解いたところ,約55分かかりました。

  1. 9とよい素数の和集合(myList)を作る
  2. myList の元を5個かけあわせた数 p[a,b,c,d,e] を作る
  3. p[a,b,c,d,e] の倍数で C(n)=242 となるものの和を求める


本番その2

p[a,b,c,d,e] の倍数について調べるのに「かけてから素因数分解」は効率が悪いと思ったので,「かける相手をあらかじめ素因数分解しておいて使いまわす」に変えてみましたが,時間は変わりませんでした。

包除原理を使うとよさそうなのですが,Mathematica っぽい書き方をするとメモリ不足でエラーになってしまうのが難点です。