Digit Product. Topic: Number Theory. Level: AIME.

Problem: (1994 AIME - #5) Given a positive integer $n$, let $p(n)$ be the product of the non-zero digits of $n$. (If $n$ has only one digit, then $p(n)$ is equal to that digit.) Let

$S=p(1)+p(2)+p(3)+\cdots+p(999)$.

What is the largest prime factor of $S$?

Solution #1: At first glance, the product of the digits is really quite a nasty function... But some shrewd algebra skills can take it on without too much trouble.

Consider $p(k)$ for $ k = 1, 2, \ldots, 9 $.

We obviously get the values $ 1, 2, \ldots, 9 $. This sums to $ 45 $.

Consider $p(k)$ for $ k = d_1d_2 $, where the $d$'s are digits, for $ d_1 > 0 $ and $ d_2 = 0,1,2,\ldots,9 $.

It's easy to see that this gives $ d_1, 1 \cdot d_1, 2 \cdot d_1, \ldots, 9 \cdot d_1 $. This sums to $ d_1 \cdot (1+1+2+\cdots+9) = 46 \cdot d_1 $.

Now take $ d_1 = 1,2, \cdots, 9 $ to get a sum of $ 46(1+2+\cdots+9) = 46(45) $.

Consider the $p(k)$ for $ k = d_1d_2d_3 $ for $ d_1 > 0 $ and both $ d_2 $ and $ d_3 $ ranging from $ 0 $ to $ 9 $.

For any fixed $ d_1 $, we just have $ d_2d_3 $ ranging, which we know to have value (assume $ 00 $ gives $ 1 $) $ (1+1+\cdots+9)(1+1+\cdots+9) = 46^2 $.

And since $ d_1 $ ranges from $ 1 $ to $ 9 $, we get $ (1+2+\cdots+9)(46^2) = 45 \cdot 46^2 $.

Whew. Now sum everything up to get $ 45+45 \cdot 46+45 \cdot 46^2 = 45(1+46+46^2) = 45(2163) = 45 \cdot 21 \cdot 103 $.

Therefore the largest prime divisor is $ 103 $. QED.

--------------------

Comment: That was a rather brute force solution, but it doesn't take much time on the test and works out pretty well. The following solution is more clever, but takes a little longer to work out logically.

--------------------

Solution #2: We look at the numbers based on their place value.

Let $ p(0) = 1 $ for this, which has no effect on the product as given in the problem, except for the case $ n = 0 $ which we will discount later.

The required sum $ S+1 $ (we add one to account for the $ 0 $ term) can be rewritten as $ S+1 = [p(0)+\cdots+p(9)][p(0)+\cdots+p(9)][p(0)+\cdots+p(9)] = [p(0)+\cdots+p(9)]^3$. Why?

First notice that $ p(n) = \prod p(d) $ where $ d $ is a digit of $ n $. This is easy to show since multiplication is "multiplicative."

So consider any number $ p(n) = p(d_1d_2d_3) = p(d_1)p(d_2)p(d_3) $. We just need to take each $ d $ from $ 0 $ to $ 9 $ to find the desired sum $ S $. That means multiplying $ p(0)+p(1)+\cdots+p(9) $ for each digit, of which there are three, verifying the above formula.

Then $ p(0)+p(1)+\cdots+p(9) = 46 $ so $ S+1 = 46^3 \Rightarrow S = 46^3-1 = (46-1)(1+46+46^2) = 45 \cdot 21 \cdot 103 $ as before. QED.

--------------------

Practice Problem: (1994 AIME - #1) The increasing sequence $3, 15, 24, 48, \ldots$ consists of those positive multiples of $3$ that are one less than a perfect square. What is the remainder when the $1994$th term of the sequence is divided by $1000$?