Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sum Equal Product

There are many articles in re this issue on the Web, although many are restricted to special cases (e.g., John Cook’s sum of tangents = product of tangents), and even some involving mixed numbers.

There is one excellent article in re: sum equal product written by two Polish mathematicians which is replete with wonderful proofs that I am not sophisticated enough to understand. (Kurlandchick & Nowicki, Nov `98)

Actually, my question is quite straightforward. Is there a formula or some kind of algorithm that can show which sums of positive, unequal integers equal their products?

Falco

share|improve this question
10  
There is an algorithm! Here it is. Loop through all the finite sets of positive integers, and for each one compute the sum and the product, and output "yes" if they are equal, and "no" if not. –  Kevin Buzzard Aug 10 '10 at 17:38
    
Richard Guy mentions the more general case in his book Unsolved Problems in Number Theory. In particular, k (the number of summands)can assume only certain values. Gerhard "Ask Me About System Design" Paseman, 2010.08.10 –  Gerhard Paseman Aug 10 '10 at 18:34
    
The Guy reference is to problem D24, pages 299-301 in the 3rd edition. Guy asks for solutions in positive integers, but does not require them to be distinct. –  Gerry Myerson Aug 10 '10 at 23:32
    
Gerry - if the problem is to solve the problem with only the unequal restriction removed, then aside from the trivial solutions $\\{n\\}$ we have solutions precisely for composite $n$. It is trivial to show that primes do not work, and for any composite $n$ we may take two non-trivial divisors $1 < j,k < jk = n$ and add the appropriate number of 1's. We have $j+k \le jk$, as $j, k \ge 2$ - this is just the inequality $(j-1)(k-1) \ge 1$. –  drvitek Aug 12 '10 at 1:02
    
drvitek, yes, but there are occasionally other solutions. E.g., 1, 1, 2, 2, 2, which is an extension of your construction. Guy asks not for values of $n$ but of $k$ (in the notation of your answer), and the problem is not so easily solved. Have a look at the book. –  Gerry Myerson Aug 12 '10 at 13:06

1 Answer 1

up vote 13 down vote accepted

Let the positive, unequal integers be $a_1 < a_2 < \cdots < a_k$ with $a_1+a_2+\cdots+a_k = a_1a_2\cdots a_k = n$. Obviously if $k = 1$ all positive integers work; suppose from now on that $k > 1$. Note that $a_k \ge k$. Then we have $a_1 + a_2 + \cdots + a_k < ka_k$, while $a_1a_2\cdots a_k \ge (k-1)!a_k$. So we must have $ka_k > (k-1)!a_k$, which means that $k > (k-1)!$. This means $k \le 3$. If $k = 2$, then we have $a_1 + a_2 = a_1a_2$, or $\frac{1}{a_1}+\frac{1}{a_2} = 1$. This can easily be seen to have only the solution $(2,2)$, which doesn't satisfy our hypothesis that the $a_i$ be unequal.

The case $k = 3$ is then the only tricky case. If $a_1 > 1$, then we have $a_1+a_2+a_3 < 3a_3$ and $a_1a_2a_3 \ge 6a_3$. So $a_1 = 1$. We then must find solutions to $1 + a_2 + a_3 = a_2a_3$. This can be rewritten as $(a_2-1)(a_3-1) = 2$, which as $a_2 < a_3$ are integers immediately gives $a_2 = 2, a_3 = 3$.

In summary, all possible solutions are $\{n\}$ for all positive integers $n$ and $\{1,2,3\}$.

History: this is definitely a classic problem; see for example 2006 USA Mathematical Olympiad problem #4 (pdf, problem is on second page), which is your problem with several restrictions removed.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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