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 ninety numbers that fit the pattern for five digits.

xy0yx   | 0 < x ≤ 9
        | 0 ≤ y ≤ 9

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

Well, if we start with an ordered left-hand sequence of values there will only be one single 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 zeros1, so the furthest left digit will be in the range 1 to 9 and all the others 0 through 9.

One additional constraint is added by the primality criterion. The last digit must be odd for any prime greater than 2, 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, 5, 7, or 9.


1 Even if we were allow leading zeros the resultant palindrome would never be prime, but we’ll get to that next.

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 and 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 odd 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 chose to produce the ordered finished sequence in-place and ready to use because I felt 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, 5, 7, 9 ) {
        my $start = "0" x $tail_digits;
        my $end   = "9" x $tail_digits;
        for my $tail ($start .. $end) {
            my $candidate =  "$head$tail" . 0 . reverse "$head$tail";
            push @out, $candidate if is_prime( $candidate );
        }
    }
    $tail_digits++;
}

say for @out;


The Perl Weekly Challenge, that idyllic glade wherein we stumble upon the holes for these sweet descents, is now known as

The Weekly Challenge – Perl and Raku

It is the creation of the lovely Mohammad Sajid Anwar and a veritable swarm of contributors from all over the world, who gather, as might be expected, weekly online to solve puzzles. Everyone is encouraged to visit, learn and contribute at

https://theweeklychallenge.org