Question

Let $S$ be the set of all rational numbers $r,$ $0\lt r\lt1,$ that have a repeating decimal expansion in the form $0.abcabcabc\ldots=0.\overline{abc},$ where the digits $a,$ $b,$ and $c$ are not necessarily distinct. To write the elements of $S$ as fractions in lowest terms, how many different numerators are required?

Answer

Answer: 660

Concepts:repeating decimal greatest common divisor Euler’s Totient Function

Difficulty rating: 2320

Small Hint:

Every element has the form $\frac{N}{999}$ , and its reduced denominator must divide $999=3^3\cdot37$

Big Hint:

Count numerators coprime to $999$ , then check which additional multiples of $3$ can occur with denominator $37$

Solution:

Every element is $\frac{N}{999}$ for $1\leq N\leq998.$ Any $a$ coprime to $999$ occurs as a reduced numerator with denominator $999,$ giving $\varphi(999)=648$ values. If $a$ is divisible by $3$ but not $37,$ it can be coprime to a reduced denominator only when that denominator is $37;$ this adds the $12$ multiples of $3$ below $37.$ A numerator divisible by $37$ would need a denominator dividing $27$ and larger than it, so no further values occur. Therefore the total is $648+12=660.$

1992 AIME Problem 5

Answer: 660

Difficulty rating: 2320

Small Hint:

Big Hint:

Solution:

Problem 5 in Other Years