## Sum Product Numbers

#### Problem

A positive integer, N, is an sum-product number if there exists a set of positive integers:

S = {`a`_{1},`a`_{2},...,`a`_{k}}, such that N = `a`_{1} `a`_{2} ... `a`_{k} = `a`_{1} + `a`_{2} + ... + `a`_{k}. 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` 1`p`, hence N cannot be prime.

If N is composite it can be written as N = `ab`, where `a,b` 2.

N = `ab` = (`a`1)`b``a`+`a`+`b`.

Let `m` = (`a`1)`b``a`, so that N = `ab` = `m`+`a`+`b`.

As `a,b` 2, let `a`=2 (the minimum value), so `m` = (`a`1)`b``a` `b`2 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 = 25 = 10, and as 2+5=7, we can write,

10 = 25111 = 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.