# Perl Weekly Challenge 144.

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

``````Submitted by: Mohammad S Anwar
Write a script to generate all Semiprime number <= 100.

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
``````

One way to generate the semiprimes in a given range is to first generate the primes and then multiply them among themselves. This is easily done with `PDL` and fits in three lines.

``````perl -MPDL -MPDL::NiceSlice -E '\$p=ones(101);\$p(0:1).=0;
\$p(\$_**2:-1:\$_).=0 for(2..sqrt(100));\$p=\$p->xvals->where(\$p);
\$sp=cat(\$p,\$p(*))->mv(-1,0)->prodover;say \$sp=\$sp->where(\$sp<=100)->uniq;'
``````

The results are

``````[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]
``````

The full version is

`````` 1  # Perl weekly challenge 144
3  #
5  use v5.12;
6  use warnings;
7  use PDL;
8  use PDL::NiceSlice;
9  my \$N=shift//100; # get upper limit from command line
10  my \$sieve=ones(\$N+1); #Erastothenes sieve
11  \$sieve(0:1).=0; #0 and 1 are not primes
12  \$sieve(\$_**2:-1:\$_).=0 for(2..sqrt(\$N)); #remove non-primes
13  my \$primes=\$sieve->xvals->where(\$sieve);
14  my \$pairs=cat(\$primes, \$primes(*))->mv(-1,0); # pairs of primes
15  my \$sp=\$pairs->prodover; # semiprimes
16  my (\$p1, \$p2, \$semiprimes)=where(\$pairs((0)), \$pairs((1)), \$sp,
17                 (\$sp->xvals>=\$sp->yvals)&(\$sp<100));
18  my \$indx=\$semiprimes->qsorti; # order results
19  my (\$p1_o,\$p2_o,\$semiprimes_o)=map {\$_->(\$indx)} (\$p1, \$p2, \$semiprimes);
20  say "The semiprimes not greater than \$N are";
21  say \$semiprimes_o((\$_)), "=", \$p1_o((\$_)), "*", \$p2_o((\$_))
22      foreach 0..\$indx->nelem-1;
23
``````

This can be run as

``````./ch-1.pl 100
``````

yielding

``````The semiprimes not greater than 100 are
4=2*2
6=3*2
9=3*3
10=5*2
14=7*2
15=5*3
21=7*3
22=11*2
25=5*5
26=13*2
33=11*3
34=17*2
35=7*5
38=19*2
39=13*3
46=23*2
49=7*7
51=17*3
55=11*5
57=19*3
58=29*2
62=31*2
65=13*5
69=23*3
74=37*2
77=11*7
82=41*2
85=17*5
86=43*2
87=29*3
91=13*7
93=31*3
94=47*2
95=19*5
``````

``````Submitted by: Mohammad S Anwar
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.

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
``````

I solve this in a straightforward and surely inefficient way. For a given Ulam partial sequence I perform all possible sums, remove the diagonal contributions, remove the previous results, remove duplicates, choose the smallest remaining term and add it to the set. Then I iterate until I get all desired terms. With PDL I can fit the solution in three lines.

``````perl -MPDL -MPDL::NiceSlice -E '
\$u=pdl((@ARGV));foreach(3..10){\$s=\$u+\$u(*);\$w=\$s->where((\$s->xvals>\$s->yvals)
&\$s>\$u((-1)))->qsort;\$w=\$w->where((\$w!=\$w->rotate(-1))&(\$w!=\$w->rotate(1)))if \$w->nelem>1;
\$u=\$u->append(\$w((0)));} say \$u;' 1 2

perl -MPDL -MPDL::NiceSlice -E '
\$u=pdl((@ARGV));foreach(3..10){\$s=\$u+\$u(*);\$w=\$s->where((\$s->xvals>\$s->yvals)
&\$s>\$u((-1)))->qsort;\$w=\$w->where((\$w!=\$w->rotate(-1))&(\$w!=\$w->rotate(1)))if \$w->nelem>1;
\$u=\$u->append(\$w((0)));} say \$u;' 2 3

perl -MPDL -MPDL::NiceSlice -E '
\$u=pdl((@ARGV));foreach(3..10){\$s=\$u+\$u(*);\$w=\$s->where((\$s->xvals>\$s->yvals)
&\$s>\$u((-1)))->qsort;\$w=\$w->where((\$w!=\$w->rotate(-1))&(\$w!=\$w->rotate(1)))if \$w->nelem>1;
\$u=\$u->append(\$w((0)));} say \$u;' 2 5
``````

The results are

``````[1 2 3 4 6 8 11 13 16 18]
[2 3 5 7 8 9 13 14 18 19]
[2 5 7 9 11 12 13 15 19 23]
``````

For the full version I avoid some unnecesary operations by keeping a list of candidate Ulam numbers and only summing the newly found numbers.

`````` 1  # Perl weekly challenge 144
2  # Task 2: Ulam Sequence
3  #
5  use v5.12;
6  use warnings;
7  use PDL;
8  use PDL::NiceSlice;
9  say("Usage: ./ch-2.pl u v [N]\nto find the first N (default 10) terms".
10      " of the Ulam sequence u,v..."),exit unless @ARGV==2 || @ARGV==3;
11  say("The given numbers should not be equal"), exit unless \$ARGV!=\$ARGV;
12  my \$ulam=pdl[\$ARGV]; # initialize sequence
13  my \$candidates=pdl[\$ARGV]; # candidate list
14  my \$N=\$ARGV//10;
15  foreach(2..\$N){
16      my \$sl=\$candidates->qsort; # short list
17      # remove duplicates
18      \$sl=\$sl->where((\$sl!=\$sl->rotate(1))&(\$sl!=\$sl->rotate(-1))) if \$sl->nelem>1;
19      my \$next=\$sl->((0)); # Next Ulam number
20      \$candidates=\$candidates->append(\$ulam+\$next); # Update candidate list
21      \$candidates=\$candidates->where(\$candidates>\$next); # remove those too small
22      \$ulam=\$ulam->append([\$next]); # update list of ulam numbers
23  }
24  say "Input: u=\$ARGV, v=\$ARGV", defined \$ARGV?", N=\$N":"";
25  say "Output: \$ulam";
``````

Examples:

``````./ch-2.pl 1 2
./ch-2.pl 2 3
./ch-2.pl 2 5
``````

Results:

``````Input: u=1, v=2
Output: [1 2 3 4 6 8 11 13 16 18]
Input: u=2, v=3
Output: [2 3 5 7 8 9 13 14 18 19]
Input: u=2, v=5
Output: [2 5 7 9 11 12 13 15 19 23]
``````

Another example:

``````./ch-2.pl 2 3 20
``````

Results:

``````Input: u=2, v=3, N=20
Output: [2 3 5 7 8 9 13 14 18 19 24 25 29 30 35 36 40 41 46 51]
``````
Written on December 22, 2021