PWC 170 › Primordial Numbers and Kronecker Products

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.)

We’re back with our noses to the mathematical grindstone this week, with two straightforward tasks.

Task 1 › Primordial Numbers

The n^th primordial number is simply the product of the first n primes. P(1) = 2, P(2) = 2×3 = 6, P(3) = 2x3x5 = 30, etc. P(0) is defined to be 1 as a special case. Since I’ve implemented various prime number generators before, I just went with Math::Prime::Util for this one, making use of the prime_iterator function:

my $it = prime_iterator;

say my $pri = 1; # P(0) = 1 by definition
say $pri *= $it->() for 1..$ARGV[0] // 10;

Easy.

Task 2 › Kronecker Products

I haven’t worked with Kronecker products for quite a few years, so when I reviewed the definition, I thought it might be tricky to implement, so I got a fresh caffeinated beverage, but much to my dismay, it was all over before my second sip.

Please do check that link for a more rigorous definition of Kronecker products. As a quick review, I will simply show an example, with ⨂ as the operator for the Kronecker product:

\(A = \begin{bmatrix}2 & 3 \\ 4 & 5 \end{bmatrix} \\
B = \begin{bmatrix}a & b \\ c & d \end{bmatrix} \)

\(A ⨂ B = \begin{bmatrix}
2 & 3 \\
4 & 5
\end{bmatrix} ⨂
\begin{bmatrix}
a & b \\
c & d
\end{bmatrix} =
\begin{bmatrix}
2B & 3B \\ 4B & 5B
\end{bmatrix} =
\begin{bmatrix}
2a & 2b & 3a & 3b \\
2c & 2d & 3c & 3d \\
4a & 4b & 5a & 5b \\
4c & 4d & 5c & 5d
\end{bmatrix}
\)

To make this happen, I opted to loop over the total number of rows in A ⨂ B and use division and modulo arithmetic to determine which sub-row and -column in B we need. I use a triple-nested map to achieve the multiplications and orderings of the final matrix.

sub kronecker {
    my ($A, $B) = @_;

    map {
        my $i = $_;
        [
            map { 
                    my    $aval = $_;
                    map { $aval * $_ } $B->[$i % @$B]->@*;
            } $A->[$i / @$B]->@*
        ]
    } 0..(@$A * @$B)-1;
}

The post-deref (->@*) looked a bit cleaner here, so I went with that, but @{$B->[$i % @$B]} would have worked just as well.

The result is a list of array refs containing the rows of the final product. The problem description didn’t specify, but I opted to also include a pretty-print routine to display the output a little nicer than Data::Dump can:

sub pp_matrix {
    print '[ ' . join(' ', map { sprintf '%3d', $_ } @$_). " ]\n" for @_
}

The output from pp_matrix(kronecker([[1,2],[3,4]], [[5,6],[7,8]])) is nicely formatted:

[   5   6  10  12 ]
[   7   8  14  16 ]
[  15  18  20  24 ]
[  21  24  28  32 ]

We were only asked to implement the solution for a product of two specific 2×2 matrices, but both of the above subs accept arbitrary shaped matrices.