This is my response to the Perl Weekly Challenge #144.
Semiprime number <= 100.
Semiprime, please checkout the
wikipedia page.
10 is Semiprime as 10 = 2 x 5
15 is Semiprime as 15 = 3 x 5
#! /usr/bin/env raku
subset PosInt of Int where * > 0;
unit sub MAIN (PosInt $limit = 100); # [1]
my @primes = (1 .. $limit div 2).grep( *.is-prime); # [2]
my @result; # [3]
for @primes -> $a # [4]
{
for @primes -> $b # [5]
{
my $product = $a * $b; # [6]
@result.push: $product if $product <= $limit; # [7]
}
}
say @result.sort.squish.join(", "); # [8]
[1] The upper limit can be overridden.
[2] The highest possible number (divisor) than we can have as half the number, as 2
is a prime (i.e. x/2 == x/2 * 2). So we stop when we have reached the
half way point. Note the use of the integer divison operator div instead
of , so that we get an integer as result.
[3] The values will end up here.
[4] Iterate over the primes up to and including the half way point.
[5] Twice, as e.g. 10x10 is a legal solution.
[6] Get the product,
[7] and save it.
[8] Sort the result, get rid of duplicates (as e.g. both 2x3 and 3x2 give us 6), and print the result.
Running it:
$ ./semi-prime
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
$ ./semi-prime 200
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, 106, 111, 115, 118, \
119, 121, 122, 123, 129, 133, 134, 141, 142, 143, 145, 146, 155, 158, 159, \
161, 166, 169, 177, 178, 183, 185, 187, 194
#! /usr/bin/env perl
use strict;
use warnings;
use feature 'say';
use Math::Prime::Util 'is_prime';
use List::Util 'uniq';
my $limit = 100;
my @primes = grep { is_prime($_) } (1 .. $limit / 2);
my @result;
for my $a (@primes)
{
for my $b (@primes)
{
my $product = $a * $b;
push(@result, $product) if $product <= $limit;
}
}
say join(", ", uniq sort{ $a <=> $b } @result); # [1]
[1] Note that sort lives in a textual world, so we have to tell it that we
are giving it numeric values.
Running it gives the same result as the Raku version:
$ ./semi-prime-perl
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
$u and $v.
Ulam Sequence having at least 10
Ulam numbers where $u and $v are the
first 2 Ulam numbers.
Ulam Sequence, please checkout the
website.
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
Note that the program is somewhat more complicated than necessary, due to the verbose mode.
File: ulam-sequence
#! /usr/bin/env raku
subset PosInt of Int where * > 0;
unit sub MAIN (PosInt $u, # [1]
PosInt $v where $v > $u, # [1a]
:l(:$limit) = 10, # [2]
:v(:$verbose));
my $size = $limit.chars;
my $ulam := gather # [3]
{
my @ulam = ($u.Int, $v.Int); # [4]
my $index = 1; # [5]
say ": { indent(1, $size) }: @ulam[0]" if $verbose;
take @ulam[0]; # [6]
say ": { indent(2, $size) }: @ulam[1]" if $verbose;
take @ulam[1]; # [7]
loop # [8]
{
my @sum = @ulam.combinations(2)>>.sum.grep( * > @ulam[$index] ); # [9]
say ": { indent($index + 2, $size) }: { @sum.sort.join(", ") } \
(with duplicates)" if $verbose;
my @bag = @sum.Bag.grep( *.value == 1 ).map( *.key ).sort; # [10]
say ": { ' ' x $size } { @bag.join(", ") } (no duplicates)" if $verbose;
my $min = @bag.min; # [11]
@ulam[++$index] = $min; # [12]
take $min; # [13]
}
}
say $ulam[^$limit].join(", "); # [14]
sub indent ($number, $size)
{
return $number.fmt('%' ~ $size ~ 'd');
}
[1] The next number is larger than the previous one, so we have a sorted list without duplicates. It follows that the second number must be larger than the first one, so we should enforce that.
[2] You do not have to stop at 10.
[3] Setting up the sequence with gather/take
is ideal here.
See my Raku Gather,
I Take article or
docs.raku.org/syntax/gather take for more information about
gather/take.
[4] The two first values, coerced to integers just for fun (from the IntStr
type, as delivered by the command line).
[5] The index of the last value in the array so far.
[6] Return the first value (at index 0).
[7] Return the second value (at index 1).
[8] The rest of the values, done in a loop.
[9] Get all the combinations of two earlier elements (combinations(2)),
and the sum of each of them (>>.sum). Get rid of the sums that are not
larger than the currently largest value in the sequence (with grep).
[10] Coerce the list to a Bag, a hash like structur where
the values in the list turns ut as keys, and the values are the number of times they
occured. Then we use grep to get rid of elements that does not have a value
of 1 (i.e. get rid of values that occured multiple times). The sort is there
for the verbose output.
See
docs.raku.org/type/Bag
for more information about the Bag type.
[11] Get the smallest value. Note that we could have used @bag[0] here
instead, as the list is sorted.
[12] Add the new value to the list,
[13] and return it.
[14] Print the required number of values.
Running it:
$ ./ulam-sequence 1 2
1, 2, 3, 4, 6, 8, 11, 13, 16, 18
$ ./ulam-sequence 2 3
2, 3, 5, 7, 8, 9, 13, 14, 18, 19
$ ./ulam-sequence 2 5
2, 5, 7, 9, 11, 12, 13, 15, 19, 23
With verbose mode:
$ ./ulam-sequence -v 1 2
: 1: 1
: 2: 2
: 3: 3 (with duplicates)
: 3 (no duplicates)
: 4: 4, 5 (with duplicates)
: 4, 5 (no duplicates)
: 5: 5, 5, 6, 7 (with duplicates)
: 6, 7 (no duplicates)
: 6: 7, 7, 8, 9, 10 (with duplicates)
: 8, 9, 10 (no duplicates)
: 7: 9, 9, 10, 10, 11, 12, 14 (with duplicates)
: 11, 12, 14 (no duplicates)
: 8: 12, 12, 13, 14, 14, 15, 17, 19 (with duplicates)
: 13, 15, 17, 19 (no duplicates)
: 9: 14, 14, 14, 15, 15, 16, 17, 17, 19, 19, 21, 24 (with duplicates)
: 16, 21, 24 (no duplicates)
: 10: 17, 17, 17, 18, 19, 19, 19, 20, 21, 22, 24, 24, 27, 29 (with duplicates)
: 18, 20, 21, 22, 27, 29 (no duplicates)
1, 2, 3, 4, 6, 8, 11, 13, 16, 18
The fifth value is 6, as the lowest one (5) has been removed by the duplicate rule.
And that's it. (No Perl version of this one, as the duplicate rule ate the program.)