-1
$\begingroup$

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

$\endgroup$

closed as off-topic by user296602, Algebraic Pavel, jkabrg, loup blanc, Simply Beautiful Art Jan 18 '18 at 23:44

  • This question does not appear to be about math within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ They really don't want this. Answer posted. $\endgroup$ – Will Jagy Oct 23 '13 at 19:31
  • $\begingroup$ @WillJagy I was going to ask this question at stackoverflow.com but felt it was more mathematically-inclined. I understand the problem and have theoretically solved it, but due to our current lack of computing power, I thought someone could perhaps point me toward a heuristic or a better idea. $\endgroup$ – wjm Oct 23 '13 at 19:40
  • 5
    $\begingroup$ I'm voting to close this question as off-topic because this question is not consistent with the aims of Project Euler, which specifically encourages participants not to post their techniques like this. $\endgroup$ – user296602 Jan 18 '18 at 20:38
  • $\begingroup$ @user296602 dat necro $\endgroup$ – wjm Jan 18 '18 at 21:02
  • $\begingroup$ @Raptor It came up in a meta thread. $\endgroup$ – user296602 Jan 18 '18 at 21:03
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It sped up the program significantly, but it wasn't enough. I ended up opting for memoization, which worked. $\endgroup$ – wjm Oct 28 '13 at 15:14
0
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.