Counting Truncatable Primes

Roman E. Maeder, Wolfram Research
Sander Huisman, University of Twente
Marco Thiel, University of Aberdeen

Counting Truncatable Primes

ABSTRACT

The 24-digit number 357686312646216567629137 is the longest left-truncatable prime in base 10. The number remains prime when any sequence of leading digits is removed, down to 7. There are 4260 such primes. In base 24, there are 1’052’029’701 truncatable primes.

We discuss parallel search strategies for counting all primes in bases up to 100 and compare the results with predictions based on the prime number theorem for arithmetic progressions. For example, the calculation for base 30 is estimated to take about 750 CPU core years.

Introduction

A (left) truncatable prime in base b is a prime that remains prime when any sequence of leading digits is removed.

The 24-digit number 357686312646216567629137 is the longest truncatable prime in base 10.

This work started as a contribution in the Wolfram Community:
https://community.wolfram.com/groups/-/m/t/1569707?p_p_auth=1KF3imIJ

Let us verify the primality:

b=10;
prime=357686312646216567629137;

NestWhileList[FromDigits[Rest@IntegerDigits[#,b],b]&,prime,Positive,1,∞,-1]//TableForm

AllTrue[%,PrimeQ]

Questions

How many such primes are there?

How long are the longest ones?

What about other bases?

Note that all truncatable primes are, well, truncations of the maximal or leaf primes (which cannot be extended). Those intermediate primes are less interesting, and we do not need to store them.

Searching for Truncatable Primes (TP)

The key idea is to start from the ground up, either using breadth-first or depth-first search, by adding candidate new leading digits, then testing for primality.

Given a prime p with k digits, form b-1 (k+1)-digit candidates p+β, p+2β, …, p+(b-1)β , where β=(b^k), and test them for primality.

If none of these are prime, p is a maximal, or leaf prime, otherwise it is a non-leaf TP and the search continues with the prime candidates.

Breadth-first search, generating all primes of lengths 1, 2, … iteratively, is useful for generating the set of all such primes, and it parallelizes easily. However, it requires a lot of (intermediate) storage.

Depth-first (recursive) search is useful if we merely want to count the primes, and perhaps find the longest ones. It does not parallelize and run-time estimates are difficult.

Outline of Recursive Search

This function counts all TP for base b. The recursive search procedure inside updates global counters as it encounters new primes.

DFSearch[b_]:=Module[{allp,leafp,maxk,maxps,search},
With[{digits=Range[1,b-1]},
(* global variables for the results of the recursive search *)
allp=leafp=<||>; maxk=0;maxps={};
(* recursive search starting at the k digit prime p; β is b^k *)
search[β_,k_][p_]:=With[{new=Select[digits*β+p,PrimeQ]},
If[Length[new]==0, (* p is maximal *)
Which[ (* is it a new record length TP? *)
k>maxk,maxk=k;maxps={p},
k==maxk,AppendTo[maxps,p]
];
leafp[k]=Lookup[leafp,k,0]+1; (* count a leaf prime of length k *)
, (* else it is extensible *)
allp[k+1]=Lookup[allp,k+1,0]+Length[new]; (* count the new primes of length k+1 *)
search[b*β,k+1]/@new (* and recurse *)
];
];
search[1,0][0]; (* we do not count the starting "prime" 0 *)
Clear[search];
{Total[leafp],Total[allp],maxk,maxps,KeySort[leafp],KeySort[allp]}
]]

The results are, respectively, the number of leaf primes, total number of TP, maximum length, list of primes of that length, length distribution (l->#) of leaf primes, length distribution of all primes.

DFSearch[10]

Here is base 16:

res16=DFSearch[16]

Longest primes rendered as digit strings in their natural base:

iString[16]/@res16[[4]]

Here is base 19:

res19=DFSearch[19]

iString[19]/@res19[[4]]

Why are there such large differences in the number of TP among different bases?

The Hybrid Method

For our larger searches we will use a hybrid method, generating all primes up to some small length, then searching for all primes starting with each one of these recursively (and independently).

We want to find these properties for a given base:

Total number of truncatable primes (broken down by length)

Total number of leaf primes (broken down by length)

The maximal length of any TP

All TP of that maximal length

For efficiency, we maintain all numbers as integers, not as digit strings.

Computation for Base 24

For base 24, we generated all primes up to length k=4, which leads to 3808 candidates, which we then searched in parallel.

The mean run time for these searches was 120s (maximum was 320s, minimum 0s), distributed like this:

Total sequential run time: 459057s (127h)
on 22 processors: less than 6 hours.

Results

Leaf primes: 379588962
total primes: 1052029701
Max length: 53
Longest: 2 primes

iString[24]/@{
6997213457896526144782582688136864268187169945479351735670318624180389243,10594160686143126162708955915379656211582267119948391137176997290182218433}

Estimated storage size for all leaf primes (as base b strings): 8.5GB

Length Distribution

Theoretical Results:
Number of Primes for a given Base

How many TP can we expect for a given base b?

Let p be a k-digit prime to base b, and  β=(b^k). The candidates form an arithmetic progression with increment β. The prime number theorem for arithmetic progressions (Dirichlet, Legendre, de la Vallée Poussin) applies, because gcd(p,β)=1.

The number of primes in the arithmetic progression with starting point p and increment β up to x is

(Subscript[π, β,p])(x)∼(1/(ϕ(β)))Li(x)

ϕ is the Euler totient function and  x=b β=(b^(k+1)) is the upper limit of the progression in our case, because we are interested in the values a+β, a+2β, …, a+(b-1)β.

https://en.wikipedia.org/wiki/Prime_number_theorem#Prime_number_theorem_for_arithmetic_progressions

Angell, I. O., and H. J. Godwin. "On Truncatable Primes." Mathematics of Computation 31, no. 137 (1977): 265-67. doi:10.2307/2005797.
https://www.ams.org/journals/mcom/1977-31-137/S0025-5718-1977-0427213-2/S0025-5718-1977-0427213-2.pdf

exp[b_,k_]:=N[LogIntegral[b^(k+1)]/EulerPhi[b^k]]

ListPlot[Table[{b,exp[b,20]},{b,3,99}],LabelingFunction->(First@#&)]

Comparison with Measurements

Yellow are the actual (log) counts, blue the predictions.

The Relative Abundance of Primes by Basis

The observed differences in the abundance of truncatable primes for various bases can be explained from the formula for the density of primes in arithmetic progressions. The term ϕ(β)=ϕ((b^k)) is equal to

ϕ((b^k))=(b^k)∏(1-(1/(Subscript[p, i])))

where the product runs over all distinct prime factors (Subscript[p, i]) of b. It follows that bases with many distinct small  prime factors have comparatively large numbers of truncatable primes.

Even bases have more primes than odd ones

Multiples of 6=2*3, 30=2*3*5, and 42=2*3*7 have particularly many primes

Base 30 is the smallest base whose truncatable primes have not yet been fully computed.

The Results of Several Months of Computing

ds=Dataset[Values[truncatablePrimes]]

We will use these tables for proposed updates of OEIS A103463 and A076623.

Pure Math disclaimer: PrimeQ[] is probabilistic, so these numbers should be considered upper limits. We did, however, perform a deterministic test on all longest primes reported here (and their truncations).

Wish List

Here is an (exponential) measure of expected complexity of all missing bases in ascending order.

({{91, 0.8284552308704666`}, {69, 0.8307482413014118`}, {63, 0.8651862993460739`}, {40, 0.8822521579517971`}, {95, 0.8942964385964204`}, {81, 0.8985329543148414`}, {52, 0.9274489308612405`}, {58, 0.9621774465457413`}, {36, 0.9811061464102205`}, {87, 0.9834464300101937`}, {64, 1.0006454762479713`}, {62, 1.0094551593087848`}, {93, 1.0333088112626077`}, {50, 1.039377820970976`}, {56, 1.0556560531422605`}, {75, 1.0586482718067136`}, {30, 1.0773039517661114`}, {68, 1.1132776369114907`}, {74, 1.1487162648029354`}, {99, 1.1548940771627498`}, {76, 1.2041300502365242`}, {48, 1.21009743300339`}, {82, 1.2396681075052696`}, {42, 1.2798312179569789`}, {86, 1.2846412844054742`}, {54, 1.320829316443599`}, {94, 1.3736698150101743`}, {92, 1.3822388981158629`}, {88, 1.405035877888424`}, {80, 1.4832911378910234`}, {70, 1.5621543240515015`}, {98, 1.6202922604490657`}, {72, 1.641724983055714`}, {66, 1.6900567323379811`}, {100, 1.7636296221580439`}, {60, 1.786896901263409`}, {78, 1.891079781013165`}, {96, 2.050003399353477`}, {84, 2.1562492084732634`}, {90, 2.4370558680095744`}})

How long will it take for base 30?

Extrapolations based on a small sample (second column):

Estimate: 750 single-core years.
Entirely doable, we need 10,000 cores for a one month project.

Next missing smallest bases: 36, 40, 42, 48, 50, 52, 54, 56, 58

Base 60 however, is hopeless. The maximal length is at least 92.
It is not even feasible to derive a reasonable estimate.

Import["/tmp/jack-o-lanterns-3735386_1280.jpg"]

https://pixabay.com/photos/jack-o-lanterns-lit-pumpkins-3735386/