Programming Praxis

5 Responses to “Google Treasure Hunt 2008 Puzzle 4”

1. jcs said

   April 16, 2009 at 7:45 PM

   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

2. FalconNL said

   April 16, 2009 at 10:23 PM

   In Haskell:

   import Data.List
   import Data.Numbers.Primes
   
   main = print $ test [541,41,17,7,1]
   
   consecutivePrimes n = map (sum . take n) $ tails primes
   
   test = head . foldl1 (\a b -> filter (\x -> elem x $ takeWhile (<= x) b) a) . map consecutivePrimes
3. Vaibhav Bansal said

   April 6, 2012 at 12:13 PM

   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;
   }
   }
4. Vaibhav Bansal said

   April 6, 2012 at 12:14 PM

   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]
5. cosmin said

   October 30, 2012 at 5:49 PM

   Python:

   def sumOfPrimes(N):
   	isPrime, primes = (N + 1)*[True], []
   	for i in xrange(3, N + 1, 2):
   		if not isPrime[i]: continue
   		primes.append(i)
   		for j in xrange(i*i, N + 1, i):
   			isPrime[j] = False
   	s = [(sum(primes[0:7]),   0, 0,   7),
   		 (sum(primes[0:17]),  0, 1,  17),
   		 (sum(primes[0:41]),  0, 2,  41),
   		 (sum(primes[0:541]), 0, 3, 541)]
   	while True:
   		allEqual = True
   		for a in s:
   			if a[0] != s[0][0]:
   				allEqual = False
   				break
   		if allEqual and s[0][0] <= N and isPrime[s[0][0]]: return s[0][0]
   		m = min(s)
   		if m[0] > N or m[3] == len(primes)-1: return None
   		s[m[2]] = (m[0] - primes[m[1]] + primes[m[1] + m[3]], m[1] + 1, m[2], m[3])
   
   print sumOfPrimes(10000000)