--- a/src/euler.lisp Mon Feb 27 00:26:54 2017 +0000
+++ b/src/euler.lisp Mon Feb 27 00:38:16 2017 +0000
@@ -278,7 +278,8 @@
(defun squarep (n)
"Return whether `n` is a perfect square."
- (= n (square (isqrt n))))
+ (and (integerp n)
+ (= n (square (isqrt n)))))
(defun triangle (n)
@@ -1368,6 +1369,30 @@
(for n = (triangle i))
(finding n :such-that (and (pentagonp n) (hexagonp n)))))
+(defun problem-46 ()
+ ;; 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×1²
+ ;; 15 = 7 + 2×2²
+ ;; 21 = 3 + 2×3²
+ ;; 25 = 7 + 2×3²
+ ;; 27 = 19 + 2×2²
+ ;; 33 = 31 + 2×1²
+ ;;
+ ;; 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?
+ (flet ((counterexamplep (n)
+ (iterate
+ (for prime :in (primes-below n))
+ (never (squarep (/ (- n prime) 2))))))
+ (iterate
+ (for i :from 1 :by 2)
+ (finding i :such-that (and (compositep i)
+ (counterexamplep i))))))
+
;;;; Tests --------------------------------------------------------------------
(def-suite :euler)
@@ -1418,6 +1443,7 @@
(test p43 (is (= 16695334890 (problem-43))))
(test p44 (is (= 5482660 (problem-44))))
(test p45 (is (= 1533776805 (problem-45))))
+(test p46 (is (= 5777 (problem-46))))
;; (run! :euler)
--- a/src/primes.lisp Mon Feb 27 00:26:54 2017 +0000
+++ b/src/primes.lisp Mon Feb 27 00:38:16 2017 +0000
@@ -126,6 +126,7 @@
:do (return nil)
:finally (return t)))))
+
(defun primep (n)
"Return (less slowly) whether `n` is prime."
(cond
@@ -136,6 +137,15 @@
((< n 100000) (brute-force-prime-p n))
(t (miller-rabin-prime-p n))))
+(defun unitp (n)
+ "Return whether `n` is 1."
+ (= n 1))
+
+(defun compositep (n)
+ "Return whether `n` is composite."
+ (and (not (unitp n))
+ (not (primep n))))
+
(defun primes-below (n)
"Return the prime numbers less than `n`."