11
$\begingroup$

Falco had asked a question regarding sum equals to product ( Sum Equals Product)

I have a question in the orthogonal direction. Suppose $X_1,X_2,...,X_n$ are variables and we allow $X_i$'s to take only natural numbers. Look at the following Diophantine equation $X_1+X_2+ \dots + X_n = X_1 X_2 \ldots X_n$. Any solution of this equation satiesfies the property that the sum of the entries is equal to their product.

It is easy to see that for every $n$, there are only finitely many solutions of the above equation, denote that number by $f(n)$. It is easy to see that there is no absolute constant $k \in \mathbb{N}$ such that $f(n) < k$ for every $n$. (look at the sequence $x_n= n!+1$, then $f(x_n) > n$, for $n \geq 5$)

If $(x_1,..., x_n)$ is a solution of the above equation then we have $\prod_{i=1}^{n-1} x_i < n$. From here one can have a very crude bound for $f(n)$.

Question: 1) What is the best upper bound for $f(n)$? 2) Is there an asymptotic behaviour of $f(n)$ as $n$ tends to infinity.

$\endgroup$

2 Answers 2

7
$\begingroup$

D24 in Guy's Unsolved Problems In Number Theory: For $k>2$ the equation $$a_1a_2\cdots a_k=a_1+a_2+\cdots+a_k$$ has the solution $a_1=2$, $a_2=k$, $a_3=a_4=\cdots=a_k=1$. Schinzel showed that there is no other solution in positive integers for $k=6$ or $k=24$. Misiurewicz has shown that $k=2,3,4,6,24,114,174$ and 444 are the only $k<1000$ for which there is exactly one solution. The search has been extended by Singmaster, Bennett and Dunn to $k\le1440000$. They let $N(k)$ be the number of different 'sum = product' sequences of size $k$, and conjecture that $N(k)>1$ for all $k>444$. They find that $N(k)=2$ for 49 values of $k$ up to 120000, the largest being 6174 and 6324, and conjecture that $N(k)>2$ for $N>6324$. They also find that $N(k)=3$ for 78 values of $k$ in the same range, the largest being 7220 and 11874, and conjecture that $N(k)>3$ for $k>11874$; also that $N(k)\to\infty$.

Guy gives many references.

$\endgroup$
5
  • 1
    $\begingroup$ Apparently the bound has been pushed to 3,634,884,924 by Louis Marmet, see oeis.org/classic/A033179 $\endgroup$
    – Charles
    Aug 13, 2010 at 4:35
  • $\begingroup$ @Gerry: Thanks for your comments. You had mentioned things which are still conjectures. are you aware of some known results in these directions. $\endgroup$
    – N. Kumar
    Aug 13, 2010 at 6:42
  • $\begingroup$ This article jstor.org/pss/3219187 also discusses the problem and states that the above bound has been checked past $10^{10}$. $\endgroup$
    – dke
    Aug 13, 2010 at 12:13
  • $\begingroup$ @NK, no, all I know is what's in Guy's book. I tried to find more recent work, but maybe I didn't try hard enough. The Singmaster-Bennett-Dunn paper remains unpublished, though it seems from Singmaster's webpages that he's happy to mail out copies. I can't follow up the suggestion by dke since I won't have jstor access for a couple of days. $\endgroup$ Aug 13, 2010 at 13:24
  • $\begingroup$ Louis Marmet's work on the problem through 2005 is visible at marmet.org/louis/sumprod/index.html $\endgroup$ Aug 13, 2010 at 13:33
0
$\begingroup$

My Sage code for finding all solutions for a given number of terms may be interesting/helpful. It's quite fast; it takes about 10 seconds to solve $n=10^{9}$ and about 1 hour to solve $n=10^{12}$ (there are exactly 569 solutions). I've also included a CSV file for the solution counts from $n=2$ to $10^{6}$.

I find that $n=27744$ also has exactly two solutions, incidentally, and my total counts differ slightly from those given above.

Equal Product-Sum Puzzle GitHub

$\endgroup$
4
  • $\begingroup$ If it takes 10 seconds to find all solutions for $n=10^9$, then it would take something like $10^{11}$ seconds to find all solutions for all $n$, $1\le n\le10^{10}$. But comments elsewhere on the problem suggest that that calculation and more were done some years ago, so they must have had something much faster. $\endgroup$ Sep 27, 2014 at 23:52
  • $\begingroup$ There are some severe modulus restrictions on values of $n$ that could have unique solutions, so you only need to check a tiny fraction. Louis Mamet (mentioned above) discusses this in some detail. Also, once you find one additional solution beyond $\{2,n-2\}$ you can stop looking for more. $\endgroup$ Sep 28, 2014 at 13:38
  • $\begingroup$ 1. I don't see any Mamet above, though I do see a Marmet below. 2. So does this mean you are able to extend the bounds reported some years ago? $\endgroup$ Sep 28, 2014 at 13:51
  • $\begingroup$ That should be Louis Marmet. My code combined with the various modular restrictions could easily extend the current bound. But the conjecture is almost certainly true - the "mixing" appears to be good enough that there could be nice asymptotics. $\endgroup$ Sep 30, 2014 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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