Consecutive prime sum


Fork me on GitHub
2015-01-14

Problem 050: Consecutive prime sum

Description:

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?


Solution:
v          // Project Euler - Problem 50
# ... #
. . . .
.  .  .
. . . .
# ... #

>"d"45**:10p5"d"*:20p*00p230p" ":03p13pv                       >040p030p>>30g1+:30p:10g%\10g/1+g"X"-#v_30g40g:1+40p:10g%\10g/1+p00g30g`#v_v
v                                      <                      _^#`g03g00<^                           <                                  < 0
>"X"30g:10g%\10g/1+p30g>30g+:00g\`       #v_$>30g1+:30p:10g%\10g/1+g" "-|v                    p091 p080 p07-10 p060 p+1/g01\%g01:p04:-1g04<
   >90g"= ",,.@        ^p+1/g01\%g01:\" ":<  ^                          <v                              p08<
                                                                         >70g1+:70p:10g%\10g/1+g80g+:00g\`#^_70g1-70p$v
vp05g04g08                                                                           <                               <<
>:50g\50g:10g%\10g/1+g-#v_$. @              >80g60g1-:10g%\10g/1+g+70g:10g%\10g/1+g-v^p09*-10g09<p07-1g07p08-g+1/g01\ %g01:g07g08<
^              p05-1g05<_>$060g90g+`#v_90g1-|                                       >:00g\`!#v_8 0p90g:60g+60p70g+70p^>90g1-     |
                                            >80g60g:10g%\10g/1+g-70g1+:10g%\10g/1+g+^        $  ^p06+1g06p08-g+1/g01\% g01:g06g08<
                                     >                                                       >                        ^
This program is too big to display/execute here, click [download] to get the full program.

Explanation:

My first approach here was a simple brute force algorithm, but that one was far too slow. So I needed an more intelligent algorithm. And I have to say the one I came up is pretty quick and I like the concept that lies behind it.

First I calculated the primes from 0 to 1 000 000.

Next I calculated the maximum chain (starting by the first prime 2) with a sum less than one million.

Now think of all the primes laid down in an array side by side:

1) We move our chain from left to right until the sum exceeds one million (the movement is a really cheap operation: take the previous sum, subtract the most left prime and add the new prime from the reight side).

2) Then we shorten the chain length by one as we remove the most left prime.

3) After that we do the movement back wards (from right to left) until we end up at the left end of our prime array.

4) Then we again shorten the chain (this time by removing the right tail) and start over again (by moving right).

X) In every step we test if the current sum is a prime number and if so we print it and terminate the program.

OOOOOOOOOOOOO  // the prime array
#####OOOOOOOO  // our chain
O#####OOOOOOO  // move right
OO#####OOOOOO
OOO#####OOOOO  // until sum > MAX_VALUE
OOOO####OOOOO  // shorten left
OOO####OOOOOO  // move left 
OO####OOOOOOO 
O####OOOOOOOO 
####OOOOOOOOO  // until left side is hit
###OOOOOOOOOO  // shorten right
O###OOOOOOOOO  // repeat until prime is found

This algorithm works because we first test every possibility with maximum chain length, and then every with length = maximum - 1 and so on and so on. So the first prime that we find is from the longest possible chain.

There are two nice things about this algorithm:

  • We don't need to calculate an extreme amount of prime sums. The step from the sum of one chain to the next is literally only an addition and an subtraction
  • Because we start with the longest chain and reduce its length in every step, the first prime we find is directly our optimal result.

Interpreter steps: 180 368 553
Execution time (BefunExec): 30s (5.84 MHz)
Program size: 2000 x 512
Solution: 997651
Solved at: 2015-01-14



made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript