HOME SUMMARY

Problem 46

1. Problem

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.

\[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\]

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?

哥德巴赫的另一个猜想

克里斯蒂安·哥德巴赫曾经猜想,每个奇合数都可以写成一个素数和一个平方的两倍之和。

\[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\]

最终这个猜想被推翻了。

不能写成一个素数和一个平方的两倍之和的最小奇合数是多少?

2. Solution

没什么好说的,直接求就是了:

(defun eu7-isprime (n)
  (cond
   ((<= n 1) nil)
   ((< n 4) t)
   ((zerop (% n 2)) nil)
   ((< n 9) t)
   ((zerop (% n 3)) nil)
   (t (let ((bound (floor (sqrt n))))
        (named-let f ((i 5))
          (cond
           ((> i bound) t)
           ((zerop (% n i)) nil)
           ((zerop (% n (+ i 2))) nil)
           (t (f (+ i 6)))))))))

(cl-block 'fin
  (cl-loop for i from 35 by 2
           if (not (eu7-isprime i)) do
           (cl-loop for n from 1
                    if (> (* n n 2) i)
                    do (cl-return-from 'fin i) end
                    if (eu7-isprime (- i (* n n 2)))
                    return t)))
=> 5777