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

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

Written by on 31 December 2011

Topics: Project Euler

In problem 77 of Project Euler we are asked the following question


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?

This question is actually very similar to the problem we just solved in Problem 76 except that it asks us to find a number with a certain property, instead of asking what property a certain number have.

I took the easy solution and modified the solution for problem 76, to search for the first number with a solution larger than 5000. In order to do that we need to make two changes.

  1. Instead of just asking for the target of 100, we will start at 2 and then run the algorithm untill we find the correct solution
  2. Instead of using all integers between 1 and 99, we need an array of primes. This is similar to what we did in problem 31 with currency denominations

These changes can be made in the C# and results in the following code

int target = 2;           
int[] primes = ESieve(2, 1000);
          
while (true) {
    int[] ways = new int[target+1];
    ways[0] = 1;

    for (int i = 0; i < primes.Length; i++) {                    
        for (int j = primes[i]; j <= target; j++) {
            ways[j] += ways[j - primes[i]];
        }
    }
                                
    if (ways[target] > 5000) break;
    target++;
}

Which gives us the following result

The first number written in over 5000 ways is 71
Solution took 0,6296 ms

My biggest surprise was actually that it was a really small number. I don’t know what I should have expected, but I found it to be much smaller than I would have expected. The execution time is fine for this problem I think.

Wrapping up Problem 77

Once again I have made a really short description for the problem, since I think everything is covered in previous solutions, and once we see the idea the changes to the code are almost trivial. I know that sounds snobbish, but really the main thing here is getting the idea.

You can find the full source code here.

The blog image is provided by Bob Rosenbaum who shared it under the creative commons license.

4 Comments For This Post I'd Love to Hear Yours!

  1. Guy says:

    Just out of curiosity- why didn’t you re-use the values you already found? Instead of allocating a new ‘ways’ array (And wrapping the process inside a while loop), couldn’t you keep it? And then iterate it in order to find a value greater than 5000?

  2. Kristian says:

    The problem with that is that I don’t have a fixed upper limit, so thats why I do what I do. But I think you are right that I could reuse a good part of the last area.

  3. DiMa says:

    Hi,
    i don’t really know about the optimizations of C# compiler for accessing arrays.

    But you could even optimize a litte bit by replacing:

    for (int i = 0; i < primes.Length; i++) {
     for (int j = primes[i]; j <= target; j++) {
      ways[j] += ways[j - primes[i]];
     }
    }
    

    with:

    for (int i = 0; i < primes.Length; i++) {
     int j = primes[i]
     if(j > target) {
       //leave the loop, also: primes[k] > target for all k > i, 
       break;   
     }
     int p = j;
     for (; j <= target; j++) {
      ways[j] += ways[j - p];
     }
    }
    

    Just a small optimization to avoid checks in the inner for-loop.
    Do know some good book on “Dynamic Programming” ?
    Currently I need some time to understand your solutions ?

  4. Kristian says:

    Hi DiMa

    Good idea to break out at that point. However, the overhead of not doing so is in this case rather small. But still it is an optimization of the code speed.

    I don’t have any really good references for dynamic programming. It has sort of snuck in on me at some time, and now it seems to “just” another tool in the box.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.