One Eye on the Primetime Slot

Wherein we continue our grind onwards with a unique, singular focus…

THE WEEKLY CHALLENGE – PERL & RAKU #177 Task 2

---

“There is nothing wrong with photography, if you don’t mind the perspective of a paralysed Cyclops.”

— David Hockney

---

Palindromic Prime Cyclops

Submitted by: Mohammad S Anwar

Write a script to generate first 20 Palindromic Prime Cyclops Numbers.

A cyclops number is a number with an odd number of digits that has a zero in the center only.

Output

101, 16061, 31013, 35053, 38083, 73037, 74047, 91019, 94049,
1120211, 1150511, 1160611, 1180811, 1190911, 1250521, 1280821,
1360631, 1390931, 1490941, 1520251

ANALYSIS

This is a good problem to solve constructivly rather than mathematically.

Lets start by divide it into 3 cases, for each of the first odd numbers for the digits. Within each class it is straightforward to calculate the constraints on every solution that can exist. If we need to we can continue for larger odd numbers, but three should establish a pattern.

One Digit

There is only one number available with one digit, and I’m not sure it can even be called a cyclops number. It also isn’t prime.

0

Three Digits

There are nine three-digit cyclops numbers:

x0x     | 0 < x ≤ 9

Five Digits

There are eighty-one numbers that fit the pattern for five digits. Remember that we can only have a single, central eye (the zero).

xy0yx   | 0 < x ≤ 9

So what can we deduce from what’s happening here?

Well, if we start with an ordered left-hand sequence of values there can only be one palindromic number created for each left-hand component. The mirrored right-hand side is therefore inconsequential to the ordering, as we will have no two numbers that only differ in their right-hand positions.

So for each class we observe the ordering is entirely determined by only the left-hand side of the number.

Essentially, then, we can constructively create an ordered list of palindromes by counting incrementally upwards from the smallest valid left-hand component. Starting with some value, we then affix a 0 digit followed by the reversed representation of the seed value. By convention we should not allow leading zeros, but that point is moot because, as mentioned earlier, a Cyclops can only have one eye.

One additional constraint is added by the primality criterion. The last digit must be odd for any prime greater than 2, and also cannot be 5. So therefore, because the right side is the left reversed, the first digit is the same as the last. This limits the leftmost digit to 1, 3, 7, or 9.

METHOD

Although we used three cases to study the construction of the palindromes, there is no logical reason to restrict the general assessment to only these cases — any number of digits can be used to construct a seed. If the seeds are ordered, the output will remain that way.

PERL 5 SOLUTION

The tricky part proved to be creating a system of nested loops to produce valid seeds with increasing numbers of digits. Yes, we could have just started counting at 1 and tossed out any disallowed first digits, but this would involve a lot of checking and is obviously inefficient — you’re throwing out half the candidates. Perhaps we don’t care, but I want to produce the ordered finished sequence in-place and as ready to use as possible because, well, I feel like it. This requires a second loop to create all numbers with a certain number of digits for a given odd start digit, progressing through the start digit list before moving on to numbers with an additional digit in the tail portion.

I like the result. It’s neat.

To check for primality I use the is_prime() function from Math::Prime::Util, here referred to by its street name ntheory.

Respect.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';

use ntheory qw( is_prime );

my @out;
my $tail_digits = 0;

while ( @out < 200 ) {
    for my $head ( 1, 3, 7, 9 ) {
        my $start = "1" x $tail_digits;
        my $end   = "9" x $tail_digits;
        for my $tail ($start .. $end) {
            next if $tail =~ /0/;          ## one eye only!
            my $candidate =  "$head$tail" . 0 . reverse "$head$tail";
            push @out, $candidate if is_prime( $candidate );
        }
    }
    $tail_digits++;
}

say for @out;