Let $p \ge 5$ be a prime number. Find the largest length of an arithmetic progression, of positive ratio, of positive integers whose terms do not contain the digit $1$ in their p-adic expansion.


I suspect that ratio should be read as difference. If so, you’re being asked to determine the greatest possible length of a strictly increasing arithmetic sequence of positive integers, whose base $p$ representations do not contain the digit $1$. In base five, for instance, if you start out with $2,4$, you’re blocked, because $6=11_{\text{five}}$. If you start at $12=22_{\text{five}}$ with a common difference of $3$ you can do a little better: $22_{\text{five}},30_{\text{five}},33_{\text{five}}$. But the next number in the sequence is $41_{\text{five}}$, so you’re blocked again. And be starting at $14=24_{\text{five}}$, I can do better yet: $24_{\text{five}},32_{\text{five}},40_{\text{five}},43_{\text{five}}$. (I’ll leave it to you to verify that I’m blocked again.)

HINT: Look at the $1$’s digit, the least significant digit. Say that your sequence is $a,a+d,a+2d$, $a+3d$, and so on. If $b\ne 0$ is the $1$’s digit of $d$, what can you say about the numbers $d,2d,3d,\dots,pd$ modulo $p$? And you don’t have to worry about a difference $d$ that ends in $0$: the $1$’s digit remains constant throughout your sequence, and you might as well just throw it away. E.g., instead of looking at $242_{\text{five}},322_{\text{five}},402_{\text{five}},432_{\text{five}}$, with difference $d=30_{\text{five}}$, look at $24_{\text{five}},32_{\text{five}},40_{\text{five}},43_{\text{five}}$, with difference $d=3$.

  • $\begingroup$ thank you very much for your explanation of what is being asked, it makes more sense to me now, and thank you for the hints too. i will look more into it and tell you what i have later. $\endgroup$ – fmat Oct 2 '12 at 7:59
  • $\begingroup$ So I think I am aiming to find the largest possible n such that: $a+nd \equiv 1 \pmod p$ while it's clear that $pd \equiv 0 \pmod p$ Therefore I am guessing now the progression must somehow be blocked before the term $a+pd$ and so $p-1$ might be the largest $n$ that gets blocked? $\endgroup$ – fmat Oct 4 '12 at 23:53
  • $\begingroup$ @finial: Yes, with a bit of work you should be able to show that you can’t get $p$ terms, but you can always get $p-1$. $\endgroup$ – Brian M. Scott Oct 5 '12 at 2:41
  • $\begingroup$ So I proved (hopefully not faultly) that since $a+pd \equiv a \pmod p$ and $a+nd \neq a+md \pmod p$ for any $n,m \lt p, n\gt m$, we have that the first digit of each term mod p has to be different. Therefore can't get p terms, but the hard part to show that we can always have $p-1$ terms is that I realized we not only have to take care of the first digit, but EVERGY DIGIT, because once we contain 1 in any digit of the term, we are out. Any more suggestion? $\endgroup$ – fmat Oct 5 '12 at 5:05
  • $\begingroup$ @finial: Use $d=1$ and a two-digit starting point just large enough to ensure that you don’t run into a $1$ before the $p$-th term. $\endgroup$ – Brian M. Scott Oct 5 '12 at 5:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.