Merge pull request #6281 from waltman/branch-for-challenge-169

Branch for challenge 169

5 files changed, 218 insertions, 18 deletions

diff --git a/challenge-169/walt-mankowski/README.md b/challenge-169/walt-mankowski/README.md
index 0ed2bb3e10..13731abfec 100644
--- a/challenge-169/walt-mankowski/README.md
+++ b/challenge-169/walt-mankowski/README.md
@@ -1,35 +1,107 @@
 Solutions by Walt Mankowski.
 
-# Task #1: Eban Numbers
+## primes.pm
+Both of this week's challenge involve prime numbers. This module contains 2 utility functions, `primes_to` and `prime_factors`. `primes_to($n)` computes the primes up to `$n` using the [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes). `prime_factors($n, $primes)` finds the prime factors of `$n` using the primes returned by `primes_to()`.
 
-For this task we need to write a script to generate all **Eban Numbers** <= 100. An Eban number is a number that has no letter 'e' in it when the number is spelled in English (American or British).
+The Sieve algorithm uses an array of flags, and after it's finished any entry with a true value is a prime. To convert that to a list I used the new [`indexed` keyword](https://perldoc.perl.org/builtin#indexed) in Perl 5.36:
+```perl
+my @primes;
+for my ($i, $v) (indexed @is_prime) {
+    push @primes, $i if $v;
+}
+```
+This little `for` loop is using 2 different experimental features. Also `indexed` is Perl's new `builtin` namespace. In order to get this to run without warnings I needed to add some boilerplate code to the top of the module:
+```perl
+use v5.36;
+use builtin 'indexed';
+no warnings 'experimental::for_list';
+no warnings 'experimental::builtin';
+```
+
+To find the prime factorization of `$n` we loop through the primes in order. If a prime `$p` divides `$n` evenly, we repeatedly add `$p` to the list of prime factors and divide `$n` by `$p` until it doesn't.
+```perl
+# 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;
+        }
+    }
+}
+```
+
+# Task #1: Brilliant Numbers
 
-I used the CPAN module `Lingua::EN::Numbers`, which
-> provides a function "num2en", which converts a number (such as 123) into English text ("one hundred and twenty-three").
+For this task we need to find the first 20 **Brilliant Numbers**. A Brilliant number is a number with exactly 2 prime factors of the same length.
 
-Using `num2en` we can generate the Eban numbers with a single line of code:
+This is easy to compute with the functions in `primes.pm`. Since we know from the problem description that the 20th Brilliant number is 299, I start by finding all the primes less than 300. I also set Perl's special variable `$,` to `' '` so when print the values at the end they'll be spaced out nicely.
 ```perl
-my @eban = grep { num2en($_) !~ tr/e// } 1..100;
+$, = ' ';
+my $MAX = 300;
+my $primes = primes_to($MAX);
 ```
 
-# Task 2: Cardano Triplets
+Then the main loop just follows the problem description. I start the loop at 4 since that's the first composite number.
+```perl
+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;
+    }
+}
 
-For this task we need to generate the first 5 **Cardano Triplets**. The formula for Cardano Triplets involves square and cube roots. Github's Markdown engine doesn't support inline math, so I'll refer the reader to a [Project Euler](https://projecteuler.net/problem=251) problem involving them.
+say @brilliant;
+```
 
-There's no obvious method to sort Cardano Triplets, so instead of generating the first 5, I decided to generate all the solutions where a, b, and c are all less than or equal to 100. I didn't use anything fancy to generate them, just 3 nested `for` loops.
+# Task 2: Achilles Numbers
 
-The only real difficulty here is that the second cube root term is often negative. This is the case for the example of (2,1,5) given in the problem description. Like all nonzero real numbers, 2 - sqrt(5) has exactly one real cube root, but since it's negative Perl's `**` operator returns `NaN`. To get around this I take the cube root of the absolute value, then make it negative:
+For this task we need to find the first 20 **Achilles Numbers**. An [Achillies number](https://en.wikipedia.org/wiki/Achilles_number) is a number that is **powerful** but not a perfect power. A number is powerful if every prime factor appears at least squared in the factorization.
 
+To test if a number is powerful, I just count how many times each prime factor appears:
 ```perl
-my $tmp = $a - $b * sqrt($c);
-my $t2 = ($tmp >= 0) ? $tmp ** $THIRD : -abs($tmp) ** $THIRD;
+# 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;
+}
 ```
 
-Also, since we're dealing with floating point numbers and potential round off errors, we'll accept it as a match if the sum is within epsilon of 1:
+Testing if a number is a perfect power is trickier. Fortunately we know from the problem that we don't need any perfect powers greater than 1800, and powers get big fast so there aren't that many of them. This function generates all of them:
 ```perl
-my $EPS = 1e-6;
-...
-if (abs($t1 + $t2 - 1) < $EPS) {
-    say "($a, $b, $c) ", $a + $b + $c ;
+# 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;
 }
 ```
+
+As with Challenge 1 this week, once we have the functions set up, the actual loop to compute the values is simple.
+```perl
+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;
+```
diff --git a/challenge-169/walt-mankowski/perl/.perl-version b/challenge-169/walt-mankowski/perl/.perl-version
index 04a883217e..795df42654 100644
--- a/challenge-169/walt-mankowski/perl/.perl-version
+++ b/challenge-169/walt-mankowski/perl/.perl-version
@@ -1 +1 @@
-5.34.0
+5.36.0
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;