A puzzle about numbers which do not have 2 in their decimal representation I came across this puzzle recently which I hope people might enjoy.
Let $S(n)$ be the set of positive integers less than $n$ which do not have a $2$ in their decimal representation and let $\sigma(n)$ be the sum of the reciprocals of the numbers in $S(n)$, so for example $\sigma(5) = 1 + 1/3
 + 1/4$ . 


*

*Show that $S(1000)$ contains $9^3 - 1$ distinct numbers.

*Show that $\sigma(n) < 80$ for all $n$.

 A: Answer to the first part. Imagine that our number system only has the 9 digits $\{0,1,3,4,5,6,7,8,9\}$ (no 2). Then count to 1000 like we always do, except now in base 9. There are $9^3$ distinct numbers. Take away 1 for 0 (because the set excludes 0), and the result is $9^3 - 1$.
A: Hint for the second part. Consider the number of elements of $S(10^n)$ larger than $10^{n-1}$, and observe that they all contribute less than $1/10^{n-1}$. Obtain the appropriate geometric series with ratio $9/10$.
A: For the second part: Since $\sigma$ is increasing, it suffices to bound $\sigma(n)$ for $n = 10^m$, $m\in\mathbb{N}$. It is not too hard to see that $|S(10^{m})| = 9^{m}-1$, so if we let $T_m = S(10^{m+1})\backslash S(10^m)$, then $|T_m| = 9^{m+1} - 9^{m}$. We have
\begin{align*} \sigma(10^{m}) = \sum\limits_{k\in S(10^m)}{\frac{1}{k}} &= \sum\limits_{k\in S(10)}{\frac{1}{k}} + \sum\limits_{j=1}^{m-1}{\sum\limits_{k\in T_j}{\frac{1}{k}}} \\
&\le \frac{1}{1}+\frac{1}{3}+\dots+\frac{1}{9}  + \sum\limits_{j=1}^{m-1}{\frac{|T_j|}{10^j}} \\
&<8 + \sum\limits_{j=1}^{\infty}{\frac{9^{j+1}-9^j}{10^j}} \\
&= 8 + 72 = 80
\end{align*}
as desired.
