Perl Weekly Challenge 144.
My solutions (task 1 and task 2 ) to the The Weekly Challenge - 144.
Task 1: Semiprime
Submitted by: Mohammad S Anwar
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
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
2 # Task 1: Semiprime
3 #
4 # See https://wlmb.github.io/2021/12/22/PWC144/#task-1-semiprime
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
Task 2: Ulam Sequence
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.
For more information about Ulam Sequence, please checkout the
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 #
4 # See https://wlmb.github.io/2021/12/22/PWC144/#task-2-ulam-sequence
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[0]!=$ARGV[1];
12 my $ulam=pdl[$ARGV[0]]; # initialize sequence
13 my $candidates=pdl[$ARGV[1]]; # candidate list
14 my $N=$ARGV[2]//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[0], v=$ARGV[1]", defined $ARGV[2]?", 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