
C1. Let $S_{n}$ be the sum of reciprocal values of non-zero digits of all positive integers up to (and including) $n$. For instance, $S_{13}=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}+\frac{1}{9}+\frac{1}{1}+\frac{1}{1}+\frac{1}{1}+\frac{1}{1}+\frac{1}{2}+\frac{1}{1}+\frac{1}{3}$. Find the least positive integer $k$ making the number $k!\cdot S_{2016}$ an integer.


## Solution.

We will first calculate $S_{999}$, then $S_{1999}-S_{999}$, and then $S_{2016}-S_{1999}$.

Writing the integers from 1 to 999 as 001 to 999, adding eventually also 000 (since 0 digits actually do not matter), each digit appears exactly 100 times in each position(as unit, ten, or hundred). Hence

$$
S_{999}=300 \cdot\left(\frac{1}{1}+\frac{1}{2}+\cdots+\frac{1}{9}\right)
$$

For the numbers in the interval $1000 \rightarrow 1999$, compared to $0 \rightarrow 999$, there are precisely 1000 more digits 1 . We get

$$
S_{1999}-S_{999}=1000+S_{999} \Longrightarrow S_{1999}=1000+600 \cdot\left(\frac{1}{1}+\frac{1}{2}+\cdots+\frac{1}{9}\right)
$$

Finally, in the interval $2000 \rightarrow 2016$, the digit 1 appears twice as unit and seven times as a ten, the digit 2 twice as a unit and 17 times as a thousand, the digits $3,4,5$, and 6 each appear exactly twice as units, and the digits 7,8 , and 9 each appear exactly once as a unit. Hence

$$
S_{2016}-S_{1999}=9 \cdot 1+19 \cdot \frac{1}{2}+2 \cdot\left(\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}\right)+1 \cdot\left(\frac{1}{7}+\frac{1}{8}+\frac{1}{9}\right)
$$

In the end, we get

$$
\begin{aligned}
S_{2016} & =1609 \cdot 1+619 \cdot \frac{1}{2}+602 \cdot\left(\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}\right)+601 \cdot\left(\frac{1}{7}+\frac{1}{8}+\frac{1}{9}\right) \\
& =m+\frac{1}{2}+\frac{2}{3}+\frac{2}{4}+\frac{2}{5}+\frac{2}{6}+\frac{6}{7}+\frac{1}{8}+\frac{7}{9}=n+\frac{p}{2^{3} \cdot 3^{2} \cdot 5 \cdot 7}
\end{aligned}
$$

where $m, n$, and $p$ are positive integers, $p$ coprime to $2^{3} \cdot 3^{2} \cdot 5 \cdot 7$. Then $k!\cdot S_{2016}$ is an integer precisely when $k$ ! is a multiple of $2^{3} \cdot 3^{2} \cdot 5 \cdot 7$. Since $7 \mid k!$, it follows that $k \geq 7$. Also, $7!=2^{4} \cdot 3^{2} \cdot 5 \cdot 7$, implying that the least $k$ satisfying $k!\cdot S_{2016} \in \mathbb{Z}$ is $k=7$.
