Merry Christmas and Happy New Year! May 2022 bring you less COVID and more Perl projects!

The examples used here are from The Weekly Challenge problem statement and demonstrate the working solution.

Part 1

Write a script to generate all Semiprime numbers <= 100.

Solution

use strict;
use warnings;
use boolean; 
use LWP::UserAgent;
use constant N => 100; 
use constant PRIME_URL => "http://primes.utm.edu/lists/small/100000.txt";

sub get_primes{
    my @primes;
    my $ua = new LWP::UserAgent(
        ssl_opts => {verify_hostname => 0}
    );
    my $response = $ua->get(PRIME_URL);
    my @lines = split(/\n/,$response->decoded_content);
    foreach my $line (@lines){
        my @p = split(/\s+/, $line);
        unless(@p < 10){
            push @primes, @p[1..(@p - 1)];
        }
    }
    return @primes;
}

sub factor{
    my($n) = @_;
    my @factors = ();
    for  my $j (2 .. sqrt($n)){
        if($j**2 == $n){  
            push @factors, [$j, $j] if $j**2 == $n;
            next; 
        }
        push @factors, [$j, $n / $j] if $n % $j == 0;
    }
    return @factors;
}

sub semiprime{
    my($n, $primes) = @_;
    my @factors = factor($n);
    return false if @factors != 1;  
    my @prime_factors = grep {$factors[0]->[0] == $_ || $factors[0]->[1] == $_} @{$primes};     
    return true if @prime_factors == 2 || $prime_factors[0]**2 == $n; 
    return false; 
}

sub semiprime_n{
    my @primes = get_primes; 
    for my $n (1 .. N){
        print "$n " if semiprime($n, \@primes);   
    } 
    print "\n"; 
}

MAIN:{
    semiprime_n;
}

Sample Run

$ perl ch-1.pl
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

Notes

I am sticking to the convention that I started a while back to not re-compute prime numbers myself, but instead just grab them from one of several convenient online sources. The URL in the code above requires only a small amount of effort to scrape and parse. I hope nobody minds the little bit of extra traffic to their site!

Please do check out their main page listed below. It's a fun resource with interesting facts and news on prime numbers and related research.

Once the list of the first 100k primes is obtained (that's more than enough for any of these challenges) we proceed to factor and test candidate numbers. Provided the number has only two factors (which may be equal) and both of them are prime then it passes the semiprime test.

Part 2

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.

Solution

use strict;
use warnings;
use constant ULAM_LIMIT => 10;   

sub ulam{
    my($u, $v) = @_;    
    my %pairs; 
    my @ulam = ($u, $v); 
    my $w = $u + $v;  
    push @ulam, $w;  
    $pairs{"$u,$v"} = $w; 
    $pairs{"$u,$w"} = $u + $w; 
    $pairs{"$v,$w"} = $v + $w; 
    do{
        my @sums = sort {$a <=> $b} grep{my $sum = $_; my @values = grep{$sum == $_} values %pairs; $sum if @values == 1 && $sum > $ulam[@ulam - 1]} values %pairs; 
        my $u = $sums[0]; 
        push @ulam, $u;
        for my $pair (keys %pairs){
            my($s, $t) = split(/,/, $pair);  
            $pairs{"$s,$u"} = $s + $u;
            $pairs{"$t,$u"} = $t + $u;
        }   
    }while(@ulam < ULAM_LIMIT);
    return @ulam;  
}

MAIN:{
    my @ulam;
    @ulam = ulam(1, 2);   
    {
        print shift @ulam;
        print ", ";
        redo if @ulam > 1;
    } 
    print shift @ulam;
    print "\n";

    @ulam = ulam(2, 3);   
    {
        print shift @ulam;
        print ", ";
        redo if @ulam > 1;
    } 
    print shift @ulam;
    print "\n";

    @ulam = ulam(2, 5);   
    {
        print shift @ulam;
        print ", ";
        redo if @ulam > 1;
    } 
    print shift @ulam;
    print "\n";
}

Sample Run

$ perl perl/ch-2.pl
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

Notes

The code here is a pretty direct translation of the definition: the next member of the sequence must be a sum of two previous members which is greater than the previous member and only be obtainable one way. Here that is done with a grep filter, with the sequence itself being stored in an array, but for convenience the sums of all unique previous pairs are kept in a hash.

References

Challenge 144

Semiprime Number

Prime Pages

Ulam Sequence