## Google Treasure Hunt 2008 Puzzle 4

### April 14, 2009

We previously discussed a function that returns a list of the prime numbers less than or equal to *n*. We assume that the puzzle solution is less than 10^{7} and calculate both the list of primes and the largest prime:

`(define big-primes (primes #e1e7))`

`(define max-prime (car (reverse big-primes)))`

We calculate the lists of sums of *n* consecutive primes in a loop, keeping *n* primes in a list, repeatedly dropping the head of the list and adding the next prime to the end of the list, keeping track of the sums as we go, and stopping when the sum exceeds the maximum prime:

`(define (sums n)`

(let loop ((ps (take n big-primes))

(rest (drop n big-primes))

(s (sum (take n big-primes)))

(ss '()))

(if (< max-prime s) (reverse ss)

(loop (append (cdr ps) (list (car rest)))

(cdr rest)

(+ s (car rest) (- (car ps)))

(cons s ss)))))

Now we can make four lists of the sums of consecutive primes:

`(define sum7 (sums 7))`

(define sum17 (sums 17))

(define sum41 (sums 41))

(define sum541 (sums 541))

The puzzle answer is the intersection of the five lists:

`> (car (intersect sum7`

(intersect sum17

(intersect sum41

(intersect sum541 big-primes)))))

7830239

`Take`

, `drop`

and `sum`

are from the Standard Prelude. The intersection of two sorted lists of integers can be calculated as shown below:

`(define (intersect xs ys)`

(cond ((or (null? xs) (null? ys)) '())

((< (car xs) (car ys)) (intersect (cdr xs) ys))

((< (car ys) (car xs)) (intersect xs (cdr ys)))

(else (cons (car xs) (intersect (cdr xs) (cdr ys))))))

You can see the complete solution at http://programmingpraxis.codepad.org/PsUPfgmT.

Pages: 1 2

Here is a solution that makes no assumptions about the size of the solution and does not compute unnecessary sums. The primes module provides a stream (as in SICP) of primes and the primitive

`prime?`

;`push, pop`

, and`dotimes`

are Scheme implementations of the like-named Common Lisp macros.(use-modules (private primes)) ;for stream-of-primes, prime?

;;; Queue object that holds n consecutive primes and sums them

