laurent_r

These are some answers to the Week 164 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few of days from now (on May 15, 2022 at 24:00). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 1: Prime Palindromes

Write a script to find all prime numbers less than 1000, which are also palindromes in base 10. Palindromic numbers are numbers whose digits are the same in reverse. For example, 313 is a palindromic prime, but 337 is not, even though 733 (337 reversed) is also prime.

Prime Palindromes in Raku

We use a data pipeline (chained method invocations) with two grep statements, one to keep palindromes and one to keep prime numbers. This leads to a fairly concise one-line solution:

say (1..^1000).grep({ $_ == .flip }).grep({.is-prime});

This works because, with such chained method invocations, the output of the first grep is fed as input to the second grep. This script displays the following output:

$ raku ./prime-palindrome.raku
(2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929)

We can also do it as a Raku one-liner:

$ raku -e 'say (1..^1000).grep({ $_ == .flip }).grep({.is-prime});'
(2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929)

Prime Palindromes in Perl

Perl doesn’t have a built-in function to determine whether an integer is prime, so we write our own is_prime subroutine. Since we’re eventually going to test only slightly more than 100 small integers, there is no need to aggressively optimize the performance of this subroutine. The program runs in significantly less than a tenth of a second.

Once we have implemented the is-prime subroutine, we can use a data pipeline (piped function calls) as before to solve the problem in just one code line:

use strict;
use warnings;
use feature "say";

sub is_prime {
    my $num = shift;
    return 1 if $num == 2;
    return 0 unless $num % 2;
    my $test = 3;
    while ($test < $num/2) {
        return 0 if $num % $test == 0;
        $test += 2;
    }
    return 1;
}

say map "$_ ", grep { is_prime $_} grep {$_ == reverse $_} 1..999;

This data pipeline should be read from right to left: we start with a range of integers between 1 and 999, apply a first filter (grep {$_ == reverse $_}) to keep only the palindromic integers, apply a second filter to retain only the primes, and finally a map to properly format the output (add a space between the values).

This program displays the following output:

$ perl ./prime-palindrome.pl
1 2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929

Task 2: Happy Numbers

Write a script to find the first 8 Happy Numbers in base 10. For more information, please check out Wikipedia.

Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.

Those numbers for which this process end in 1 are happy numbers, while those numbers that do not end in 1 are unhappy numbers.

Example:

19 is Happy Number in base 10, as shown:

19 => 1^2 + 9^2
   => 1   + 81
   => 82 => 8^2 + 2^2
         => 64  + 4
         => 68 => 6^2 + 8^2
               => 36  + 64
               => 100 => 1^2 + 0^2 + 0^2
                      => 1 + 0 + 0
                      => 1

Basically, we need a subroutine to perform iteratively the process of replacing the current number with the sum of the squares of its digit. If we find 1, then we’ve found an happy number and can return a true value to break out of the process. If we find a number that we have already seen, then we have entered into an endless loop, which means that have found an unhappy (or sad) number, and we can return a false value to break out of the process.

Happy Numbers in Raku

The is-happy subroutine implements the algorithm described above. We use a SetHash to store the intermediate values and check whether we have entered into an endless loop. Note that we create an infinite lazy list of happy numbers, and then print out the number of happy numbers that we need.

sub is-happy(Int $n is copy) {
    my $seen = SetHash.new;
    loop {
        return True if $n == 1;
        return False if $n ∈ $seen;
        $seen{$n} = True;
        $n = $n.comb.map({$_ ** 2}).sum;
    }
}
my @happy-numbers = grep {is-happy $_}, 1..Inf;
say @happy-numbers[0..7];

This program displays the following output:

$ raku ./happy-numbers.raku
(1 7 10 13 19 23 28 31)

Happy Numbers in Perl

In Perl, the is_happy subroutine implements again the algorithm outlined above. We use a plain hash to store the intermediate values and check whether we have entered into an endless loop.

use strict;
use warnings;
use feature "say";

sub is_happy {
    my $n = shift;
    my %seen;
    while (1) {
        return 1 if $n == 1;
        return 0 if exists $seen{$n};
        $seen{$n} = 1;
        my $sum = 0;
        $sum += $_ for map $_ ** 2, split //, $n;
        $n = $sum;
    }
}
my $count = 0;
my $i = 1;
while ($count < 8) {
    if (is_happy $i) {
        print "$i ";
        $count++;
    }
    $i++;
}
say "";

This program displays the following output:

$ perl ./happy-numbers.pl
1 7 10 13 19 23 28 31

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on May 22, 2022. And, please, also spread the word about the Perl Weekly Challenge if you can.