ホーム - 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.

\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?

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

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

\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倍と素数の和で表せない最小の奇合成数はいくつか?

(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)