An arithmetic sequence whose members do not contain the digit ‘9’

Question

There is a non-constant arithmetic progression made of natural numbers only; none of them contains the digit $9$. Prove that such an arithmetic progression has no more than $72$ terms.

Answer 1

We have a sequence $a_n = b+ns$, where we call $b$ the "base element" and $s$ the step. We notice for first that if $s\equiv 1,3,7,9\pmod{10}$ all the ten residue classes $\pmod{10}$ are covered by $a_0,\ldots,a_9$, hence the sequence cannot avoid the digit $9$ for more than $9$ terms. For a similar reason, we cannot have $s\equiv 2,4,6,8\pmod{10}$, since otherwise we fall into one of the residue classes $90+[0,9]\pmod{100}$ before the $45$th term. If $s\equiv 0\pmod{10}$, hence $s=10s'$, the digits represented by the sequence, apart from the last one that is constant, are the same that the digits represented by the sequence $a_n' = \lfloor b/10\rfloor + ns'$. So we may assume without loss of generality that $s\equiv 5\pmod{10}$. If now we focus on the sequence $b_n=a_{2n}$, we can easily deduce that $s\equiv 25\pmod{100}$ by the same way as above. By focusing now on $c_n = a_{4n}$, it is easy to check that, in order to avoid the residue classes $900+[0,99]\pmod{1000}$ in the first $40$ terms, the only chances are $s\equiv 125,625\pmod{1000}$. Now it is just tedious, by focusing on $d_n=a_{8n}$, to check that even such sequences cannot avoid the residue classes $9000+[0,999]\pmod{10^4}$ for more than $72$ terms, hence we're done.

Answer 2

This is only a partial solution. I thought I could extend it to a full solution, but that failed. The argument may be instructive, and could get somebody else on the track, so I will leave it here.

We cover the case where the arithmetic progression starts with 0, so our sequence is $0,x,2x,\ldots$. Assume that $x$ has $k$ decimal digits. If we are counting in multiples of $x$ there is no way thay we can skip the entire range from $[9\cdot 10^{k+1},10^{k+2})$, but if we want an arithmetic progression of more then 10 terms avoiding 9, then we must clearly skip the entire range $[9\cdot 10^k,10^{k+1})$.

This gives us the requirement that we need to find a one-digit number $b$ such that $bx\geq10^{k+1}$ and $(b-1)x<9\cdot 10^k$.

We will show that $b=9$ cannot work and that $b=8$ gives us exactly what we want. Smaller values are not interesting: e.g. if $b=7$ this would imply that $60x<90\cdot 10^k$ and $70x\geq 10^{k+2}$, so we get smaller limits.

When $b=9$ we get $9x\geq10^{k+1}$ and $8x<9\cdot 10^k$.

$9x\geq10^{k+1}$ implies $8x\geq\frac{80}{9}\cdot 10^k$, so $\frac{80}{9}\cdot 10^k\leq 8x<9\cdot 10^k$. This implies that already $8x$ contains a 9 (write down the decimal expansion of $\frac{80}{9}$ and realize that it is not an integer!), which is not what we are looking for.

When $b=8$ we get $8x\geq10^{k+1}$ and $7x<9\cdot 10^k$.

$8x\geq10^{k+1}$ implies that $x\geq\frac54\cdot 10^k$. But then $72x\geq 90\cdot10^k$, so our sequence can have at most 72 terms (note that we started with 0). The case $x=125$ shows that this result is sharp.