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 + 2What 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.
- 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
- 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.
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?
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.
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 ?
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.
I realize that it was a long time ago that you did this. But an optimization could be to do a naive prime check on the current target and if it is a prime, append it to primes. Seems like you’ll get a 200-300X improvement from that.
can anyone suggest me the solution of the above problem in matlab