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

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

Written by on 17 March 2012

Topics: Project Euler

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 2*3*4 = 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 2*2, 2*3,…,2*12000. Then 3*3,3*4,….3*8000 and so on until I reached . After that I needed to check all factorization with 3 factors starting with 2*2*2, 2*2*3,…,2*2*6000. 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 {
            //add another factor
            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.

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

  1. SuprDewd says:

    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#.

  2. Kristian says:

    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

  3. SuprDewd says:

    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.

  4. Kuko says:

    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.

  5. Kristian says:

    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

  6. N says:

    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. :)

  7. Kristian says:

    It is because we have

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

    which is also a factorization you are missing.

  8. N says:

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

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.