# Product-sum numbers [Project Euler Problem 88]

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?

This is Project Euler Problem 88.

This is the first problem where I got totally stuck. I did my research and found an interesting and useful paper When the sum equals the product (pdf) by Leo Kurlandchik and Andrzej Nowicki.

There are some relevant theorems in this paper but despite having this information at my disposal and dedicating time and brain power to this problem I was unable to solve it. I simply couldn't crack it. Or rather, I found a solution but it would take approximately 48 hours to terminate so I knew something was missing.

Eventually I gave up and cheated by doing a web search. This was a huge mistake. I'm so disappointed with myself for giving up. I managed to solve all the previous problems on my own with relative ease when I took the time and sat down and thought them through.

The most illuminating post I could find on this problem had a solution written in a programming language I'm not familiar with so at least I got the opportunely to implement my own solution in Python and thus understand what was going on but I view this as a major failure on my part since the solution was so easy in hindsight. It is discouraged to publish writeups so I'll refrain from discussing the actual solution any further.

I hate the feeling when I should be able to solve something but can't. I of course understand that you will sooner or later get to a problem where you are completely stumped but I just didn't expect it to happen so early on. This kind of took the fun out of Project Euler for me. I'll keep at it and we'll see how it goes.

Before publishing this post I got back up on the horse and did two more problems. Problem 89 was easy and I managed to solve Problem 90 (rated at my current maximum difficulty 40%!) in under an hour. I did some fuckups double counting stuff while figuring out the combinatorics as per usual but maybe there is still hope.