Project Euler's Problem Number 88

Question

I am tackling Project Euler's problem number 88, which in a nutshell reads:

Let $S_n$ be the set of sequences of natural numbers $(s_1,s_2,...,s_n)$ where $s_1\leqslant s_2\leqslant\cdots\leqslant s_n$ and $$ \sum s_i=\prod s_i.\tag{*} $$ Observe that $$\begin{align} S_2&=\{(2,2)\},\\ S_3&=\{(1,2,3)\},\\ S_4&=\{(1,1,2,4)\},\\ S_5&=\{(1,1,1,2,5),(1,1,1,3,3),(1,1,2,2,2)\},\quad\text{and}\\ S_6&=\{(1,1,1,1,2,6)\}. \end{align}$$ Moreover, let $\text{min }S_n$ be the smallest sum of the elements of the sequences in this set. For example, $$ \text{min }S_5=8. $$ What is the sum of the elements of $$ \bigcup_{i=2}^{12000}\{\text{min }S_i\}? $$ If $6$ replaced $12000$ above, the answer would be $30$.

I conjectured that an element of a sequence in $S_n$ is no greater than $n$, and obtained $S_n$ by computing all natural-number sequences $s_1\leqslant s_2\leqslant\cdots\leqslant s_n\leqslant n$ and picking those that satisfy $(*)$.

The program runs perfectly for small $n$. However, when I tried to answer the boldface question, my program ran for hours with no result... and kept going. I shut it down when I discovered that there are

$$ \binom{23999}{11999}=\text{number with }7223\text{ digits} $$

natural-number sequences $s_1\leqslant s_2\leqslant\cdots\leqslant s_{12000}\leqslant12000$.

Since I cannot wait until the end of the universe, could someone give me a better alternative on how to approach this problem? Could I perhaps halt computing sequences when a certain condition is met?

Edit 1: I just conjectured that $\text{sum }S_n\leqslant2n$. I will now use this to crop my number of brute-force sequences.

Edit 2: The speed improved, but it was not enough...

Answer 1

I ended up opting for the following dynamic-programming approach (spoilered):

I computed all greater-than-one natural-number sequences $(s_1,s_2,...,s_n)$ where $s_1\leqslant s_2\leqslant \cdots\leqslant s_n$ and $\prod s_n\leqslant2n$, keeping the minimum value of $S_m\mapsto\prod s_n$, where $m=n-\sum s_n+\prod s_n$.

Answer 2

Since I cannot wait until the end of the universe, could someone give me a better alternative on how to approach this problem? Could I perhaps halt computing sequences when a certain condition is met?

Yes. You're trying to optimise, so you can stop computing sequences when you find one which is provably optimal.

That may sound trite, but think about it carefully.