# Almost Prime and In Sequence: The Weekly Challenge #144

144 = 12 ^{2}, and it’s really *gross!*

### TASK #1 › Semiprime

Submitted by: Mohammad S Anwar

Write a script to generate allSemiprimenumbers`<= 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.

A number is **semiprime** if it’s the product of two prime numbers, besides 1 and itself, of course.

So, we need to know if a number is prime, and we need all factors. Instead of my previous *is_prime* function, which Colin calls out as suboptimal for this purpose, I grabbed Flavio Poletti’s

```
sub is_prime ($n) {
for (2 .. sqrt $n) { return unless $n % $_ }
return 1;
}
```

So, beyond that, you need?

- A number between 2 and the square root of
*n* - that is a factor of
*n* - and the corresponding factor to complete the math
- and both numbers are primes
- that have not been handled before.

Thankfully, this is easy to do with functional programming.

#### Show Me The Code

```
#!/usr/bin/env perl
use strict;
use warnings;
use feature qw{ say state postderef signatures };
no warnings qw{ experimental };
say join ', ', grep { is_semiprime($_) } 1 .. 100;
sub is_semiprime ($n ) {
my $done;
return 0 if is_prime($n);
my @factors =
grep { !$done->{ $_->[0] }{ $_->[1] }++ } # avoid replication
grep { is_prime( $_->[0] ) } # factor 1 is prime
grep { is_prime( $_->[1] ) } # factor 2 is prime
map { [ sort $_, $n / $_ ] } # both applicable factors
grep { 0 == $n % $_ } # is a factor
2 .. sqrt $n;
return scalar @factors == 1 ? 1 : 0;
}
sub is_prime ($n) {
for ( 2 .. sqrt $n ) { return unless $n % $_ }
return 1;
}
```

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

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

The key words are *“exactly one way”*. Starting `u=1`

and `v=2`

, you get 3 and 4, and can get to 5 with 1 + 4 and 2 + 3, so 5 is not a Ulam number.

So, the key is to store the number of ways you can get to a number, and then check to be sure that you only count 1.

We also go back to the **O(nlogn)** method of using two loops over the factor array, ensuring that there are no duplicated factors.

I use `delete`

a lot to clear the output hash of entries that match too many times.

I dunno, there’s probably more I could say to explain myself, but I’m failing to see what.

#### Show Me The Code

```
#!/usr/bin/env perl
use strict;
use warnings;
use feature qw{ say postderef signatures state };
no warnings qw{ experimental };
use JSON;
my $json = JSON->new;
my @examples;
push @examples, [ 1, 2 ];
push @examples, [ 2, 3 ];
push @examples, [ 2, 5 ];
push @examples, [ 5, 7 ];
for my $x (@examples) {
say '-' x 20;
my ( $u, $v ) = $x->@*;
my @sequence = ulam( $u, $v );
my $sequence = join ', ', sort { $a <=> $b } @sequence;
say <<"END";
Input: \$u = $u, \$v = $v
Output: $sequence
END
}
sub ulam ( $u = 1, $v = 2 ) {
my %output;
my @output;
# cover the base cases
$output{$u} = 1;
$output{$v} = 1;
my ($c) = sort { $b <=> $a } $u, $v;
while (1) {
$c++;
# ensure that non-Ulam numbers ("exactly one way")
# get weeded out
map { delete $output{$_} } grep { $output{$_} > 1 }
keys %output;
@output = sort { $a <=> $b } keys %output;
# testing early, because of the filter
return @output if scalar @output == 10;
for my $i ( 0 .. -2 + scalar @output ) {
my $x = $output[$i];
for my $j ( $i + 1 .. -1 + scalar @output ) {
my $y = $output[$j];
my $d = $x + $y;
if ( $c == $d ) {
$output{$c}++;
}
}
}
}
# "Remember the impossible scenario we never planned for?"
return [];
}
```

```
./ch-2.pl
--------------------
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
--------------------
Input: $u = 5, $v = 7
Output: 5, 7, 12, 17, 19, 22, 26, 27, 32, 33
```