A puzzle about numbers which do not have 2 in their decimal representation

Question

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$.

Answer 1

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.

Answer 2

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$.

Answer 3

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$.