PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 239 / 擬似フォーチュン数

偶数の正整数 N は 2 の累乗であるか素因数がすべて連続した素数である場合,許容的と呼ぶ。最初の 12 個の許容的な数は 2,4,6,8,12,16,18,24,30,32,36,48 である。

N が許容的であるとき,N+M が素数である最小の整数 M > 1 を N の擬似フォーチュン数(pseudo-Fortunate number)と呼ぶ。

たとえば N=630 は許容的である。630 は偶数で,その素因数は連続する素数 2, 3, 5, 7 である。

631 より大きい次の素数は 641 であり,630 の擬似フォーチュン数は M=11 である。同様に 16 の擬似フォーチュン数は 3 である。

10^9 未満の許容的な数 N に対して, すべての異なる擬似フォーチュン数の合計を求めよ。

Problem 293 - Project Euler


問題文の流れは

  1. 許容的な数を求める
  2. 擬似フォーチュン数を求める

ですが,擬似フォーチュン数の方が簡単なのでこちらから書きました。
NextPrime を使います。

次に許容的な数を求めます。「10^9 未満」の条件から,使える素数は9個です。

「2だけ使った数の集合を作る」→「その各要素に3をかけたものの集合を作る」のような操作を繰り返して,最後に和集合をとります。
NestWhileList と AppendTo で書きました。

計算時間は約0.3秒で,許容的な数は6656個,相異なる擬似フォーチュン数は41個でした。ダブりまくりです。