(define make-summing-queue

(lambda (n)

(let ((front '()) (back '()) (primes stream-of-primes))

(define popq ;just throw away the head of queue

(lambda ()

(unless (pop front)

(set! front (reverse back))

(set! back '())

(pop front))))

(define popp ;return the next prime

(lambda ()

(let ((p (str-car primes)))

(set! primes (str-cdr primes))

p)))

(dotimes (i n)

(push (popp) back))

(lambda (cmd)

(case cmd

((next) (push (popp) back) (popq)) ;shift sum

((fb) (format #t "front: ~s, back: ~s\n" front back))

((show) (princ (append front (reverse back))))

((sum) (apply + (append front back))))))))

;;; Find sums of primes

(define queues (list (make-summing-queue 541)

(make-summing-queue 41)

(make-summing-queue 17)

(make-summing-queue 7)))

(define run

(lambda (queues)

(let ((first (car queues)))

(while (not (prime? (first 'sum)))

(first 'next))

(let iter ((goal (first 'sum)) (rest (cdr queues)))

(cond ((null? rest) (first 'sum))

((= goal ((car rest) 'sum)) (iter goal (cdr rest)))

((< goal ((car rest) 'sum)) (first 'next) (run queues))

(else ((car rest) 'next) (iter goal rest)))))))

`;; (for-each (lambda (q) (q 'show)) queues)`

;; to see lists of primes

In Haskell:

package com.algorithm;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

public class Prime {

public static boolean isNumberPrime(long number) {

for (long i = 3l; i <= Math.sqrt(number); i += 2) {

if(number % i == 0) {

return false;

}

}

return true;

}

public static void main(String[] args) {

List primeNoList = new ArrayList();

primeNoList.add(1);

primeNoList.add(2);

for (int i=3; i<=8000000; i+=2) {

if(isNumberPrime(i)) {

primeNoList.add(i);

}

}

Map<Integer, List> sumConsecutivePrimeNos0 = sumConsecutivePrimeNos(7, primeNoList);

Map<Integer, List> sumConsecutivePrimeNos1 = sumConsecutivePrimeNos(17, primeNoList);

Map<Integer, List> sumConsecutivePrimeNos2 = sumConsecutivePrimeNos(41, primeNoList);

Map<Integer, List> sumConsecutivePrimeNos3 = sumConsecutivePrimeNos(541, primeNoList);

for (Integer smallestPrimeNo : primeNoList) {

if (sumConsecutivePrimeNos0.containsKey(smallestPrimeNo) &&

sumConsecutivePrimeNos1.containsKey(smallestPrimeNo) &&

sumConsecutivePrimeNos2.containsKey(smallestPrimeNo) &&

sumConsecutivePrimeNos3.containsKey(smallestPrimeNo)) {

System.out.println(“smallest prime No : ” + smallestPrimeNo);

System.out.println(“7 consecutive prime nos : ” + sumConsecutivePrimeNos0.get(smallestPrimeNo));

System.out.println(“17 consecutive prime nos : ” + sumConsecutivePrimeNos1.get(smallestPrimeNo));

System.out.println(“41 consecutive prime nos : ” + sumConsecutivePrimeNos2.get(smallestPrimeNo));

System.out.println(“541 consecutive prime nos : ” + sumConsecutivePrimeNos3.get(smallestPrimeNo));

break;

}

}

}

private static Map<Integer, List> sumConsecutivePrimeNos(int count, List primeNoList) {

Map<Integer, List> map = new HashMap<Integer, List>();

for (int i = 0; i < primeNoList.size() – count; i++) {

List consecutiveList = primeNoList.subList(i, i + count);

int sum = 0;

for (int primeNo : consecutiveList) {

sum += primeNo;

}

if (sum > primeNoList.get(primeNoList.size() – 1)) {

break;

}

if (isNumberPrime(sum)) {

map.put(sum, consecutiveList);

}

}

return map;

}

}

The solution above is implemented in java and the output is :

smallest prime No : 7830239

7 prime nos : [1118563, 1118567, 1118569, 1118599, 1118629, 1118653, 1118659]

17 prime nos : [460463, 460477, 460531, 460543, 460561, 460571, 460589, 460609, 460619, 460627, 460633, 460637, 460643, 460657, 460673, 460697, 460709]

41 prime nos : [190759, 190763, 190769, 190783, 190787, 190793, 190807, 190811, 190823, 190829, 190837, 190843, 190871, 190889, 190891, 190901, 190909, 190913, 190921, 190979, 190997, 191021, 191027, 191033, 191039, 191047, 191057, 191071, 191089, 191099, 191119, 191123, 191137, 191141, 191143, 191161, 191173, 191189, 191227, 191231, 191237]

541 prime nos : [11933, 11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011, 12037, 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109, 12113, 12119, 12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211, 12227, 12239, 12241, 12251, 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323, 12329, 12343, 12347, 12373, 12377, 12379, 12391, 12401, 12409, 12413, 12421, 12433, 12437, 12451, 12457, 12473, 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527, 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589, 12601, 12611, 12613, 12619, 12637, 12641, 12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713, 12721, 12739, 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823, 12829, 12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923, 12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007, 13009, 13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109, 13121, 13127, 13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187, 13217, 13219, 13229, 13241, 13249, 13259, 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337, 13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421, 13441, 13451, 13457, 13463, 13469, 13477, 13487, 13499, 13513, 13523, 13537, 13553, 13567, 13577, 13591, 13597, 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681, 13687, 13691, 13693, 13697, 13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759, 13763, 13781, 13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877, 13879, 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967, 13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081, 14083, 14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221, 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323, 14327, 14341, 14347, 14369, 14387, 14389, 14401, 14407, 14411, 14419, 14423, 14431, 14437, 14447, 14449, 14461, 14479, 14489, 14503, 14519, 14533, 14537, 14543, 14549, 14551, 14557, 14561, 14563, 14591, 14593, 14621, 14627, 14629, 14633, 14639, 14653, 14657, 14669, 14683, 14699, 14713, 14717, 14723, 14731, 14737, 14741, 14747, 14753, 14759, 14767, 14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831, 14843, 14851, 14867, 14869, 14879, 14887, 14891, 14897, 14923, 14929, 14939, 14947, 14951, 14957, 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073, 15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139, 15149, 15161, 15173, 15187, 15193, 15199, 15217, 15227, 15233, 15241, 15259, 15263, 15269, 15271, 15277, 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331, 15349, 15359, 15361, 15373, 15377, 15383, 15391, 15401, 15413, 15427, 15439, 15443, 15451, 15461, 15467, 15473, 15493, 15497, 15511, 15527, 15541, 15551, 15559, 15569, 15581, 15583, 15601, 15607, 15619, 15629, 15641, 15643, 15647, 15649, 15661, 15667, 15671, 15679, 15683, 15727, 15731, 15733, 15737, 15739, 15749, 15761, 15767, 15773, 15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859, 15877, 15881, 15887, 15889, 15901, 15907, 15913, 15919, 15923, 15937, 15959, 15971, 15973, 15991, 16001, 16007, 16033, 16057, 16061, 16063, 16067, 16069, 16073, 16087, 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183, 16187, 16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267, 16273, 16301, 16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381, 16411, 16417, 16421, 16427, 16433, 16447, 16451, 16453, 16477, 16481, 16487, 16493, 16519, 16529, 16547, 16553, 16561, 16567, 16573, 16603, 16607, 16619, 16631, 16633, 16649, 16651, 16657, 16661, 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747, 16759, 16763, 16787, 16811, 16823, 16829, 16831, 16843, 16871, 16879, 16883, 16889, 16901, 16903, 16921, 16927, 16931, 16937, 16943, 16963, 16979, 16981, 16987, 16993, 17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053, 17077, 17093]

Python:

Would it be ok if I repost a few of your posts so long as I provide credit and

sources back to programmingpraxis.com? My website is on the exact same topic as yours and my visitors could undoubtedly learn from much of the articles you give here.

Feel free to let me know if this would be fine.

Cheers