## 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`