Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|Project Euler]]

# [[Problem 46]]

## Goldbach's Other Conjecture

<p>It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.</p>

\begin{align}

9 = 7 + 2 \times 1^2\\

15 = 7 + 2 \times 2^2\\

21 = 3 + 2 \times 3^2\\

25 = 7 + 2 \times 3^2\\

27 = 19 + 2 \times 2^2\\

33 = 31 + 2 \times 1^2

\end{align}

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?

## もうひとつのゴールドバッハの予想

<p>Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.</p>

\begin{align}

9 = 7 + 2 \times 1^2\\

15 = 7 + 2 \times 2^2\\

21 = 3 + 2 \times 3^2\\

25 = 7 + 2 \times 3^2\\

27 = 19 + 2 \times 2^2\\

33 = 31 + 2 \times 1^2

\end{align}

後に, この予想は誤りであることが分かった.

平方数の2倍と素数の和で表せない最小の奇合成数はいくつか?

```scheme

(import (scheme base)

        (gauche base))

(define (prime? num)

  (assume (exact-integer? num))

  (assume (positive? num))

  (cond

    [(= num 1) #f]

    [(= num 2) #t]

    [(even? num) #f]

    [(= num 3) #t]

    [(zero? (mod num 3)) #f]

    [else

      (let loop ([i 1])

        (let ([n6-1 (- (* i 6) 1)]

              [n6+1 (+ (* i 6) 1)])

          (cond

            [(< num

                (* n6-1 n6-1))

             #t]

            [(zero? (mod num n6-1))

             #f]

            [(< num

                (* n6+1 n6+1))

             #t]

            [(zero? (mod num n6+1))

             #f]

            [else

              (loop (+ i 1))])))]))

(define (goldbach? num)

  (assume (exact-integer? num))

  (assume (<= 9 num))

  (let loop ([i 1])

    (let ([square-i*2 (* (* i i)

                         2)])

      (cond

        [(< num square-i*2) #f]

        [(prime? (- num

                    square-i*2))

         #t]

        [else

          (loop (+ i 1))]))))

(define goldbach-false-num

  (let loop ([i 35])

    (cond

      [(prime? i) (loop (+ i 2))]

      [(goldbach? i) (loop (+ i 2))]

      [else i])))

(define answer-46 goldbach-false-num)

(format #t "46: ~d~%" answer-46)

```