# Perl Weekly Challenge 170.

My solutions (task 1 and task 2 ) to the The Weekly Challenge - 170.

Write a script to generate first 10 Primorial Numbers.

Primorial numbers are those formed by multiplying successive
prime numbers.

For example,

P(0) = 1    (1)
P(1) = 2    (1x2)
P(2) = 6    (1x2×3)
P(3) = 30   (1x2×3×5)
P(4) = 210  (1x2×3×5×7)

A canned solution may be obtained from the pn_primorial function of the package Math::Prime::Util, leading to a trivial 1-liner.

perl -MMath::Prime::Util=pn_primorial -E '\$N=shift; say "P(\$_)=", pn_primorial(\$_) for 0..\$N-1;' 10

Results:

P(0)=1
P(1)=2
P(2)=6
P(3)=30
P(4)=210
P(5)=2310
P(6)=30030
P(7)=510510
P(8)=9699690
P(9)=223092870

On the other hand, one could solve the problem from first principles, generating the prime numbers using an Eratosthenes sieve, and then multiplying the first ones. Using PDL it leads to the following 3-liner.

perl -MPDL -MPDL::NiceSlice -E '\$N=shift; \$M=\$N>6?1+\$N*(log(\$N)+log(log(\$N))):14;
\$e=ones(\$M); \$e(0:1).=0;\$e(\$_**2:-1:\$_).=0 for(2..sqrt(\$M)); \$p=sequence(\$M)->where(\$e);
say "P(\$_)=", \$_==0?1:\$p(0:\$_-1)->prodover foreach(0..\$N-1)' 10

Results:

P(0)=1
P(1)=2
P(2)=6
P(3)=30
P(4)=210
P(5)=2310
P(6)=30030
P(7)=510510
P(8)=9699690
P(9)=223092870

The commented full code follows:

1  # Perl weekly challenge 170
2  # Task 1: Primorial numbers from scratch
3  #
5  use v5.12;
6  use warnings;
7  use PDL;
8  use PDL::NiceSlice;
9  die "Usage: ./ch-1.pl N\nto obtain the first N Primorial numbers" unless @ARGV;
10  my \$N=shift; # how many desired primorials
11  my \$M=\$N>6?1+\$N*(log(\$N)+log(log(\$N))):14; #upper bound on N-th prime
12  my \$sieve=ones(\$M); # large enough Eratosthenes sieve
13  \$sieve(0:1).=0; # 0 and 1 are not primes
14  \$sieve(\$_**2:-1:\$_).=0 for(2..sqrt(\$M)); # all non-trivial multiples are not primes
15  my \$primes=sequence(\$M)->where(\$sieve); # primes correspond to non-zeroed positions in sieve
16  say "P(\$_)=", \$_==0?1:\$primes(0:\$_-1)->prodover # multiply first primes to obtain primorials
17      foreach(0..\$N-1);

Example:

./ch-1.pl 10

Results:

P(0)=1
P(1)=2
P(2)=6
P(3)=30
P(4)=210
P(5)=2310
P(6)=30030
P(7)=510510
P(8)=9699690
P(9)=223092870

You are given 2 matrices.

Write a script to implement Kronecker Product on the given 2
matrices.

For example,

A = [ 1 2 ]
[ 3 4 ]

B = [ 5 6 ]
[ 7 8 ]

A x B = [ 1 x [ 5 6 ]   2 x [ 5 6 ] ]
[     [ 7 8 ]       [ 7 8 ] ]
[ 3 x [ 5 6 ]   4 x [ 5 6 ] ]
[     [ 7 8 ]       [ 7 8 ] ]

= [ 1x5 1x6 2x5 2x6 ]
[ 1x7 1x8 2x7 2x8 ]
[ 3x5 3x6 4x5 4x6 ]
[ 3x7 3x8 4x7 4x8 ]

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

We may view a matrix as a representation of a rank-2 tensor, i.e., a function of two vectors that produces a number and that is linear in its two inputs, i.e., A(u,v)=Aijuivj (sum over repeated indices), and B(w,x)=Blmwlxm. Then we may define the tensor product C=A⊗B as a rank 4 tensor, i.e., a multilinear function that takes four vectors and produces a number, i.e., C(u,v,w,x)=A(u,v) B(w,x)=Cijkluivjwkxl, where Cijkl=AijBkl. Notice that each argument may live in a different vector space with different dimensionality. We may also interpret C as a linear function of only two arguments, each of which is built by multiplying together both first arguments, u and w, and both second arguments v and x, to form the vectors P=u⊗w and Q=v⊗x, with components Pik=uiwk and Qjl=vjxl, where ik and jl are composite indices, but may be written as single indices I, J by ordering and numbering the index pairs. Thus, if i goes from 0 to du-1 and k from 0 to dw-1, where du and dw are the dimension of the vectors u and w, then I goes from 0 upto du dw as (i,k) take the values (0,0), (0,1)(0,dw-1), (1,0), (1,1)(1,dw-1), (2,0)(du-1,0)(du-1,dw-1). Correspondingly, by permutting indices and clumping them, we may represet C by a matrix with components CIJ.

Fortunately, the Perl Data Language permits the representation of tensors as multidimensional arrays and permits reshaping them to collapse two or more dimensions into one. This allows a very simple oneliner solution.

perl -MPDL -MPDL::NiceSlice -E '(\$A, \$B)=map {pdl \$_} @ARGV; say +(\$A(*1,*1,:,:)*\$B)
->mv(1,2)-> reshape(\$A->dim(0)*\$B->dim(0), \$A->dim(1)*\$B->dim(1));' "[[1,2],[3,4]]" "[[5,6],[7,8]]"

Results:

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

The commented full code is

1  # Perl weekly challenge 170
2  # Task 2: Kronecker product
3  #
5  use v5.12;
6  use warnings;
7  use PDL;
8  use PDL::NiceSlice;
9  die "Usage: ./ch-2.pl A B\nto obtain the Kronecker product of A and B" unless @ARGV==2;
10  # The input matrices should be written as an array of rows, each row
11  # as an array of numbers and within quotes, as in  "[[1,2,3],[4,5,6]]"
12  # for a 2x3 matrix
13  my (\$A, \$B)=map {pdl \$_} @ARGV;
14  my \$C=\$A(*1,*1,:,:)*\$B(:,:,*1,*1); #use dummy indices to build tensor
15                                     #product # C_{ijkl}=A_{ij}B_{kl}
16  # Notice: PDL uses column,row notation, not the algebraic row, column
17  # Get size of each dimension
18  my (\$I, \$J, \$K, \$L)=(\$A->dim(1), \$A->dim(0), \$B->dim(1), \$B->dim(0));
19  my \$Kronecker=\$C->mv(1,2) # change indices to ikjl
20      ->reshape(\$J*\$L, \$I*\$K); # clump indices i and k, and j and l
21  say "The Kronecker product of \$A and \$B is \$Kronecker";

Example:

./ch-2.pl "[[1,2],[3,4]]" "[[5,6],[7,8]]"

Results:

The Kronecker product of
[
[1 2]
[3 4]
]
and
[
[5 6]
[7 8]
]
is
[
[ 5  6 10 12]
[ 7  8 14 16]
[15 18 20 24]
[21 24 28 32]
]
Written on June 20, 2022