Chop off their heads and conquer the Pentagon (week 147)

Chop off their heads!

Task 1 this week asks us to write a script to generate first 20 left-truncatable prime numbers in base 10.

A left-truncatable prime (LTP) is a prime number which, in a given base, contains no 0, and if the leading left digit is successively removed, then all resulting numbers are primes.

In principle this is easy enough: generate the primes using a sieve of our good friend Eratosthenes, discard any containing zeroes, and check the remainder for being left-truncatable. 

I chose to exclude single digit primes, ie 2, 3, 5, and 7 because I felt that they did not meet the criterion of 'all resulting numbers are primes', because there are no resulting numbers.

The next 16 LTPs are only 2 digits - they range from 11 to 97, and 4 more - 113, 131, 137 and 167 complete the required 20. The computing time is negligible.

However, had the task asked for the first 1000, or 10 000 LTPs it would be worth applying a little optimisation.  For example, the last digit of an LTP can only be 1, 3 or 7, since any number ending in 0, 2, 4, 5, 6 or 8 is not prime, any ending in 9 will fail the LTP test when only that digit remains.

So doing that I found 1000 LTPs in 3 seconds.

I then tried for 10 000.  It is interesting to note that 33333331 is an LTP, meaning that 33333331, 3333331, 333331, 33331, 3331, 331, 31 are all primes.  Could it be that any number of 3s followed by 1 is an LTP?

It took quite a while because they get steadily sparser, and my computer ran out of memory before getting to the 10 000th. The last one it found was 999 779 337.

Conquer the Pentagon

For task 2 we are asked to write a script to find the first pair of Pentagon Numbers (PNs) whose sum and difference are also a Pentagon Number. Pentagon Numbers are defined by P(n) = n(3n - 1)/2.

My first attempt at this worked, but was rather slow. I generated successive PNs, checked the difference between each new one and all the preceding ones, thus creating a queue of pairs which met the difference criterion.

I then continued generating PNs, and when I got to one that matched one of the queued sums, I had a result. 

Although we were only asked for the first pair, I wanted to find the second pair, so I deleted from the queue the one I had identified as a solution to the task, and also deleted any whose sums were less than that, but despite leaving this running for 15 minutes or so, I found no other qualifying pair. So either my method is faulty, or they are pretty rare, or maybe there is only one.

I mentioned that that was my first attempt.  My second attempt - the one I have submitted - was faster. I used the fact, gleaned from Wikipedia, that any PN gives an integer result in this formula:

(sqrt(24 * PN + 1) + 1) / 6

Using this avoids the need for my queue and the need to identify any PNs beyond the larger member of the pair.  

I am happy to say that both methods came up with the same answer, and despite its improved speed the second method also failed to find a second qualifying pair.

I did worry about applying the Wikipedia formula, because determining that a floating point operation results in an integer result is a little tricky.  For example, in some contexts, this:

$x = 1/3;
$y = $x + $x + $x;
say int($y);

results in 0 rather than the expected 1.  This is, roughly, because 0.333 + 0.333 + 0.333 = 0.999 which truncates to 0.  Happily Perl, on my system at least, does not make that error.