Extending primes forever

Question

I found a big number 357686312646216567629137 with the characteristic that if we cut it from the left, we always get a prime number, meaning that 7 is prime, 37 is prime, 137 is prime and so on..

Thinking about this i got up with the question, if it is possible to continue this and if it possible to find always a bigger number with this characteristic.

I found this question making it reasonable that it is kind of unlikely that we can continue with this process forever, but that means not that it is not possible. Obviously we could brute force all 9 possibilities for the next number on the far left, but at numbers of this size I personally have no tool to check if the resulting number is prime or not.

So I would appreciate if anyone have any knowledge on this. I also have no idea what I should google to find any results on this question.. Maybe this problem have a name or something

This may interest you: https://en.wikipedia.org/wiki/Truncatable_prime — Mike Daas, Aug 24 '22 at 18:33
Your number $p=357686312646216567629137$ is a left-truncatable prime, which is restricted - every number $xp$ for a digit $x\in {1,2,\ldots ,9}$ is composite. It is the last entry here. — Dietrich Burde, Aug 24 '22 at 18:37
And indeed, the set of left-truncatable primes is finite, and your number is the largest one. So it stops - your title is not true. — Dietrich Burde, Aug 24 '22 at 18:45
Usually, Numberphile videos are not useful. Best witness , the $1+2+3+\cdots=-1/12$ video. — Peter, Oct 27 '22 at 12:04

score 4 · Accepted Answer · answered Aug 24 '22 at 18:59

Here is a summary of the above comments. The numbers you are describing are called left-truncatable primes, and it is easy to see that the set of such primes is finite - since it has finitely many endpoints, see the video, or this reference:

Proof for finite number of truncatable primes

There is an OEIS page for it here. The final list has $4260$ primes and starts with $$ 2, 3, 5, 7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97, 113, 137, 167,\cdots , 357686312646216567629137. $$

score 2 · Answer 2 · answered Aug 24 '22 at 22:06

Obviously we could brute force all 9 possibilities for the next number on the far left, but at numbers of this size I personally have no tool to check if the resulting number is prime or not.

Well, let's make the problem a little simpler.

Call the integer $n$ "pseudoprime" if it has no prime factors (other than $n$ itself) less than a million. Actual prime numbers are then a subset of pseudoprimes. And all pseudoprimes less than $10^{12}$ are primes. This is easily checked by computer.

import math
def generate_primes(limit):
    """
    Return a list of all primes in range(2, limit).
    """
    result = []
    potential = range(2, limit)
    while potential:
        p = potential[0]
        result.append(p)
        potential = [n for n in potential if n % p]
    return result
PRIMES = generate_primes(10**6)
def is_pseudoprime(n):
    # Special handling of 1, 0, and negatives
    if n < 2:
        return False
    # Test every known prime up to sqrt(n)
    max_divisor = int(math.sqrt(n) * 1.00000001)
    for p in PRIMES:
        if p > max_divisor:
            return True     # n is a true prime
        if n % p == 0:
            return False    # n is composite
    return True    # Ran out of trial divisors.  Maybe prime.
def is_ltpp(n):
    """
    Check if n is a left-truncatable pseudoprime.
    """
    num_digits = len(str(n))
    return all(is_pseudoprime(n % 10 ** k) for k in range(1, num_digits + 1))

We can now find the left-truncatable pseudoprimes by brute force.

def find_ltpp():
    # Start with single-digit primes.
    num_digits = 1
    ltpp = [2, 3, 5, 7]
    while True:
        print('There are {0} {1}-digit LTPPs.  The largest is {2}.'
            .format(len(ltpp), num_digits, ltpp[-1]))
        # Add one digit on the left.
        potential = [n + digit * 10**num_digits
            for n in ltpp
            for digit in range(1, 10)]
        num_digits += 1
        ltpp = [n for n in potential if is_ltpp(n)]
        if not ltpp:
            print('There are NO {0}-digit LTPPs.'.format(num_digits))
            break

If you're sufficiently patient, this function produces the output:

