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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\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
    Commented 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
    Commented 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
    Commented 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$
    – Gerry Myerson
    Commented 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$
    – Gerry Myerson
    Commented 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

Improve this answer
$\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$
    – Gerry Myerson
    Commented 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$
    – Christopher D. Long
    Commented 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$
    – Gerry Myerson
    Commented 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$
    – Christopher D. Long
    Commented Sep 30, 2014 at 18:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .