PWC 167 › Circular Primes

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Task #1 this week has us finding circular primes, 3 digits or more. Circular primes are numbers that remain prime through all of their rotations. For example, since all the rotations of 113 (113, 131, and 311) are all primes, 113 is a circular prime. (131 and 311 are circular primes as well, but based on the example given with this task, we are only to give the lowest circular prime in each group.) This would correspond with OEIS A016114.

I just wrote yet another Sieve of Eratosthenes in week 164, so this time I’ll just use Math::Prime::Util. The basic algorithm I came up with is rather naïve, but effective:

for each digit d in [3..∞)
    for each prime n with d digits
        for each unique rotation r
            next digit if circular[r] or ¬prime[r]
        circular[r] ← true
        say "r is circular"

Perl Implementation

First, we’ll look at a bit of housekeeping and the two outermost loops:

my $target = 10; # How many circular primes we want
my %circ;        # $circ{n} = 1 if n is a circular prime

for (my $digits = 3; ; $digits++) {
    my ($lo, $hi) = (10**($digits-1), 10**$digits-1);

    my @primes = @{ primes($lo, $hi) };
    my %prime  = map { $_ => 1 } @primes;

N:  for my $n (@primes) { ... }

    last if scalar keys %circ >= $target;
}

Beware setting $target to any value greater than ten! I’ll get to why later in this blog post.

I chose to loop on the number of digits, and then expand that into $lo and $hi to get the min/max range for primes. I did this because $digits will come in handy in our inner loop.

I’m storing all $digits-digit primes in @primes, and also shoving that whole works into a %prime hash for fast lookups. After that, I simply loop over every prime number in the range. Let’s look at that highlighted loop now:

N:  for my $n (@primes) {
        my $rot = $n;
        for (1..$digits-1) {
            $rot = chop($rot) . $rot;
            next N if $circ{$rot} or not $prime{$rot};
        }
        say $n;
        $circ{$n} = 1;
    }

For each prime ($n), we loop $digits-1 times, and use chop to efficiently remove the last character and put it at the front of the string (rotation step). Within that loop, we simply check if any of the rotated versions are circular primes we’ve already seen, or not prime, and discard the original number if either of those are true. Otherwise, we fall through and output the original number, and add it to our hash of seen circular primes.

I could have omitted the output step and simply returned a sorted list of keys from %circ, but for our purposes here, printing each circular prime made more sense.

Why just the first ten?

The next circular prime after 199 933 is 1 111 111 111 111 111 111. It’s what’s known as a repunit, which is short for “repeated unit” (“unit” meaning 1), and is typically abbreviated as R19 (19 repeated ones). The next prime after that is R23, and every circular prime thereafter are repunits.

Obviously, finding these repunit primes via my above algorithm would be horribly space and time inefficient; it would be much, much easier to simply keep appending 1s and check if the number is prime. There’s even no need to check if those are circular, since they are automatically circular, being entirely comprised of ones. Here’s how it looks:

    # All circular primes > 6 digits are repunits
    if ($digits > 6) {
        my $n = 1 x $digits;
        say "R_$digits" if is_prime($n);
        $circ{$n} = 1;
        next;
    }

With the above support for repunits, my script finds the first 13 terms easily, up to 300 digits. The next term after that is R1031, which is a 1031 digit number. Math::Prime::Util really begins to struggle. The largest known probable example is R270343, which is a few orders of magnitude beyond what my script can handle (my script only deals in definite primes).

Circular primes up to 1023 have been exhaustively searched (not by me!). Beyond that, we have found several repunit primes, and suspect there are more. But you may be wondering if there are any more non-repunit circular primes? I don’t know, and as far as I can tell, it’s still an open question.

ch-1.pl full source.

Leave a Reply

Your email address will not be published.