Tuesday, June 03, 2008

Google Treasure Hunt 2008: Puzzle 4 (primes) solution

This is another one that lends itself to a nice solution in Common Lisp. It helps not to be too worried about efficiency in the beginning - "early optimization is the root of all evil". So I don't use Erastosthenes' sieve to enumerate primes, I just iterate over natural numbers (2, 3, k+2) and check for primality using a trivial PRIMEP. For each cardinality (number of consecutive primes that should be summed up), I maintain a vector of exactly that size, to be used as a ring buffer. Each time I get a complete sum-of-primes which is itself a prime, I note that this sum-prime can be represented as a consecutive-primes-sum of the given cardinality. When a number has as many entries as we have cardinalities, we have won.


;;; Question:
;;;
;;; Find the smallest number that can be expressed as
;;; the sum of 23 consecutive prime numbers,
;;; the sum of 33 consecutive prime numbers,
;;; the sum of 403 consecutive prime numbers,
;;; the sum of 1163 consecutive prime numbers,
;;; and is itself a prime number.
;;;
;;; For example, 41 is the smallest prime number that can be expressed as
;;; the sum of 3 consecutive primes (11 + 13 + 17 = 41) and
;;; the sum of 6 consecutive primes (2 + 3 + 5 + 7 + 11 + 13 = 41).
;;;
;;; Your answer: ____________
;;;
(in-package :noc)

(defun primep (n)
(let ((sq (truncate (sqrt n))))
(do ((k 2 (1+ k)))
((> k sq) t)
(when (zerop (rem n k))
(return nil)))))

(defun map-primes (fun)
(map-primes-1 fun 2))

(defun map-primes-1 (fun k)
(when (primep k)
(funcall fun k))
(map-primes-1 fun (if (= k 2) 3 (+ k 2))))

(defun make-vector-adder (size sum-fun)
(let ((vec (make-array (list size)))
(count 0)
(fullp nil)
(sum 0))
(let ((fun #'(lambda (k)
(when fullp
(decf sum (aref vec count)))
(setf (aref vec count) k)
(incf sum k)
(incf count)
(when (= count size)
(setq count 0)
(setq fullp t))
(when (and fullp (primep sum))
#+VERIFY
(when (= sum 5457701)
(format t "Sum of ~D consecutive primes:~% " size)
(dotimes (k size)
(format t " ~D" (aref vec (rem (+ k count) size))))
(terpri))
(funcall sum-fun sum)))))
fun)))

(defun solve (cardinalities)
(let ((prime-to-card (make-hash-table :test #'equal)))
(let ((adders
(mapcar #'(lambda (k)
(make-vector-adder
k
#'(lambda (sum)
(let ((cards
(cons k (gethash sum prime-to-card '()))))
(when (= (length cards) (length cardinalities))
(return-from solve sum))
(setf (gethash sum prime-to-card) cards)))))
cardinalities)))
(let ((iterator #'(lambda (k)
(dolist (adder adders) (funcall adder k)))))
(map-primes iterator)))))

;;; noc(38): (time (solve '(23 33 403 1163)))
;;; ; cpu time (non-gc) 2,480 msec user, 0 msec system
;;; ; cpu time (gc) 80 msec user, 0 msec system
;;; ; cpu time (total) 2,560 msec user, 0 msec system
;;; ; real time 2,747 msec
;;; ; space allocation:
;;; ; 10,128 cons cells, 13,369,008 other bytes, 0 static bytes
;;; 5457701