PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 266 / 擬似平方根

12の約数は 1,2,3,4,6,12 である。このうち12の平方根を超えない最大の数は3である。
整数 n に対し,その平方根を超えないような n の最大の約数を n の擬似平方根(PSR) と呼ぶことにしよう。PSR(3102)=47 である。

p を 190 未満の素数の積とする。
PSR(p) mod 10^16 を求めよ。

Problem 266 - Project Euler


PSR[n] を求める関数は Mathematica で簡単に書けますが,2^42 個もの約数についてまともに調べるのは流石に無理でした。メモリ不足で止ってしまいます。

PSR[n_]:=Max[Select[Divisors[n], #^2 <= n &]]

190以下の素数42個を小さい方から順に1個目~21個目,22個目~42個目の2グループに分け,その積の約数を求めます。これら約数の集合を小グループ,大グループとよぶことにします。

求める数は小グループの数1個と大グループの数1個の積です。

  1. 小グループの数を1個選んで固定
  2. 積が √p を超えないように,ペアになる大グループの数を選ぶ
  3. すべてのペアの積の最大値が答え

と,このように計算しました。大グループの検索範囲が徐々にせばまっていくことに気づくと,大幅に時間を短縮できます。
たとえば小グループの i 番目が大グループの j 番目とペアになったとすると,小グループの i+1 番目とペナになるのは大グループの j 番目以下です。