Project Euler 88: Exploring minimal product-sum numbers for sets of different sizes.

Based on the number of people who have solved Problem 88 of Project Euler it seems to be a rather difficult problem. At the time of writing 2661 people have solved this problem. This post should show you that in reality the problem is not that difficult. That being said I spent the majority of a week before I got the right insights to solve it. The problem reads

A natural number, N, that can be written as the sum and product of a given set of at least two natural numbers, {a1a2, … , ak} is called a product-sum number: N = a1 + a2 + … + ak = a1 x a2 x … x ak.

For example, 6 = 1 + 2 + 3 = 1 x 2 x 3.

For a given set of size, k, we shall call the smallest N with this property a minimal product-sum number. The minimal product-sum numbers for sets of size, k = 2, 3, 4, 5, and 6 are as follows.

k=2: 4 = 2 x 2 = 2 + 2
k=3: 6 = 1 x 2 x 3 = 1 + 2 + 3
k=4: 8 = 1 x 1 x 2 x 4 = 1 + 1 + 2 + 4
k=5: 8 = 1 x 1 x 2 x 2 x 2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1 x 1 x 1 x 1 x 2 x 6 = 1 + 1 + 1 + 1 + 2 + 6

Hence for 2≤k≤6, the sum of all the minimal product-sum numbers is 4+6+8+12 = 30; note that 8 is only counted once in the sum.

In fact, as the complete set of minimal product-sum numbers for 2≤k≤12 is {4, 6, 8, 12, 15, 16}, the sum is 61.

What is the sum of all the minimal product-sum numbers for 2≤k≤12000?

Okay, that doesn’t sound too easy does it? Well I guess you wouldn’t be here if it was too easy. If you don’t want the full solution but just some insights into the maths you need to solve it, just read the first part.

Mathematical insights into the problem

The first insight we should get is that if we have a set of factors say {2,3,4} we get that 234 = 24 and 2+3+4 = 9. Something that isn’t exactly a product-sum like we are looking for. However, we can add ones which doesn’t change the product but change the sum. Indeed if we add 24-9 = 15 ones we will get a product sum with 18 factors. In other words any set of factors can be converted into a product-sum for k = “product of factor” – “sum of factors” + “number of factors”. Whether this is minimal or not is another question which we wont answer just yet.

The second insight we might get is that the minimal product-sum for k is larger than or equal to k since the minimal product-sum consist of k ones which sums to k. The upper limit for the minimal product sum for k is 2k. The reason is that we can always use the factors {2,k} this gives us the product 2k and the sum 2+k. By adding k-2 ones we end up with a valid product sum for k which equals 2k. In other words the minimal product-sum (mps) for k is kmps(k)2k.

With these two insight we should be able to find the solution for the problem.

Creating the solution

Basically we need to factorize all numbers between 2 and 24000 in order to check if these factorizations  are a minimal product sum of some k. However, finding all factorizations of a number is not necessarily an easy task to do. And to be honest I haven’t found a good algorithm for doing that. There is a bit about integer factorization at Wolfram.

So I took another approach instead. I generated all factorizations from the factors instead starting at 22, 23,…,212000. Then 33,34,….38000 and so on until I reached . After that I needed to check all factorization with 3 factors starting with 222, 223,…,226000. And so on. The upper limit of factors we need is in order to generate all factorizations for all numbers from 2 to 24000.

The easy way to do that would be to have 14 for loops inside each other, but I wanted a bit more of a generic solution so I coded it in a while loop with a counter to jump up and down in the array to increment the factors as needed. I have tried to add comments in the loop in order to explain what I do. Basically it is just a bunch of logic in order to generate the sequence starting with 2*2 and so on.

Once we have a factorization we can calculate the corresponding k and check if the found solution is better than the previously best solution starting with a solution of 2k.

C# doesn’t have log2 built in, but the nice little logarithm rule is that we can calculate it using log10 instead. In reality what we are trying to do is solve the following equation for x

The easy way to do it is to use log2 and get

and since log2(2) = 1 then we have the solution. However since we only have log10 and log we have to use one of them and instead we can isolate x as

I know this part is trivial for some people, but sometimes I like to cover the basics for my self to remember where the rules come from.

I have used linq a bit in this solution as it is so much easier to initialise the array holding the product-sums that way as well as pulling out distinct values and summing them in the end.

