5

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?

Thomas Andrews
  • 177,126
pbsh
  • 166
  • 4
  • 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. – Thomas Andrews Oct 04 '16 at 18:38
  • So proof be exhaustion is the only way? – pbsh Oct 04 '16 at 18:39
  • Well, "only way" is a bit strong, but I suspect it is the best way. – Thomas Andrews Oct 04 '16 at 18:40
  • (It would certainly be interesting if one could prove this true in any base, so finding a non-exhaustive solution might help us generalize.) – Thomas Andrews Oct 04 '16 at 18:45
  • 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. – Thomas Andrews Oct 04 '16 at 18:54
  • @Thomas andrews exactly my thought too. I just wanted to know if there exists a more rigours way than arriving at a heuristic. – pbsh Oct 04 '16 at 18:57

1 Answers1

1

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.

Charles
  • 32,122
  • It works pretty well for base 10. But if I choose a extremely large base, then the exhaustive method becomes just pointless right? – pbsh Oct 04 '16 at 18:51
  • @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. – Charles Oct 04 '16 at 20:56

  • 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.

     – Sundar R Jun 01 '18 at 19:56
  • (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.) – Sundar R Jun 01 '18 at 19:59