What is the maximum length of a string of nonzero digits that has no substring that is divisible by a given prime number?
I want to find a string of length n which has no substring divisible by the given prime number p (the string cannot have zeroes). I coded in c++ and for some prime numbers p I noticed the following property:
The maximum length possible for that desired string is p-1. Does that property hold for every prime number?
These are the prime numbers that I have tested:
2, 3, 5, 7, 11, 13
For all of these prime numbers except 2 and 5, length of the longest string which has no substring divisible by that prime number is (that prime number - 1 ). For example for 13 we have string "111112115541" which has no substring divisible by 13. Length of this string is 12 and my code says there is no such string with length 13. So 12 is maximum.
I can't check this for 17. Because my code takes very time to execute and cannot realize that property is correct or not. Actually I have found the desired string for 17 with length 16 and if my code says that there is no such string with length 17 then that property is also holds for 17.
BTW For all prime numbers p <= 97 my code has found that desired string with length (p-1). But I don't know that this length is maximum or not. I'm only sure about 3, 7, 11, 13 .
Upper bound. If $p$ does not divide $10$, then there can be no such string of digits longer than $p-1$.
Namely, consider all suffixes of your string (including the empty string) and compute the remainder of each of them (interpreted as a number) modulo $p$. If the string is longer than $p-1$ then there are more than $p$ different suffixes; by the pigeonhole principle two of them will have the same remainder. Subtract them! You get a number of the form $b\cdot 10^n$ where $b$ is a substring of your original string, such that $p\mid b\cdot 10^n$. Since $p$ doesn't divide $10^n$, it must divide $b$.