PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 127 / abc-hit

n の根基 (radical) を rad(n) と書き,n の異なる素因数の積とする。
たとえば 504 = 2^3*3^2*7 より
rad(504) = 2*3*7 = 42

正整数の3つ組 (a, b, c) が abc-hit であるとは

  • GCD(a, b) = GCD(b, c) = GCD(c, a) = 1
  • a < b
  • a + b = c
  • rad(abc) < c

をみたすことである。(5, 27, 32) は abc-hit である。

  • GCD(5, 27) = GCD(5, 32) = GCD(27, 32) = 1
  • 5 < 27
  • 5 + 27 = 32
  • rad(4320) = 30 < 32

abc-hit は非常に稀である。c < 1000 には31個しかなく,そのときの ∑c は 12523 である。

c < 120000 での ∑c を求めよ。

Problem 127 - Project Euler


GCD(a,b)=1 のとき

  • GCD(b,c)=GCD(c,a)=1
  • rad(abc)=rad(a)*rad(b)*rad(c)

これを使って計算しました。約10分。

メモ化したり,rad(a)rad(b)≧2 を使ったりしましたが,規定の1分を大幅にオーバーしてしまいました。

この他に「a, b についてループさせる」「あらかじめ rad(n) のリストを作っておく」も試してみましたが,上の方法には及びませんでした。