Project Euler [Problem 46]
ゴールドバッハ予想ってなんか聞いたことあるわ
でもたぶんこっちじゃない
問題
Goldbach's other conjecture
It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.
[tex: 9 = 7 + 2 \times 12] [tex: 15 = 7 + 2 \times 22] [tex: 21 = 3 + 2 \times 32] [tex: 25 = 7 + 2 \times 32] [tex: 27 = 19 + 2 \times 22] [tex: 33 = 31 + 2 \times 12]
It turns out that the conjecture was false.
What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
私訳
ゴールドバッハの別の予想
クリスチャン・ゴールドバッハが提案した 「すべての奇数の合成数は素数と平方数の2倍の和の形で書ける」という予想を指す。
[tex: 9 = 7 + 2 \times 12] [tex: 15 = 7 + 2 \times 22] [tex: 21 = 3 + 2 \times 32] [tex: 25 = 7 + 2 \times 32] [tex: 27 = 19 + 2 \times 22] [tex: 33 = 31 + 2 \times 12]
この予想は偽であった。
最小の奇数の合成数で、この形に書けないものはなにか？
解答方針
奇数の合成数 c をまず作る必要があり、
さらにそこから平方数の候補 () を探索し、差が素数に含まれるか判定する。
差が 2 のケースを吸収するには、候補数とほとんど同じ大きさの素数表が必要である。
従って、大きな素数表を作り、その隙間の奇数を探索する方針とする。
ちょっと遅すぎた。 方針を変えて、エラトステネスの篩と同じように、 素数を出発点として [tex: 2 \times k2] を加算した、 予想に適合する数のリストを作ってみることにする
結局素数判定にバグがあったのが問題だったっのではないかとなった
