Here comes the II. quest from Google Treasure Hunt. Maybe it sounds very simple, and algorithm what we’ve (Szakál Károly (ftnkaresz /at gmail /dot com) and I) used isn’t so difficult, but after 3 hours of hard-coding, what we got? A full stack error with 2GB RAM. 😉

Find the smallest number that can be expressed as

the sum of 3 consecutive prime numbers,

the sum of 9 consecutive prime numbers,

the sum of 253 consecutive prime numbers,

the sum of 781 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).

Recursion is very bad thing in programming. It isn’t requires deeper analysis of problems, there is enough to make good type definitions, a good algorithm with some recursive calls and return statement and finally there recursion will solve the problem for you. Okay! 🙂

The main goal of Data Structure and Algorithms is how to solve problems without recursive calls, and how to avoid the whole recursion.

The first solution made without recursion in programming language C. The main part of this program is an infinite while loop, what terminates itself if the right prime sum found:

while(1) { switch (r) { case 0: result=PrimSum(previousPrime,1063,&previousPrime); ix=0; nextPrime=2; r=sum(nextPrime,1063,result); break; case 1: ix++; if (!(ix<5)) { return 0; } nextPrime=2; r=sum(nextPrime,array[ix],result); break; case 2: r=sum(nextPrime=NextPrim(nextPrime),array[ix],result); break; } }

Finally, our number is: 6304483.