Prime summations

2015-08-28

Problem 077: Prime summations

Description:

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

Solution:

v00000 00  // Project Euler - Problem 77
XXXXXX
#####################################################################################################

#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################
#####################################################################################################

> "e" :10p 1 :20p*40p230p" ":02p12pvv03:+1g03<        >030p    0>::10g%\10g/2+g"X"-#v_:30g:1+30p:v
v                                  <># p# :#  v#     _^#`g03g04<|-g04:+1            <p+2/g01\%g01<
>"X"30g:10g%\10g/2+p30g>30g+:40g\`       #v_$^>10g%\10g/2+g" "-|>$30g:50p10g*>1-:0\:10g%\10g/4+pv
                       ^p+2/g01\%g01:\" ":<  ^                 <             ^_v#:              <
vp08"d"p07*"}("$                                                               <
0                                                   >061p31g>:0\`#v_:4+51g\g61g+61pv
>1+:11p021p031p>31g:50g-\2g:41p11g`!*!#v_11g41g-:51p|       ^-1                    <
^                           _v#!`g07g12<            >111g31g4+pv  >$21g61g:1v
               ^             ># 1# 1# g# .# @#         p13+1g13<p12+p+4g13g1<

Start

Pause

Reset

Download

Output:

Stack: (0)

Explanation:

For an extended explanation please look at problem-076, it's basically the same..

Yet again we remember already calculated values in an grid. The only difference is now that our y-axis is the prime index (We generate a few primes with an Sieve of Eratosthenes).

And once we find a number which count is greater five thousand we abort and print this number.

The only mayor difference to problem-076 is that now not every summand is valid. It is possible that you can use prime[7] but not prime[6]. So we have to look at each possible summand individually. This makes unfortunately the optimization where we remember the sum of all values invalid.