## Google Treasure Hunt 2008 Puzzle 4

### April 14, 2009

This puzzle comes from the 2008 Google Treasure Hunt:

Find the smallest number that can be expressed as the sum of 7 consecutive prime numbers, the sum of 17 consecutive prime numbers, the sum of 41 consecutive prime numbers, the sum of 541 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 task is to find the number. When you are finished, you can read or run a suggested solution, or post your solution or discuss the exercise in the comments below.

Pages: 1 2

### 11 Responses to “Google Treasure Hunt 2008 Puzzle 4”

1. jcs said

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

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[/sourcecode]

3. Vaibhav Bansal said

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

for (int i=3; i<=8000000; i+=2) {
if(isNumberPrime(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

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

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)
```
6. 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

7. ftt said

``` let divides divisor number = divisor <> number && number % divisor = 0```

``` let rec sieve multiples potential_primes = match multiples with | first :: rest -> sieve rest (List.filter ((divides first) >> not) potential_primes) | [] -> potential_primes let primesUpTo n = let upper_bound = int (sqrt (float n)) let candidates = 2::[3 .. 2 .. n] sieve (List.takeWhile (fun n -> n < upper_bound) candidates) candidates let calculate_sums (numbers: list) max_sum n = Seq.windowed n numbers |> Seq.map Seq.sum |> Seq.takeWhile (fun sum -> sum Set.ofSeq let solve windows upper_bound = let primes = primesUpTo upper_bound let max_prime = List.rev primes |> List.head let sums = windows |> Seq.map (calculate_sums primes max_prime) Set.intersectMany sums |> Set.minElement ```

```solve [7; 17; 41; 541] 10000000 ```

8. ftt said

Solution in F#:

``` let divides divisor number = divisor <> number && number % divisor = 0```

``` let rec sieve multiples potential_primes = match multiples with | first :: rest -> sieve rest (List.filter ((divides first) >> not) potential_primes) | [] -> potential_primes let primesUpTo n = let upper_bound = int (sqrt (float n)) let candidates = 2::[3 .. 2 .. n] sieve (List.takeWhile (fun n -> n < upper_bound) candidates) candidates let calculate_sums (numbers: list<int>) max_sum n = Seq.windowed n numbers |> Seq.map Seq.sum |> Seq.takeWhile (fun sum -> sum <= max_sum) |> Set.ofSeq let solve windows upper_bound = let primes = primesUpTo upper_bound let max_prime = List.rev primes |> List.head let sums = windows |> Seq.map (calculate_sums primes max_prime) Set.intersectMany sums |> Set.minElement ```

```solve [7; 17; 41; 541] 10000000 ```

9. ftt said

Ah, the whitespace is still broken. Oh well.

10. George Leake said

C#
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Numerics;

//Find the smallest number that can be expressed as
//the sum of 7 consecutive prime numbers,
//the sum of 17 consecutive prime numbers,
//the sum of 41 consecutive prime numbers,
//the sum of 541 consecutive prime numbers,
//and is itself a prime number

namespace PraxisPrimes1
{
internal class Program
{
private static int nPrimes = 1000000;
private static List primes = new List();

``````    private static void Main(string[] args)
{
Stopwatch clock = Stopwatch.StartNew();
MakePrimes(nPrimes);
long sum = 0;
if (Try(7, ref sum))
if (Try(17, ref sum))
if (Try(41, ref sum))
if (Try(541, ref sum))
{
long result = sum;
clock.Stop();
Console.Beep(800, 20);
Console.WriteLine("Result: {0}\nExecution time: {1} ticks (~{2}ms)", result, clock.ElapsedTicks, clock.ElapsedMilliseconds);
Console.WriteLine("Press any key to end");
}
}

private static bool Try(int n, ref long sum)
{
List<long> nums = new List<long>();
sum = 0;
long p = 0;
for (int j = 0; j < primes.Count; j++)
{
sum = 0;
for (int k = 0; k < n; k++)
{
p = primes[j + k];
sum += p;
}
if (primes.Contains(sum))
return true;
nums.Clear();
}
return false;
}

private static bool IsPrime(long n)
{
if (n == 2 || n == 3)
return true;
if (n < 2 || n % 2 == 0)
return false;
long max = (long)Math.Sqrt((double)n);
for (long i = 3; i <= max; i += 2)
if (n % i == 0)
return false;
return true;
}

private static void MakePrimes(int n)
{