There are 4 1-digit LTPPs.  The largest is 7.
There are 11 2-digit LTPPs.  The largest is 97.
There are 39 3-digit LTPPs.  The largest is 997.
There are 99 4-digit LTPPs.  The largest is 6997.
There are 192 5-digit LTPPs.  The largest is 96997.
There are 326 6-digit LTPPs.  The largest is 496997.
There are 429 7-digit LTPPs.  The largest is 6396997.
There are 521 8-digit LTPPs.  The largest is 96396997.
There are 545 9-digit LTPPs.  The largest is 396396997.
There are 517 10-digit LTPPs.  The largest is 4396396997.
There are 448 11-digit LTPPs.  The largest is 76633396997.
There are 354 12-digit LTPPs.  The largest is 616333396997.
There are 298 13-digit LTPPs.  The largest is 5616333396997.
There are 265 14-digit LTPPs.  The largest is 35616333396997.
There are 215 15-digit LTPPs.  The largest is 435616333396997.
There are 194 16-digit LTPPs.  The largest is 6435616333396997.
There are 188 17-digit LTPPs.  The largest is 65678739293946997.
There are 158 18-digit LTPPs.  The largest is 165678739293946997.
There are 129 19-digit LTPPs.  The largest is 6165678739293946997.
There are 118 20-digit LTPPs.  The largest is 56165678739293946997.
There are 108 21-digit LTPPs.  The largest is 666276812967623946997.
There are 101 22-digit LTPPs.  The largest is 9151351291983366421997.
There are 92 23-digit LTPPs.  The largest is 33151351291983366421997.
There are 82 24-digit LTPPs.  The largest is 233151351291983366421997.
There are 60 25-digit LTPPs.  The largest is 6233151351291983366421997.
There are 55 26-digit LTPPs.  The largest is 19327957389768645663786197.
There are 53 27-digit LTPPs.  The largest is 572334815396334245663786197.
There are 49 28-digit LTPPs.  The largest is 9572334815396334245663786197.
There are 42 29-digit LTPPs.  The largest is 49572334815396334245663786197.
There are 38 30-digit LTPPs.  The largest is 619572334815396334245663786197.
There are 43 31-digit LTPPs.  The largest is 5934572334815396334245663786197.
There are 36 32-digit LTPPs.  The largest is 45934572334815396334245663786197.
There are 29 33-digit LTPPs.  The largest is 757863372334815396334245663786197.
There are 23 34-digit LTPPs.  The largest is 6273863372334815396334245663786197.
There are 19 35-digit LTPPs.  The largest is 89139326798675469278339997564326947.
There are 21 36-digit LTPPs.  The largest is 939139326798675469278339997564326947.
There are 17 37-digit LTPPs.  The largest is 2939139326798675469278339997564326947.
There are 12 38-digit LTPPs.  The largest is 62939139326798675469278339997564326947.
There are 10 39-digit LTPPs.  The largest is 162939139326798675469278339997564326947.
There are 10 40-digit LTPPs.  The largest is 6162939139326798675469278339997564326947.
There are 8 41-digit LTPPs.  The largest is 12162939139326798675469278339997564326947.
There are 6 42-digit LTPPs.  The largest is 512162939139326798675469278339997564326947.
There are 5 43-digit LTPPs.  The largest is 9496392127212135769692168751546215769833347.
There are 2 44-digit LTPPs.  The largest is 96335316563367861332796686312646216567629137.
There are 3 45-digit LTPPs.  The largest is 196335316563367861332796686312646216567629137.
There are 4 46-digit LTPPs.  The largest is 5196335316563367861332796686312646216567629137.
There are 1 47-digit LTPPs.  The largest is 23616335316563367861332796686312646216567629137.
There are 2 48-digit LTPPs.  The largest is 623616335316563367861332796686312646216567629137.
There are 3 49-digit LTPPs.  The largest is 9623616335316563367861332796686312646216567629137.
There are 4 50-digit LTPPs.  The largest is 49623616335316563367861332796686312646216567629137.
There are 4 51-digit LTPPs.  The largest is 649623616335316563367861332796686312646216567629137.
There are 3 52-digit LTPPs.  The largest is 7651623616335316563367861332796686312646216567629137.
There are 2 53-digit LTPPs.  The largest is 64351623616335316563367861332796686312646216567629137.
There are 1 54-digit LTPPs.  The largest is 578121623616335316563367861332796686312646216567629137.
There are NO 55-digit LTPPs.

So, the left-truncatable pseudoprimes thin out until you reach a 54-digit example, and none at all for 55 (or more) digits.

Since left-truncatable primes are a subset of left-truncatable pseudoprimes, and the latter is finite, then it follows that there are only a finite number of left-truncatable primes. To find them, you'll need a way to filter the left-truncatable pseudoprime list to exclude numbers that aren't actually prime.

I just noticed that the largest left-truncatable pseudoprime has the same last 21 digits as the largest left-truncatable actual prime. — Dan, Aug 26 '22 at 14:35

score -2 · Answer 3 · answered Aug 24 '22 at 19:00

The probability of hitting a prime number reduces to approximately ln N when N is large. If we already have a prime of m digits then adding a (base 10) digit to the left between 1 and 9 will achieve a multiple between 2 and 91 of your m digit number. Now using ‘the law of averages’ there will be (ln 91 - ln 2)= approximately average of 3.8177 prime numbers in that whole zone of possible adding an extra digit. The probability, however that simply adding one digit (1-9) to the left will hit one of those prime numbers in amongst the more than 10m numbers in that zone will diminish and the probability of hitting a prime number every time will diminish to zero. If one allowed the possibility of adding more than one digit to the left, then the sequence will progress longer, possibly indefinitely. However if the number of added digits was limited to say 2, then, again, I expect the sequence to terminate.

Extending primes forever

3 Answers3

Linked