Smith Numbers
Time limit1sMemory limit128 MB
For each input n, print the smallest Smith number larger than n, where a Smith number is a composite whose digit sum equals the digit sum of its prime factors.
- Level
Medium4 of 10
- Topics
- Number theory, Math, Brute force, Implementation
- Solved
- No attempts yet
Problem
In 1982, Albert Wilansky, a mathematician at Lehigh University, was skimming his phone directory when he noticed that his brother-in-law H. Smith's telephone number had a curious property: the sum of the digits of the number equals the sum of the digits of its prime factors.
Smith's telephone number was 4937775. Its prime factorization is:
4937775 = 3 × 5 × 5 × 65837
The sum of the digits of the number is 4 + 9 + 3 + 7 + 7 + 7 + 5 = 42, and the sum of the digits of all of its prime factors is likewise 3 + 5 + 5 + (6 + 5 + 8 + 3 + 7) = 42. Delighted by the coincidence, Wilansky named such numbers after his brother-in-law: Smith numbers.
Because every prime number also satisfies this property (trivially), Wilansky decided that a prime is too simple to deserve the name and excluded primes from the definition.
In short, a Smith number is a composite number whose digit sum equals the sum of the digits of its prime factors (counted with multiplicity).
For example, 9985 and 6036 are Smith numbers. Wilansky, however, could never find a Smith number larger than his brother-in-law's telephone number. Your task is to find Smith numbers larger than 4937775.
Input
The input consists of a sequence of positive integers, one per line. Each integer has at most 8 digits. The input ends with a line containing the single number 0, which is not processed.
Output
For every number n > 0 in the input, output the smallest Smith number strictly larger than n, each on its own line. Such a number is guaranteed to exist.