6
$\begingroup$

For no particular reason I stumbled upon the sequence/set of all numbers where all substrings of the decimal representation is prime (A085823). It's quite easy to see that this must be a finite set. My approach was that the digits must alter between 3 and 7 eventually (since a prime can't end with 2 or 5 for larger than that and a prime can't consist of just two non-1 digits, those would be dividable by 2, 5 or 11) and we can see where it ends.

But if we change the base that approach fails. For example in base 8 a prime can end in 3, 5 or 7 AFAICS so such numbers can end in a altering sequence of 3, 5 and 7s but having tree digits to alter between there's always a way to vary the sequence.

I tried to write a python snippet to produce such numbers in different bases and for those I've tested the program seem to hang (ie don't seem to find any more numbers). Is it true that there are only a finite number of such numbers for every base?

$\endgroup$

1 Answer 1

3
$\begingroup$

Yes!

Let $b \geq 2$ be a base in which you want to represent these numbers. Then, set $c := b-1$. Clearly, $b \equiv 1 \mod c$.

Now assume there was a number $n$ which has a length $\geq 2c+1$ for which every subword of its representation in base $b$ would be prime again. Write $n$ as $a_m \cdots a_0$ in base $b$. Consider $$\DeclareMathOperator{\Mod}{mod} s_k :\equiv \sum_{i=0}^k a_i \Mod c$$ for $k\in \{0, \dots, m\}$. Since the $s_k$ can only take $c$ possible values and $m+1 \geq 2c+1$ by assumption, we have that there are $i<j<k, i,j,k \in \{0, \dots, m\}$ s.t. $s_i = s_j = s_k$. But this implies $k > i+1$ and: $$0 \equiv s_k - s_i \equiv \sum_{l=i+1}^k a_l \equiv \sum_{l=i+1}^k a_l \cdot b^{l-(i+1)} \Mod c$$ But the last sum of which we take $\Mod c$ is precisely the number represented by $a_k \cdots a_{i+1}$ in base $b$. As a subword of our $n$, it has to be prime. The above equality then yields that it actually has to be equal to $c$ (since it is divisible by $c$ and prime). But since $k>i+1$, we have $$c=b-1=\sum_{l=i+1}^k a_l \cdot c^{l-(i+1)}\geq a_k \cdot b^{k-(i+1)} > b$$ which is a contradiction.

So, we can conclude that the length of such an $n$ can be $2c$ at most. Thus there are only finitely many such $n$s in every base.

One can even show that the length is at most $2p-1$ where $p$ is the smallest prime that does not divide $b$. If you are interested, I'll link a proof of this.

$\endgroup$
3
  • $\begingroup$ A minor point is that since $0$ and $1$ can't be in the string, you can choose a base $b \gt 2$. Otherwise, for $b = 2$, you have your $c = 1$. Otherwise, every else looks fine. $\endgroup$ Nov 27, 2019 at 4:57
  • $\begingroup$ I would be interested in the $2p-1$ proof Jakob B. $\endgroup$
    – user682219
    Dec 9, 2019 at 21:04
  • $\begingroup$ Nevermind, I managed to work it out. $\endgroup$
    – user682219
    Dec 10, 2019 at 21:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .