# Is there a sequence of primes whose decimal representations are initial segments of each other?

I.e., is there a sequence of primes whose decimal expansions have the following form:

$$a_1,\ a_1a_2,\ a_1a_2a_3,\ a_1a_2a_3a_4, \dots$$

What about with the order of the digits reversed, so each number's decimal representation is a final segment of the next one's? (Or any other interesting variation of restrictions?)

In binary, neither is possible. Starting with $2 = 10_2$, adding digits to the left would give even numbers greater than 2, hence composite. Adding to the right eventually hits 95. More generally it's clear that you'd have to add a $1$ digit, meaning that the sequence is of the form $x_{n+1} = 2x_n + 1$ with $x_0 = 10_2 = 2$. This has the general form $3\cdot 2^n - 1$. Since 2, 3, and 5 are primes, this expression will be congruent to $0\pmod 5$ every $5$ terms.

-

The longest such sequences (of the first kind) end in 23399339, 29399999, 37337999, 59393339 or 73939133. The longest sequence of the second kind (not allowing prepending zeroes) ends in 357686312646216567629137.

(These numbers were found by a quick search using PARI/GP)

For base $b$ instead of $10$ observe the following:

Call $p$ a $b$-Gupta prime of the first kind if $p$ is prime and $\lfloor \frac pb\rfloor$ is zero or a $b$-Gupta prime of the first kind. Call $p$ a $b$-Gupta prime of the second kind if $p$ is prime and $b^k\le p<b^{k+1}$ and $k=0$ or the remainder $p\bmod b^k$ is a $b$-Gupta prime of the second kind.

If there are $r_k$ $b$-Gupta primes of some kind with $k$ digits, there are only $br_k$ numbers $p$ such that $\lfloor \frac pb\rfloor$ or $p\bmod b^k$ is a $b$-Gupta prime of the same kind. Heuristically, these candidates are prime with probability $\frac1{\ln p}\approx \frac1k\cdot \frac1{\ln b}$. Therefore we expect $r_{k+1}\lesssim\frac 1k\cdot \frac b{\ln b} r_k$, i.e. $r_k$ should fall off quite rapidly after a few initial steps.

-
This is discussed at en.wikipedia.org/wiki/Truncatable_prime and other places you can find using the search term "truncatable primes". – Gerry Myerson Dec 31 '12 at 23:24
Oh, I should have googled the result 357686...137 I found :) – Hagen von Eitzen Jan 1 '13 at 17:39