This goes as my solution to the same problem as also quoted by shanky singh a.k.a. Shashank singh.

The problem goes as

Find the smallest number that can be expressed as
the sum of 5 consecutive prime numbers,
the sum of 21 consecutive prime numbers,
the sum of 25 consecutive prime numbers,
the sum of 847 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).

My solution:

well shanky singh, your approach wont work and is high in both time and space complexity in the sense that you are deviating from the main problem at hand What I suggest as a solution is a recurring solution or we may have to use the backtracking algorithm, which by now I have forgotten the ways to do it.

But my algorithm will work like this

Take a list of lets say some 1,00,000 first consecutive prime numbers now traverse the list with a window size of 847 and calculate its sum. Then proceed forward with checking if the sum is also a prime or not. once confirmed, move further from the end of the window position. i.e. if the window start position is at 3 and the size is 847, then start now from 850th position in the list and this time the window size will be 25. proceed forward with the same logic and compare the sum with that of those 847 primes. now moving further from the end of the size 25 window and selecting 21 window size, go for the sum , sliding the window until the sums are the same and in the finally taking up the size 7 window from there.

But just now as soon as i finished writing this post, i figured that this algorithm may not work a expected, the reason being when we are moving from window size 25 to 21 we are skipping all the primes in between the start of window-21 and window-25. It may so happen if we start from the position (start of window-25 + (25-21) ) we get the sum even before leaving the boundaries of the window-25, and so the solution may lie in the overlapping zones of these two windows. The reason that I propose for such an anomaly is this that when we are skipping a window or starting a new window from the end of the previous window, we should also see if the difference between the size of the windows should be greater than the size of the smaller window. I am not very much sure of this algorithm to work or not, but would definitely like to accept any changes and suggestions. Shanky Singh, you should better be suggesting something to this algo

Start Slide Show with PicLens Lite

This entry was posted on Friday, November 7th, 2008 at 4:10 pm and is filed under Google, programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.