The C# code looks like

```int maxK = 12000;
int maxNumber = 2 * maxK;

int numFactors = (int) (Math.Log10(maxNumber) / Math.Log10(2));
int[] factors = new int[numFactors];

int[] k = Enumerable.Range(0, maxK+1).Select(x => x * 2).ToArray();
k[1] = 0;

factors[0] = 1;
int curMaxFactor = 1;
int j = 0;

while (true) {
if (j == 0){
//at first factor
if (curMaxFactor == numFactors)
//Used all the factos we can
break;

if (factors[0] < factors[1]) {
//can increment
factors[0]++;
} else {
curMaxFactor++;
factors[curMaxFactor - 1] = int.MaxValue;
factors[0] = 2;
}

j++;
factors[1] = factors[0]-1;
} else if(j == curMaxFactor-1){
//At the max factor
factors[j]++;
int sum = 0;
int prod = 1;
for (int i = 0; i < curMaxFactor; i++) {
prod *= factors[i];
sum += factors[i];
}

if (prod > maxNumber) {
//Exceed the limit so go back
j--;
} else {
//Check the result
int pk = prod - sum + curMaxFactor;
if (pk <= maxK && prod < k[pk]) {
k[pk] = prod;
}
}
}else if (factors[j] < factors[j + 1]) {
//increment the reset the next factor
//and go up
factors[j]++;
factors[j+1] = factors[j]-1;
j++;
} else  if(factors[j] >= factors[j + 1]) {
//Need to go further back
j--;
}
}
int result = k.Distinct().Sum();
```

If you are really quick at reading through the sixty something lines of code you might notice that I am generating the sum and product each and every time, and we should be able to store that. Furthermore you have noticed that I could possibly lower the upper bound of 24000 since it is likely that the minimal product-sum is smaller for the large numbers and thus I don’t need to check up to 24000. However, the code runs as

```The sum of minimal product-sum numbers is 7587457
Solution took 15,2543 ms
```

So I am quite satisfied with the solution speed. I tried adding code to lower the upper bound, but it took more time to lower it, than it did to do the actual calculations. Keeping track of sum and product is not something I have tried implementing. But be my guest and see if it can yield a performance boost.

Wrapping up

I am pretty proud of having solved this problem. It took me a good while to do so even after the first insight which came rather quickly. The second insight I wrote about here gave me the upper bound I needed to go through the solution space. I hope that you got something from this, whether you solved it on your own, or you ended up giving up.

The final solution is really fast so I think we are just about right on it. You can find the source file here. In case you want all of it.

Based on the blog image apparently we turned left at the junction on this pretty amusing sign found by Brent Moore who shared it under the creative commons license.

Posted by Kristian

SuprDewd

Well done! You should be proud.

I had come up with first insight, but not the second one. Great explanation, and I’m sure I can implement a solution for myself now.

By the way: Math.Log(n, b) returns the base-b logarithm of n in C#.

Kristian

Hi SuprDewd

Thanks, I am pretty proud that I managed to solve this. It did take some time though. I think you could possibly implement it your self based on the first section of the post. That would still mean some thinking then.

And thanks for the Math.log explanation. I didn’t know. How do you figure those things out? I try to use the code completion, but yet these things fails me miserably.

/Kristian

SuprDewd

Haha. I have no idea how I know all these things 🙂 But I would guess that Visual Studio’s IntelliSense has something to do with it.

Kuko

Hi,

I tried a different way. I used a recursive function to compute all possible factorizations for a given number N which has at least 2 factors. For each one of these I found for which value of K, the number N would be a candidate for the product-sum number. For example:

If n = 20, the first factorizaion is f1 = 2 x 2 x 5, so it has 3 factors and its sum is equal to 9… so for the value K = 3 + 20 – 9, the number 20 is a possible candidate to be the product-sum number of size K = 14.

Then we do the same for the next factorization.. f2 = 2 x 10, so it has 2 factors and its sum is 12, so for K = 2 + 20 – 10 = 12, number 20 is candidate to be the product-sum number for K = 12. And so on.

We do this for all numbers until we get the product-sum number for the limit of K <= 12000. In the process we might compute this number for many values which are greater than 12000, but these ones must be ignored.

My C++ solution needs up to 7 seconds to find the solution.

Kristian

