Loading...
Project Euler 88: Minimal product-sum numbers
Euler 88 Problem Description
A natural number, N, that can be written as the sum and product of a given set of at least two natural numbers, {a1, a2, … , ak} is called a product-sum number: N = a1 + a2 + … + ak = a1 × a2 × … × ak.
For example, 6 = 1 + 2 + 3 = 1 × 2 × 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 × 2 = 2 + 2
k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3
k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4
k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1 × 1 × 1 × 1 × 2 × 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?
Analysis
Our original DP solution markedly improved with ideas from the PE forums. This is very similar to Euler’s solution with improved timing and storage.
Project Euler 88 Solution
Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 88 Solution Python 2.7 source.
Afterthoughts
-
No afterthoughts yet.
Hi Mike, i am a high school student. I read your code for several times but still cannot understand how the recursion works. Can you explain it for me? It really makes me confused.
Posted by Chaozy Z | March 13, 2019, 2:30 AMYou do need the kmax = 12000 + 1, otherwise you miss the last element. The indexing on the list n will go from 0 to 11999. You miss k = 12000.
Think of it as the same range(n) not including n in the list.
Same way when you run it with kmax = 12. You only get the right answer because n for both k = 11 and k = 12 are both 16. So missing the final value of k still gets you the correct answer. I suspect that n for k = 12000 is the same value as that for a lower value of k. So you still get the right answer there. And somehow not overshooting with k = 12000 does not impact the sum.
I think the solution will be to just overshoot kmax by some amount then trim the tail of the list when you do the set conversion.
Posted by Larry C | August 9, 2014, 9:42 AMGood catch Larry. I’m not exactly sure why I was adding one to the kmax var, but when I remove it it works for kmax=12 and kmax=12000.
Now, kmax=6 requires an initial call to prodsum as prodsum(1,2,0,2) which is the overshoot solution you proposed.
Let me look into this over the weekend. I must have changed something over the years and didn’t check it against other cases.
Thanks for finding this. If you ever find a problem with my solutions your analysis is always welcome.
Posted by Mike Molony | August 9, 2014, 8:43 AMWhile trying to understand your algorithm, and I am still working on that, I think I found a glitch.
I ran it with kmax = 12 + 1, the example in the problem statement and got the answer of 87 instead of 61 as given in the problem statement.
It looks like it is returning the wrong value for k = 12. Your algorithm gives 26 at that point rather than the correct answer of 16. It is not until I get up to running the algorithm for kmax = 15 + 1 that it returns the correct value of 16.
The nature of your algorithm is such that stopping at kmax does not ensure the correct solution for all values of k < kmax. You have to overshoot kmax by some amount to get them all correct.
Posted by Larry C | August 9, 2014, 6:43 AM