Left Truncatable Prime
Pretty cool.
I first learned about truncatable primes from Project Euler problem 37: "Find the sum of the only eleven primes that are both truncatable from left to right and right to left."
https://projecteuler.net/problem=37
(I have some rust code that solves this problem in ~300 microseconds on my laptop. I bet it's possible to get it faster though. Anyone want to try?)
When written in base 10, anyway :)
I suppose an extra challenge would be to find values which are truncatable primes in more than one base at once... Hmmm.
The primality test uses Fermat's Little Theorem, but I thought it was not 100% perfect. (Or perhaps it is for left-truncatable primes?)
I didn't know about the third parameter in pow(), either. Quite interesting.
I wonder how long one could be if we only require it to stay prime when it has more than K digits? Take K=0 to get the original problem.
In this form of the problem, it is not the length, L, of the initial prime that we want to maximize but rather L-K.
My guess is that these looser requirements won't make much difference. Estimating based on the prime number theorem and pretending that primes are essentially random numbers (an assumption that works remarkably well a large fraction of the time), I get, if I didn't totally botch it, that given a k digit integer that is prime, there is about a 1/(2k) chance that you can add a digit on the left and still have a prime.
Another generalization comes to mind. Suppose that instead of a pencil, we are dealing with some item with break-away segment. Each segment has d digits printed on it, so when we have L segments we have a dL digit number. As we break away segments we left truncate this number by d digits.
I don't think that would make much of a difference. We can treat it as an L digit number in base 10^d, which we truncate a digit at a time. Another hand wavy application of prime number theorem gives 1/(2kd) as the chance that you can left-extend a k digit base 10^d prime by one digit and get a prime.
What if we allowed 0 as a digit?
Are there infinitely many 0-enabled left-truncatable primes?
AFAICT, The code would never find a prime of the form 100p
The article mentions a "DON'T DO DRUGS" pencil. The actual pencil, distributed in 1998 by the Bureau for At-Risk Youth, was even funnier. It said "TOO COOL TO DO DRUGS", and apparently the company had no clue what would happen as you sharpened it:
◄ TOO COOL TO DO DRUGS
◄ COOL TO DO DRUGS
◄ DO DRUGS
◄ DRUGS
Someone has even done a remake of the pencil:
It's fun to see this. I investigated these on my own as an undergrad, but I called them solid primes. Originally I wrote a visual basic program (it was a long time ago) to find all the solid primes in base ten, which obviously involved writing a big num implementation. It ran for three days, only half solved the problem and then ran out of memory. Recoding it in Mathematica took 6 lines, ran in 20 minutes and found all of them.
Plotting the distribution gives a nice curve which you can model quite well with the prime number theorem. From memory it looks like x^2*e^-x. Then plotting in different bases is also interesting.