;;; 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

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

Subscribe to:
Posts (Atom)