# Project Euler with Befunge

# 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:**

# ... #

. . . .

. . .

. . . .

# ... #

>"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 |