## Monday, January 23, 2006

### 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$?

1. p(0) = 1! Now it makes sense! =O

2. Also, y' = y + x:

y'' = y' + 1
y''' = y''
y'' = Ke^x
y' = Ke^x + C_1
y = Ke^x + C_1 x + C_2

And calculation yields C_1 = C_2 = -1. :)

Now, a more interesting problem: y = y' + y''.

3. Nice, that's actually pretty simple.