5
$\begingroup$

How do we prove that there exists a finite number of truncatable primes? It's intuitive that as it gets bigger it has more factors, so less chance of it being primes when truncated, but what is the mathematical proof?

$\endgroup$
6
  • $\begingroup$ As far as I know, it's just a case-by-case analysis. Find all the $2$-digit truncatable primes. Then find all the three digits. Note that if you have an $n+1$-digit truncatable prime, then dropping the first or last must also return a truncatable prime. Eventually, you can just list them all. $\endgroup$ Oct 4, 2016 at 18:38
  • $\begingroup$ So proof be exhaustion is the only way? $\endgroup$
    – pbsh
    Oct 4, 2016 at 18:39
  • $\begingroup$ Well, "only way" is a bit strong, but I suspect it is the best way. $\endgroup$ Oct 4, 2016 at 18:40
  • $\begingroup$ (It would certainly be interesting if one could prove this true in any base, so finding a non-exhaustive solution might help us generalize.) $\endgroup$ Oct 4, 2016 at 18:45
  • $\begingroup$ Mathematically, if there are $M$ truncatable primes with $n$ digits in base $b$, then, by chance, we'd expect there to be approximate $2M(b-1)\frac{\pi(b^n)}{b^n} \approx 2M(b-1)\frac{1}{n\log b}$ of $n+1$ digit truncatable primes. That gives a heuristic to expect it is true for all bases, but, obviously, not a proof. $\endgroup$ Oct 4, 2016 at 18:54

1 Answer 1

1
$\begingroup$

You build up the truncatable primes digit-by-digit. For n > 1, the set of n-digit truncatable primes is just the prime numbers which are (n-1)-digit truncatable primes with an extra digit tacked onto the left or right. If you try all 10 digits and none of them work, then there are no n-digit truncatable primes, and hence no (n+1)-digit truncatable primes, and so on. If you start from the set of one-digit primes you eventually reach that point whether going left or right. By following this process you also build the full list of that type of truncatable prime.

$\endgroup$
4
  • $\begingroup$ It works pretty well for base 10. But if I choose a extremely large base, then the exhaustive method becomes just pointless right? $\endgroup$
    – pbsh
    Oct 4, 2016 at 18:51
  • $\begingroup$ @Segmentation_fault It can be hard with big bases, yes. For any base we expect that there would be only finitely many, but if it's large enough it could be quite hard to prove. $\endgroup$
    – Charles
    Oct 4, 2016 at 20:56
  • $\begingroup$ > the set of n-digit truncatable primes is just the prime numbers which are (n-1)-digit truncatable primes with an extra digit tacked onto the left or right < Note that the (n-1)-digit prime only has to be either of left-truncatable or right-truncatable, not necessarily both sides truncatable. So one has to maintain a list of left-trunc and right-trunc primes at each stage, in addition to the actual truncatable primes. Then try each of 3, 5, 7, 9 (not all 10 digits since result should be prime) tacked onto these ones' left or right and check if you get left-trunc and right-trunc primes. $\endgroup$
    – Sundar R
    Jun 1, 2018 at 19:56
  • $\begingroup$ (For eg. there's no 5-digit truncatable prime, but there's a 6-digit one because there are 5-digit left-truncatable 39397 and right-truncatable 73939 primes that make up the 6-digit truncatable prime 739397 together.) $\endgroup$
    – Sundar R
    Jun 1, 2018 at 19:59

You must log in to answer this question.

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