Perl code for challenge 169

3 files changed, 128 insertions, 0 deletions

diff --git a/challenge-169/walt-mankowski/perl/ch-1.pl b/challenge-169/walt-mankowski/perl/ch-1.pl
new file mode 100644
index 0000000000..5e0e3c86c7
--- /dev/null
+++ b/challenge-169/walt-mankowski/perl/ch-1.pl
@@ -0,0 +1,26 @@
+use v5.36;
+use lib '.';
+use primes qw(primes_to prime_factors);
+
+# Task 1: Brilliant Numbers
+#
+# Write a script to generate first 20 Brilliant Numbers.
+#
+#     Brilliant numbers are numbers with two prime factors of the same length.
+#
+# The number should have exactly two prime factors, i.e. it’s the
+# product of two primes of the same length.
+
+$, = ' ';
+my $MAX = 300;
+my $primes = primes_to($MAX);
+
+my @brilliant;
+for (my $n = 4; @brilliant < 20 && $n <= $MAX; $n++) {
+    my @factors = prime_factors($n, $primes);
+    if (@factors == 2 && length($factors[0]) == length($factors[1])) {
+        push @brilliant, $n;
+    }
+}
+
+say @brilliant;
diff --git a/challenge-169/walt-mankowski/perl/ch-2.pl b/challenge-169/walt-mankowski/perl/ch-2.pl
new file mode 100644
index 0000000000..7dd829bcd0
--- /dev/null
+++ b/challenge-169/walt-mankowski/perl/ch-2.pl
@@ -0,0 +1,60 @@
+use v5.36;
+use lib '.';
+use primes qw(primes_to prime_factors);
+
+# Task 2: Achilles Numbers
+# Submitted by: Mohammad S Anwar
+#
+# Write a script to generate first 20 Achilles Numbers. Please
+# checkout wikipedia for more information.
+#
+#     An Achilles number is a number that is powerful but imperfect
+#     (not a perfect power). Named after Achilles, a hero of the
+#     Trojan war, who was also powerful but imperfect.
+#
+#     A positive integer n is a powerful number if, for every prime
+#     factor p of n, p^2 is also a divisor.
+#
+#     A number is a perfect power if it has any integer roots (square
+#     root, cube root, etc.).
+
+$, = ' ';
+my $MAX = 1800;
+my $primes = primes_to($MAX);
+my $perfect_power = powers_upto($MAX);
+
+my @achilles;
+for (my $n = 2; @achilles < 20 && $n <= $MAX; $n++) {
+    my @factors = prime_factors($n, $primes);
+    if (is_powerful(@factors) && !$perfect_power->{$n}) {
+        push @achilles, $n;
+    }
+}
+
+say @achilles;
+
+# a number is powerful if there are at least 2 of each prime factor
+sub is_powerful(@factors) {
+    my %cnt;
+    for my $i (@factors) {
+        $cnt{$i}++;
+    }
+    for my $v (values %cnt) {
+        return 0 if $v == 1;
+    }
+    return 1;
+}
+
+# there aren't that many perfect powers less than 1800, so since we know
+# the answer we'll cheat a little and generate them all ahead of time
+sub powers_upto($n) {
+    my %powers;
+    for my $i (2..sqrt($n)) {
+        my $val = $i * $i;
+        while ($val <= $n) {
+            $powers{$val} = 1;
+            $val *= $i;
+        }
+    }
+    return \%powers;
+}
diff --git a/challenge-169/walt-mankowski/perl/primes.pm b/challenge-169/walt-mankowski/perl/primes.pm
new file mode 100644
index 0000000000..878c523b0b
--- /dev/null
+++ b/challenge-169/walt-mankowski/perl/primes.pm
@@ -0,0 +1,42 @@
+package primes;
+use Exporter 'import';
+our @EXPORT_OK = qw(primes_to prime_factors);
+
+use v5.36;
+use builtin 'indexed';
+no warnings 'experimental::for_list';
+no warnings 'experimental::builtin';
+
+# find the primes up to $n using the sieve of Eratosthenes and return
+# them as an arrayref
+sub primes_to($n) {
+    my @is_prime = map {1} 0..int($n);
+    $is_prime[0] = $is_prime[1] = 0;
+    for my $i (2..int(sqrt($n))) {
+        if ($is_prime[$i]) {
+            for (my $j = $i+$i; $j <= $n; $j += $i) {
+                $is_prime[$j] = 0;
+            }
+        }
+    }
+
+    my @primes;
+    for my ($i, $v) (indexed @is_prime) {
+        push @primes, $i if $v;
+    }
+    return \@primes;
+}
+
+# return the prime factors of $n as a sorted list
+sub prime_factors($n, $primes) {
+    my @factors;
+    for my $p ($primes->@*) {
+        return @factors if $p > $n;
+        while ($n % $p == 0) {
+            push @factors, $p;
+            $n /= $p;
+        }
+    }
+}
+
+1;