Let p(n) denote the product of the nonzero digits of n. For example, p(5) = 5, p(37) = 21, and p(604) = 24. Without resorting to a computer, evaluate
p(1) + p(2) + p(3) + ... + p(999999).
Let s(d) denote the sum of values of p(n) for all n with at most d digits. Then this problem is asking for s(6).
s(1) is trivial, it is the sum of the digits 1 through 9, which equals 45.
If s(n-1) is known then s(n) can be calculated as:
s(n-1) for the existing terms;
plus (1+2+3+...+9)*s(n-1) for each of the nine blocks of numbers formed by appending each digit in turn to each member of s(n-1) (padding with 0s as needed);
plus 45 for {1*10^(n-1), 2*10^(n-1), ... 9*10^(n-1)}.
Then s(n) = 46*s(n-1) + 45. Not hard to use a calculator to manually calculate the sequence as 45, 2115, 97335, 4477455, 205962975, 9474296895, ...
The final sum sought is 9,474,296,895.
Solution
