Let $d$ be the common difference of the sequence. If $p|d$, the units' digit never changes and we could strike it away, resulting in a sequence of common difference $\frac dp$ still having the same property. By this, we may assume $\gcd(d,p)=1$. Now $d$ is invertible $\mod p$, let $c$ be an inverse. If the sequence is $dn+e$, we find that $n\equiv c(k-e) \mod p$ gives $dn+e \equiv cd(k-e)+e \equiv k-e+e =k \mod p$, thus if we choose a nonnegative representant of $c(k-e) < p$, then we see that one of the first $p$ terms always contains the digit $k$. This shows that the length is at most $p-1$, archieved by $1,2,...,p-1$ itself. PS: why $p \neq 2,3$

ZetaX wrote: This shows that the length is at most $p-1$, archieved by $1,2,...,p-1$ itself. I am probably asking something extremely stupid, but why is $1,2,...,p-1$ an example of $p-1$? $k$ appears in this sequence for any $k$, doesn't it? (never worked with p-adic numbers before so I'm completely unsure) As for $p=2,3$, I think they only call it an arithmetic progression if it has at least $3$ terms.

You are right, I mistakenly considered $k=0$ only (this problem by the way is one purely in $\mathbb Z$, so it's not really $p$-adical). For all other cases: If $k \neq 1$ consider the sequence $k+1 , k+2, k+3, ... p-1 , p+0, p+1, ... , p+(k-1)$. If $k=1$, use $2p+2,2p+3,...,3p+0$.

ZetaX wrote: If $k=1$, use $2p+2,2p+3,...,3p+0$. Not if $p=3$, then $3p=100$ if I'm not mistaken. But of course there are enough trivial examples for $p=3$.