# 6124d264353e

`Problem 46`
author Steve Losh Mon, 27 Feb 2017 00:38:16 +0000 e7d5fdbc48b4 735c2b5c9430 (none) src/euler.lisp src/primes.lisp

## Changes

```diff -r e7d5fdbc48b4 -r 6124d264353e src/euler.lisp
--- 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)```
```diff -r e7d5fdbc48b4 -r 6124d264353e src/primes.lisp
--- 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`."```