30 March 2022

All about primes

Additive primes

... are prime numbers whose digits sum to a prime.  Given that I've resorted to using is_prime from Math::Prime::Util, there isn't much left to do.

One could try a number of ways of summing the digits.  Perhaps the neatest (version 1) is:

$sd = 0;
$sd += $1 while $n =~ m|(\d)|g;

- a single line and reasonably comprehensible, and works for a bigint.  

Another thought (version 2) was:

$n =~ s|(\d)|$1+|g;
$sd = eval($n . '0');

This inserts a plus after each digit of $n, appends a zero and evals the resulting sum.

And the arithmetic way (version 3):

while ($n > 0) {
    $sd += $n % 10;
    $n = int($n / 10);
}

So which is the most efficient?  I tested them each on a 20-digit number, running the sum a million times, and the results were:
Version 1 - 23 seconds
Version 2 - 89 seconds
Version 3 - 15 seconds.

So version 2 loses out, probably because the eval means invoking the compiler and probably also prevents any optimisation.  But probably they would all be fine for any real-world task.

Cuban primes

The first series of Cuban primes are the values of 3y^2 + 3y + 1 for y = 1, 2, ... which are prime. 

There seems little benefit in optimising the calculation, but given that we have to test for all values of y, it's worth noting that:

candidate[y]     = 3y^2       + 3y       + 1
candidate[y + 1] = 3(y + 1)^2 + 3(y + 1) + 1
   = 3y^2 + 9y + 7
   = candidate[y] + 6(y + 1)

So we can zip through the candidate values by simply adding 6(y + 1) to the previous one, and then is_prime is your friend.


No comments:

Post a Comment