30 May 2022

Prime, ePrim, mePri, imePr, rimeP ... and Gamma

Circular primes

Task 1 asks us to identify the first 10 circular primes: that is, prime numbers which when permuted by repeatedly moving the last digit to the start are still prime.

Although not stated, but implied by the supplied answer, the answers are all the lowest value permutation of the given string of digits - so for example 197 is an answer but not 719 or 971.

My simple solution uses good old Eratosthenes's sieve to generate the primes. Then for each prime we can permute the digits, immediately moving on the next candidate if:

  • the permuted value is not prime, or
  • the permuted value matches an already-identified circular prime (for the reason stated in the second paragraph above)
Since Mohammad was kind enough to share the answer, we know that the 10th circular prime is a 6-digit number - 199 933 - and we might be tempted to limit the size of our sieve to that number.  However, some of its permutations considerably exceed the number itself, for example 999 331, so I ran the sieve up to 1 000 000.

I debated how to permute the digits of a multidigit number and settled on:

$c =~ m|(.*)(.)|;
$c = $2 . $1;

It's been stated in previous reviews that substr() is faster:

$c = substr($c, 1, 99) . substr($c, 0, 1);

but I couldn't measure the difference - if any.

Gamma functions

It's just about 50 years since I completed my PhD and I don't recall using a gamma function since then. I do, though, remember that for an integer j, gamma(j) is (j-1)! But that doesn't help much.

Fortunately the kind people at Wikipedia have provided some Python code to implement the required approximation, and I was able to translate that easily into Perl, handling the complex numbers with Math::Complex. I'd never used Math::Complex before, and I must say it's very easy to use - compared, for example, to BigInt.

Now you could complain that I haven't really answered the question because I didn't compute the parameters, but at least I've produced working code, and in the real world, that's what counts.


No comments:

Post a Comment