Hi Kuko

I thought about the same approach, but I couldn’t wrap my head around factoring each number the way you describe. From your description I do think that we end up with more calculations than in the method I have used. I am not sure though.

/Kristian

Hey, great article.
However, I can’t understand why your algorithm is giving 36 for k=29.

All the factorizations I’d come up with are:
[[36], [2, 18], [2, 2, 9], [2, 2, 3, 3], [2, 3, 6], [3, 12], [4, 9], [6, 6]]

So, possible k’s are:
k = 36 – 36 + 1 = 1
k = 36 – 20 + 2 = 18
k = 36 – 13 + 3 = 26
k = 36 – 10 + 4 = 30
k = 36 – 11 + 3 = 28
k = 36 – 15 + 2 = 23
k = 36 – 13 + 2 = 25
k = 36 – 12 + 2 = 26

Am I missing something?

P.S. I’m trying to solve this problem for a while now. Can’t understand
why my answer is incorrect. 🙂

Kristian

It is because we have

3*3*4*(26 ones) = 3 + 3 + 4 + (26 ones)

which is also a factorization you are missing.

Thanks, mate! That solved the problem with my factorizer.
And as a result I’ve got the correct answer!

JohnRobin

There is a far easier way to solve this. Instead, initialize a set K = [2,12000] and iterate upward trough N. if any N has any product-sum still in K, it is a valid minimal, and so added to a set Ns.

when K is empty, terminate, sum up Ns

quick even in python

Shimo

I have a code but doubt if it runs for large numbers. Can anyone give me the correct outputs for some large numbers>10000, so that I can test my code.

Jean-Marie Hachey

Hi Shimo !

Here are some outputs calculated with Kristian’s code :

http://www.mathblog.dk/files/euler/Problem88.cs

___

Value of k (output)

10000 (5441890)

12000 (7587457)

15000 (11350366)

20000 (18858239)

25000 (28129601)

30000 (38595063)

35000 (50543324)

Shimo

Thanks Jean, Thanks a lot.

Antonio

For the “factorization” approach, you don’t actually need to find ALL factorizations, just split into 2 factors N=ab, with a 0, N := N+1 and loop

Antonio

For the “factorization” approach, you don’t actually need to find ALL factorizations, just split into 2 factors N=ab, with a≤b. That is pretty easy to do with a list of prime numbers and a couple loops.

Approach:
– create a vector to store { {k=# factors, s=sum of factors} }: FS[]
– create a vector to store the minimum N for each k: KN[]
– Starting at N=2, R=Kmax
— factor N = ab, and merge FS[N] = {{1,N}, FS[a][i]+FS[b][j] } for all a,b,i,j
e.g. F[2] = { {1,2} }
F[3] = { {1,3} }
F[4] = { {1,4}, FS[2][1]+FS[2][1] } = { {1,4}, {2,4} }
F[8] = { {1,8}, FS[2][1]+FS[4][1,2] } = { {1,8}, {2,6}, {3,6} }

— As you build up each entry {k, s}, check if KN[k+N-s] has already be assigned. If not, KN[k+N-s] = N, R := R-1
– If R > 0, N := N+1 and loop

Richard

I wrote my own solution which was logically correct but would have taken literally weeks to run to completion. Then I converted your code from C# to C and it ran in 6 milliseconds! The only part I had to rewrite from scratch was the last part to calculate the total which I did as follows:

qsort(k + 2, maxK – 1, sizeof(int), MyComp); //sort the array to make detecting duplicates easier
for (int i = 2; i <= maxK; i++) {
if (((i < maxK) && (k[i] != k[i + 1])) || (i == maxK))
result += k[i]; // add unique (non-duplicate) values to result
}
printf("The sum of minimal product-sum numbers is %d\n", result);

Valent

Thanks for some ideas (add ones to product). But I don’t like this “factorization” method, so I used heavyweight brute-force for checking all possible sequences of 14 numbers. It took 100ms on Java. Mine is not best solution but it works.

Thanks for some hints to solve this problem!
By the way, My program (made it myself) found that there is 20 when k=10; (8 ones) + 2 + 10 = (8 ones) * 2 * 10 = 20.
But, the problem says there are {4, 6, 8, 12, 15, 16}, when 2<=k<=12, no 20 in there.

Am I doing something wrong?