3
$\begingroup$

What is the longest known sequence of primes where each new term is obtained by appending a new decimal digit to the previous term?

Examples:

$$(2,23,233,2333,23333)$$

There are no more members in this sequence, because $233331,233333,233337,233339$ are all composite numbes.

$$(3,37,373,3733,37337,373379,3733799,37337999)$$

This one is longer, but still only $8$ terms.

An so on. Because prime gaps can become arbitrary long for large numbers, there is no way any such sequence will be infinite. On the other hand, they can be very long, I think.

What is the longest known sequence of this kind?

Can we prove that:

  • There is no infinite sequence of this kind. Or at least that the sum of reciprocals of any such sequence is finite.

Of course, we can study such sequences in binary or other bases.

Edit

The sequence can start with any prime. This link is very relevant. See also the comments.

The argument that an infinite sequence like this is unlikely goes like this: For each new term we have only four possibilities:

$$a_{n+1}=10 a_n+b,~~~~b=(1,3,7,9)$$

All of these numbers are contained in a very small interval, about $10$ in size. But the density of primes becomes smaller with growing number of digits, and the gaps become larger. In my opinion, the probability of finding the next term for any such sequence becomes smaller with growing $n$.

It doesn't mean that an infinite sequence is impossible, but I conjecture that it's impossible to prove that any such infinite sequence exists.


This question seems to be very closely related to an older question and a more recent question

$\endgroup$
  • $\begingroup$ You are not requiring the sequence to start with a one-digit prime, correct? $\endgroup$ – bof Jul 13 '16 at 10:43
  • $\begingroup$ @bof, correct, I'll edit $\endgroup$ – Yuriy S Jul 13 '16 at 10:45
  • 2
    $\begingroup$ I guess the sum of reciprocals will be finite whether the numbers are prime or not, since each term of the sequence is more than ten times as big as the previous one. $\endgroup$ – bof Jul 13 '16 at 10:51
  • $\begingroup$ If the sequence starts with a single-digit prime, then the longest possible sequences have 8 terms, according to this article on truncatable primes. $\endgroup$ – bof Jul 13 '16 at 10:53
  • $\begingroup$ How come you state flatly "there is no way any such sequence will be infinite" and then ask as a question "can we prove that there is no infinite sequence of this kind"? $\endgroup$ – bof Jul 13 '16 at 10:55
1
$\begingroup$

It appears such a sequence cannot be infinite. Basically, what you're doing is multiplying by $10$ and adding either $1$, $3$, $7$ or $9$. I wrote some python code to test whether sequences of a certain length existed.

I started with a list of all the integers from $0$ up until the highest prime below $10000$ minus one. These are all the possible values of $n\ mod\ p$ with $0<p<10000$. Then I made a new list, which contained all the the values in the old one, multiplied by $10$ and with $1$, $3$, $7$ or $9$ added to them. I removed all the multiples of primes (not the primes themselves) and repeated this proces. As it turns out, the list is empty after repeating this proces $15$ times

Code:

>>> L = []
>>> for x in range(max(primes)):
    L.append(x)


>>> for x in range(15):
    L2 = []
    for l in L:
        L2.append(10*l+1)
        L2.append(10*l+3)
        L2.append(10*l+7)
        L2.append(10*l+9)
    L3 = []
    for l in L2:
        zero = False
        for p in primes:
            if l%p==0 and l!=p:
                zero = True
                break
        if not zero:
            L3.append(l)
    L = copy(L3)


>>> len(L)
0
>>> 

This means that no sequences of length $19$(the initial $4$-digit number can also be a prime with this very special property) exist. As a matter of fact, there don't even exist sequences of length $18$.

$\endgroup$
  • $\begingroup$ You are mistaken about $14$. See this link. It contains a prime $13302806296379339933399333$ We can truncate this prime exactly $14$ times, to the final prime $133028062963$ $\endgroup$ – Yuriy S Jul 13 '16 at 12:39
  • $\begingroup$ Oh, you're right. the initial number can also be a prime of at most 4 digits, so the limit is $17$, I'll correct it. $\endgroup$ – Mastrem Jul 13 '16 at 12:40

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.