Merge pull request #5395 from choroba/ech144

Add solutions to 144: Semiprime & Ulam Sequence by E. Choroba

2 files changed, 118 insertions, 0 deletions

diff --git a/challenge-144/e-choroba/perl/ch-1.pl b/challenge-144/e-choroba/perl/ch-1.pl
new file mode 100755
index 0000000000..f09b0d7aa4
--- /dev/null
+++ b/challenge-144/e-choroba/perl/ch-1.pl
@@ -0,0 +1,60 @@
+#!/usr/bin/perl
+use warnings;
+use strict;
+
+{   package Semiprime;
+    use Moo;
+    has _primes => (is => 'rw', default => sub { [2, 3] });
+
+    sub is_semiprime {
+        my ($self, $n) = @_;
+        $self->_extend_primes while $n > $self->_primes->[-1];
+        for my $p (@{ $self->_primes }) {
+            return $self->_is_prime($n / $p) ? 1 : 0
+                if 0 == $n % $p;
+        }
+        return 0
+    }
+
+    sub _extend_primes {
+        my ($self) = @_;
+        my $candidate = $self->_primes->[-1];
+
+      CANDIDATE:
+        while ($candidate += 2) {
+            for my $p (@{ $self->_primes }) {
+                next CANDIDATE if 0 == $candidate % $p;
+            }
+            last CANDIDATE
+        }
+        push @{ $self->_primes }, $candidate;
+    }
+
+    sub _is_prime {
+        my ($self, $n) = @_;
+        return 0 if $n <= 1;
+
+        for my $p (@{ $self->_primes }) {
+            return $p == $n if 0 == $n % $p;
+        }
+        return
+    }
+}
+
+use Test2::V0;
+plan 6;
+
+my $s = 'Semiprime'->new;
+
+is $s->is_semiprime(10), 1, 'Example 1';
+is $s->is_semiprime(15), 1, 'Example 2';
+
+is $s->is_semiprime(1), 0, 'One';
+is $s->is_semiprime(23), 0, 'Prime';
+is $s->is_semiprime(30), 0, 'Three primes';
+
+my @under100 = grep $s->is_semiprime($_), 0 .. 100;
+is \@under100, [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],
+    'List <= 100'; # From Wikipedia.
diff --git a/challenge-144/e-choroba/perl/ch-2.pl b/challenge-144/e-choroba/perl/ch-2.pl
new file mode 100755
index 0000000000..cda3452b7f
--- /dev/null
+++ b/challenge-144/e-choroba/perl/ch-2.pl
@@ -0,0 +1,58 @@
+#!/usr/bin/perl
+use warnings;
+use strict;
+
+{   package Ulam::Sequence;
+    use Moo;
+
+    has u        => (is => 'ro',   requried => 1);
+    has v        => (is => 'ro',   required => 1);
+    has sequence => (is => 'lazy', builder  => 1);
+
+    sub extend {
+        my ($self, $l) = @_;
+        $l //= 1 + @{ $self->sequence };
+
+        my $n = $self->sequence->[-1];
+        while ($l != @{ $self->sequence }) {
+            while (++$n) {
+
+                my %seen;
+                @seen{ @{ $self->sequence } } = (1) x @{ $self->sequence };
+
+                for my $s (@{ $self->sequence }) {
+                    ++$seen{$n - $s} unless $n - $s == $s;
+                }
+                my $twice = grep 2 == $_, values %seen;
+                if ($twice && $twice < 3) {
+                    push @{ $self->sequence }, $n;
+                    last
+                }
+            }
+        }
+    }
+
+    sub _build_sequence {
+        my ($self) = @_;
+        return [ $self->u, $self->v ]
+    }
+}
+
+use Test2::V0;
+plan 4;
+
+my $us1 = 'Ulam::Sequence'->new(u => 1, v => 2);
+$us1->extend(10);
+is $us1->sequence, [1, 2, 3, 4, 6, 8, 11, 13, 16, 18], 'Example 1';
+
+my $us2 = 'Ulam::Sequence'->new(u => 2, v => 3);
+$us2->extend(10);
+is $us2->sequence, [2, 3, 5, 7, 8, 9, 13, 14, 18, 19], 'Example 2';
+
+my $us3 = 'Ulam::Sequence'->new(u => 2, v => 5);
+$us3->extend(10);
+is $us3->sequence, [2, 5, 7, 9, 11, 12, 13, 15, 19, 23], 'Example 3';
+
+my $us4 = 'Ulam::Sequence'->new(u => 1, v => 3);
+$us4->extend(10);
+is $us4->sequence, [1, 3, 4, 5, 6, 8, 10, 12, 17, 21], '(1,3)-U';