laurent_r

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

Spoiler Alert: This weekly challenge deadline is due in a few days from now (on December 26, 2021 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: Semiprimes

Write a script to generate all Semiprime number <= 100.

For more information about Semiprime, please checkout the Wikipedia page.

In mathematics, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers.

Example:

10 is Semiprime as 10 = 2 x 5
15 is Semiprime as 15 = 3 x 5

Semiprimes might look like a somewhat useless curiosity, but they are in fact extremely important in the field of public key cryptography. For example, generating the public and private keys for a RSA cipher involves generating two very large prime numbers (with several dozens of digits) and computing their product. Raku has built-in features to quickly create RSA keys (and also to encode messages and decode cryptograms): arbitrary precision integers, an efficient is-prime primality test (using the fast Miller-Rabin test) and modular arithmetic. See this for further details. But that’s another subject.

Semiprimes in Raku

We start by generating a list of prime numbers between 1 and 50. Then we want to generate all pairs of such primes. Since we also want square semiprimes (i.e. numbers that are squares of prime numbers), we cannot use the combinations method. We will use instead the X cross product operator between the array of primes and itself, multiply the pair items, filter out those which are too large, sort them and remove duplicates.

use v6;

constant \MAX = 100;
my @primes = grep { .is-prime }, 1..MAX/2;
my @nums = grep { $_ <= MAX }, map { [*] $_[0,1] }, 
    (@primes X @primes);
say @nums.sort.squish;
# say now - INIT now;

This program displays the following output:

$ raku ./semi-primes.raku
(4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95)

Semiprimes in Perl

Our Perl implementation is essentially a port of the Raku implementation, except that we had to roll out our primessubroutine for generating a list of prime integers, and to use two nested loops for generating the pairs of primes.

use strict;
use warnings;
use feature "say";
use constant MAX => 100;

sub primes {
    my $max = shift;
    my @primes = (2, 3, 5);
    PRIMES: for my $c (7..$max/2) {
        for my $i (2..$c/2) {
            next PRIMES unless $c % $i;
        }
        push @primes, $c;
    }
    return @primes;
}

my @p = primes MAX;
my @semi_primes;
# Generating pairs of primes and their product 
for my $i (0..$#p) {
    for my $j (0..$i) {
        my $product = $p[$i] * $p[$j];
        push @semi_primes, $product if $product <= MAX;
    }
}
my @result;
my $j = -1;
# Removing duplicate products
for my $i (sort {$a <=> $b} @semi_primes) {
    push @result, $i if $i != $j;
    $j = $i;
}
say "@result";

This program displays the following output:

$ perl semi-primes.pl
4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95

Task 2: Ulam Sequence

You are given two positive numbers, $u and $v.

Write a script to generate Ulam Sequence having at least 10 Ulam numbers where $u and $v are the first 2 Ulam numbers.

For more information about Ulam Sequence, please checkout this website.

The standard Ulam sequence (the (1, 2)-Ulam sequence) starts with U1 = 1 and U2 = 2. Then for n > 2, Un is defined to be the smallest integer that is the sum of two distinct earlier terms in exactly one way and larger than all earlier terms.

Example 1:

Input: $u = 1, $v = 2
Output: 1, 2, 3, 4, 6, 8, 11, 13, 16, 18

Example 2:

Input: $u = 2, $v = 3
Output: 2, 3, 5, 7, 8, 9, 13, 14, 18, 19

Example 3:

Input: $u = 2, $v = 5
Output: 2, 5, 7, 9, 11, 12, 13, 15, 19, 23

The fact that a member of the sequence has to be “the smallest integer that is the sum of two distinct earlier terms in exactly one way” makes it quite difficult to construct the number directly from the previous ones. For example, suppose we have so far 1, 2, 3, 4. It would probably possible to find the next one. But the fact that it has to be the sum “in exactly one way” excludes 5 from the sequence, because it can be reached in two ways (1 + 4 and 2 + 3). But to be able to find that, we basically need to build all possibilities. In other words, we basically need a brute force approach: find all pairs of previous terms, perform the sums and find the smallest unique sum that is larger than the largest previous term. In the process, we can possibly improve the process by pruning values that are too small or too large, to reduce the number of values to examine, but it is still basically a brute force approach.

Note that the task specification asks us to find “at least 10 Ulam numbers”. I’ve decided to generate 12 Ulam numbers, i.e. 10 numbers in addition to the two seeds. This wasn’t requested, but it is still in line the the requirement of providing at least 10 Ulam numbers.

Ulam Sequence in Raku

For a given existing sequence of numbers, we use the combinations method to generate all possible pairs, sum each of them, compute the sums, filter out the sums that are too small and sort them. Then we loop on the resulting list, remove the duplicates and insert in the sequencearray the first valid candidate. And we start again with the new sequence and do it ten times in total.

uses v6;

sub ulam ($first, $second) {
    my @sequence = $first, $second;
    for 1..10 {
        my @sums = sort grep { $_ > @sequence[*-1] }, 
            map { [+] $_[0, 1] }, @sequence.combinations: 2;
        my $last = 0;
        for 0..@sums.end -> \i {
            next if @sums[i] == $last;
            push @sequence, @sums[i] and last if i >= @sums.end;
            $last = @sums[i] and next if @sums[i] == @sums[i+1];
            push @sequence, @sums[i] and last;
        }
    }
    return @sequence;
}
for (1,2), (2,3), (2,5) -> $test {
  say "$test => ", ulam |$test;

}

This program displays the following output:

$ raku ./ulam_seq.raku
1 2 => [1 2 3 4 6 8 11 13 16 18 26 28]
2 3 => [2 3 5 7 8 9 13 14 18 19 24 25]
2 5 => [2 5 7 9 11 12 13 15 19 23 27 29]

Ulam Sequence in Perl

This is essentially a port to Perl of the Raku solution above, except that we had to implement our own combine subroutine to replace the Raku built-in combination method.

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

sub combine {
    my @seq = @_;
    my $min = $seq[-1];
    my @comb_sums;
    for my $i (0..$#seq) {
        for my $j (0..$i-1) {
            my $sum =  $seq[$i] + $seq[$j];
            next if $sum <= $min;
            push @comb_sums, $sum;
        }
    }
    return sort { $a <=> $b } @comb_sums;
}

sub ulam {
    my @sequence = @{$_[0]};
    for (1..10) {
        my @sums = combine @sequence;
        my $last = 0;
        for my $i (0..$#sums) {
            next if $sums[$i] == $last;
            push @sequence, $sums[$i] and last if $i >= $#sums;
            $last = $sums[$i] and next if $sums[$i] == $sums[$i+1];
            push @sequence, $sums[$i] and last;
        }
    }
    return @sequence;
}
for my $test ([1,2], [2,3], [2,5]) {
    say "@$test => ", join " ", ulam $test;
}

This program displays the following output:

1 2 => 1 2 3 4 6 8 11 13 16 18 26 28
2 3 => 2 3 5 7 8 9 13 14 18 19 24 25
2 5 => 2 5 7 9 11 12 13 15 19 23 27 29

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 January 2, 2022. And, please, also spread the word about the Perl Weekly Challenge if you can.