by Arne Sommer

# Primarily Ulam with Raku (and perl)

[162] Published 26. December 2021.

This is my response to the Perl Weekly Challenge #144.

## Challenge #144.1: Semiprime

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

File: semi-prime ```#! /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 ```

### A Perl Version

This is straight forward translation of the Raku version.

File: semi-prime-perl ```#! /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 ```

## Challenge #144.2: Ulam Sequence

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

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