Over on Quora, I answered the question "What is a program in Java to check whether a number is a sum-product number?"
The correct answer, in my opinion, is the following:
public static boolean isSumProductNumber( int n ) {
return ( n == 0 ) || ( n == 1 ) || ( n == 135 ) || ( n == 144 );
}
Those are the only possible sum-product numbers in base 10.
It's a number which is equal to the sum of its digits multiplied by the product of its digits. For example, the sum of the digits in "1" are 1 and the product of the digits in "1" are also 1, so 1 = 1 times 1 is a sum-product number in any base. In base 10, the sum of the digits of "135" is 9 and the product of the digits is 15, and 135 = 9 times 15.
Suppose we have a d-digit number n. The product of its digits must be less than 9^d, and the sum of its digits must be less than 9*d. So a sum-product number must be less than (9d)(9^d)
But the number itself is greater than 10^(d-1), because 10^(d-1) is the smallest number with d digits. Therefore,
10^(d-1) <= (9d)(9^d)
We can get Wolfram Alpha to help us solve that inequality: 10^(d-1) <= (9d)(9^d), which tells us that d <= 84.8591, or more meaningfully, d <= 84. So, no 85-digit or larger number can be a sum-product number in base 10.
The same proof can be repeated in any given base, or demonstrated for all bases.
The base-10 digits 2, 3, 4, 5, 6, 7, 8, 9 are all divisible by one of 2, 3, 5, or 7. So the digit product must be of the form 2^a 3^b 5^c 7^d. But, it can't be the case that a sum-product number is divisible by 10, so we can assume that either a = 0 or c = 0 (or both).
The digit sum must be less than 9*84 = 756.
These numbers are small enough we can now do exhaustive search on all possible values of the digit product (that are less than 10^85) multiply them by all possible values of the digit sum, and see whether the result is a sum-product number. This is not the most efficient way, but there are now "only" about five billion possibilities to check.
The following Python code performs that brute-force search, but as I mentioned, not very efficiently. It searches many numbers twice--- once as 2^a 3^b 7^c * 2s and again as 2^(a+1) 3^b 7^c * s, so there is considerable room for improvement. It had tried about 474 million possibilities in the first hour I let it run, up to about 2^120 for the outermost loop of the (2,3,7) possibilities. So if allowed to continue, it should exhaust the possibilities in no more than about 10 hours.
import itertools
import time
def isSumProduct( n ):
d = 0
p = 1
origN = n
while n > 0 and p != 0:
digit = n % 10
d += digit
p *= digit
n /= 10
return d * p == origN
possibleSums = [ s for s in range( 1, 756 )
if s % 10 != 0 ]
def gen237Products( a, b, c):
maxVal = 10**85
na = 1
while na < maxVal:
nb = na
while nb < maxVal:
nc = nb
while nc < maxVal:
yield nc
nc *= c
nb *= b
na *= a
seq1 = ( p * s
for p in gen237Products( 2, 3, 7 )
for s in possibleSums
)
seq2 = ( p * s
for p in gen237Products( 3, 5, 7 )
for s in possibleSums
)
count = 0
start = time.time()
for n in itertools.chain( seq1, seq2 ):
count += 1
if count % 1000000 == 0:
print count, n, time.time() - start
if isSumProduct( n ):
print "Sum-product number:", n
print count, time.time() - start
EDIT: The code completed in 6105 seconds after checking 845,833,630 cases. My "5 billion" estimate was by considering the worst case for each factor individually.
Weisstein, Eric W. "Sum-Product Number." From MathWorld -- A Wolfram Web Resource. http://mathworld.wolfram.com/Sum-ProductNumber.html