1994 AIME Problems/Problem 5

Problem

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

Solution 1

Suppose we write each number in the form of a three-digit number (so $5 \equiv 005$), and since our $p(n)$ ignores all of the zero-digits, replace all of the $0$s with $1$s. Now note that in the expansion of

$(1+ 1 +2+3+4+5+6+7+8+9) (1+ 1 +2+3+\cdots+9) (1+ 1 +2+3+\cdots+9)$

we cover every permutation of every product of $3$ digits, including the case where that first $1$ represents the replaced $0$s. However, since our list does not include $000$, we have to subtract $1$. Thus, our answer is the largest prime factor of $(1+1+2+3+\cdots +9)^3 - 1 = 46^3 - 1 = (46-1)(46^2 + 46 + 1) = 3^3 \cdot 5 \cdot 7 \cdot \boxed{103}$.

Solution 2

Note that $p(1)=p(11), p(2)=p(12), p(3)=p(13), \cdots p(19)=p(9)$, and $p(37)=3p(7)$. So $p(10)+p(11)+p(12)+\cdots +p(19)=46$, $p(10)+p(11)+\cdots +p(99)=46*45=2070$. We add $p(1)+p(2)+p(3)+\cdots +p(10)=45$ to get 2115. When we add a digit we multiply the sum by that digit. Thus $2115\cdot (1+1+2+3+4+5+6+7+8+9)=2115\cdot 46=47\cdot 45\cdot 46$. But we didn't count 100, 200, 300, ..., 900. We add another 45 to get $45\cdot 2163$. The largest prime factor of that is $\boxed{103}$.

See also

1994 AIME (ProblemsAnswer KeyResources)
Preceded by
Problem 4
Followed by
Problem 6
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png