mathschallenge.net logo

Sum Product Numbers

Problem

A positive integer, N, is an sum-product number if there exists a set of positive integers:
S = {a1,a2,...,ak}, such that N = a1 times a2 times ... times ak = a1 + a2 + ... + ak. In order for the set to be a sum and product, it is necessary that S contains at least two elements.

Prove that N is a sum-product number iff it is composite.


Solution

If N is prime, the two factors must be 1 and p. However, 1+p greater than 1timesp, hence N cannot be prime.

If N is composite it can be written as N = ab, where a,b greater than or equal 2.

N = ab = (aminus1)bminusa+a+b.

Let m = (aminus1)bminusa, so that N = ab = m+a+b.

As a,b greater than or equal 2, let a=2 (the minimum value), so m = (aminus1)bminusa greater than or equal bminus2 greater than or equal 0.

As N = ab = m+a+b, and m is never negative, we demonstrate that the sum will be equal to or less than the product.

In which case, the difference, m, can be made up of a sum of ones, for which adding as many ones as necessary will not affect the product.

For example, N = 10 = 2times5 = 10, and as 2+5=7, we can write,
10 = 2times5times1times1times1 = 2+5+1+1+1.

Thus N is a sum-product number iff it is composite.

If each element of S can be any integer (positive or negative), prove that all positive integers are sum-product numbers.

Problem ID: 200 (10 Jan 2005)     Difficulty: 3 Star

Only Show Problem