PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 46 / もうひとつのゴールドバッハ予想

Christian Goldbachはすべての奇合成数は平方数の2倍と素数の和で表せると予想した。

  • 9 = 7 + 2×1^2
  • 15 = 7 + 2×2^2
  • 21 = 3 + 2×3^2
  • 25 = 7 + 2×3^2
  • 27 = 19 + 2×2^2
  • 33 = 31 + 2×1^2

後にこの予想は誤りであることが分かった。平方数の2倍と素数の和で表せない最小の奇合成数はいくつか?

Problem 46 - Project Euler


2通りの方法で解きました。最初にやったのがこちら。奇合成数の集合 myList1 と「平方数の2倍と素数の和」の集合 myList2 を比較するというものです。

答えの5777を得るために10^4まで調べていますが,myList2の作り方がかなり適当です。n=5 を指定すると物理メモリの「変更済み」が多発して固まってしまいます。

そこで考え直したのがこちら。

この問題では最小値を求めるだけなので,前もって大きなリストを作っておく必要はありません。(n-素数)/2 が平方数になるかどうか調べていって SelectFirst しています。