1994 AIME Problems/Problem 5

From AoPSWiki

Problem

Given a positive integer $n\,$ , let $p(n)\,$ be the product of the non-zero digits of $n\,$ . (If $n\,$ has only one digits, 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}$ .

1994 AIME (Problems • Resources)
Preceded by Problem 4	Followed by Problem 6
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Personal tools

Navigation

Search

Toolbox