# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1488155896 0
# Node ID 6124d264353e0a25bf79150fe6c93b2660846e8c
# Parent  e7d5fdbc48b4fbf4606ee63bb219bc609da84379
Problem 46

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`."