Merge pull request #6276 from jo-37/contrib

Solutions to challenge 169

2 files changed, 185 insertions, 0 deletions

diff --git a/challenge-169/jo-37/perl/ch-1.pl b/challenge-169/jo-37/perl/ch-1.pl
new file mode 100755
index 0000000000..1955c0e643
--- /dev/null
+++ b/challenge-169/jo-37/perl/ch-1.pl
@@ -0,0 +1,93 @@
+#!/usr/bin/perl -s
+
+use v5.16;
+use Test2::V0;
+use Math::Prime::Util qw(factor nth_semiprime logint);
+use List::MoreUtils 'distinct';
+use Math::Utils 'log10';
+use Coro::Generator;
+use experimental 'signatures';
+
+our ($tests, $examples, $base);
+$base ||= 10;
+
+run_tests() if $tests || $examples;	# does not return
+
+die <<EOS unless @ARGV;
+usage: $0 [-examples] [-tests] [-base=B] [N]
+
+-examples
+    run the examples from the challenge
+ 
+-tests
+    run some tests
+
+-base=B
+    Find brilliant numbers in base B.
+
+N
+    Print the first N brilliant numbers.
+
+EOS
+
+
+### Input and Output
+
+main: {
+    my $brilliant = brilliant($base);
+    say $brilliant->() for 1 .. shift;
+}
+
+
+### Implementation
+
+# Build a generator for brilliant numbers in base B by filtering
+# the sequence of all semiprimes.
+sub brilliant ($b) {
+    my $n;
+    generator {
+        while () {
+            # Emulate "next_semiprime()".
+            my $sp = nth_semiprime(++$n);
+            # Filter prime factors having the same length in base B.
+            yield $sp if 1 == distinct map logint($_, $b), factor $sp;
+        }
+    };
+}
+
+
+### Examples and tests
+
+sub run_tests {
+    SKIP: {
+        skip "examples" unless $examples;
+
+        my $brilliant = brilliant(10);
+        is [map $brilliant->(), 1 .. 20], [4, 6, 9, 10, 14, 15, 21, 25, 35,
+            49, 121, 143, 169, 187, 209, 221, 247, 253, 289, 299],
+            'task 1';
+    }
+
+    SKIP: {
+        skip "tests" unless $tests;
+
+        my $brilliant10 = brilliant(10);
+        is [map $brilliant10->(), 1 .. 55], [4, 6, 9, 10, 14, 15, 21, 25,
+            35, 49, 121, 143, 169, 187, 209, 221, 247, 253, 289, 299,
+            319, 323, 341, 361, 377, 391, 403, 407, 437, 451, 473, 481,
+            493, 517, 527, 529, 533, 551, 559, 583, 589, 611, 629, 649,
+            667, 671, 689, 697, 703, 713, 731, 737, 767, 779, 781],
+            'A078972';
+
+        my $brilliant2 = brilliant(2);
+        is [map $brilliant2->(), 1 .. 46], [4, 6, 9, 25, 35, 49, 121,
+            143, 169, 289, 323, 361, 391, 437, 493, 527, 529, 551, 589,
+            667, 713, 841, 899, 961, 1369, 1517, 1591, 1681, 1739, 1763,
+            1849, 1927, 1961, 2021, 2173, 2183, 2209, 2257, 2279, 2419,
+            2491, 2501, 2537, 2623, 2773, 2809],
+            'A085721';
+	}
+
+    done_testing;
+    exit;
+}
diff --git a/challenge-169/jo-37/perl/ch-2.pl b/challenge-169/jo-37/perl/ch-2.pl
new file mode 100755
index 0000000000..9440668f01
--- /dev/null
+++ b/challenge-169/jo-37/perl/ch-2.pl
@@ -0,0 +1,92 @@
+#!/usr/bin/perl -s
+
+use v5.16;
+use Test2::V0;
+use Math::Prime::Util qw(gcd factor_exp euler_phi);
+use List::Util 'all'; # only "all"
+use Coro::Generator;
+use experimental 'signatures';
+
+our ($tests, $examples, $strong);
+
+run_tests() if $tests || $examples;	# does not return
+
+die <<EOS unless @ARGV;
+usage: $0 [-examples] [-tests] [-strong] [N]
+
+-examples
+    run the examples from the challenge
+ 
+-tests
+    run some tests
+
+-strong
+    limit the result to "Strong Achilles numbers"
+
+N
+    Print the first N (Strong) Achilles numbers.
+
+EOS
+
+
+### Input and Output
+
+main: {
+    my $achilles = gen_achilles($strong);
+    say $achilles->() for 1 .. shift;
+}
+
+
+### Implementation
+
+# Brute force scan for (Strong) Achilles numbers.
+sub gen_achilles ($s) {
+    generator {
+        for (my $n = 1;; $n++) {
+            yield $n if is_achilles($n, $s);
+        }
+    }
+}
+
+# Check if N is a (Strong) Achilles number.
+sub is_achilles ($n, $s) {
+    # Get the prime exponents of N.
+    my @exp = map $_->[1], factor_exp $n;
+
+    all {$_ > 1} @exp and gcd(@exp) == 1 and
+        (!$s || is_achilles(euler_phi($n), 0));
+}
+
+
+### Examples and tests
+
+sub run_tests {
+    SKIP: {
+        skip "examples" unless $examples;
+
+        my $achilles = gen_achilles(0);
+        is [map $achilles->(), 1 .. 20], [72, 108,  200,  288,  392,
+            432,  500,  648,  675,  800,  864, 968, 972, 1125, 1152,
+            1323, 1352, 1372, 1568, 1800], 'task 2';
+    }
+
+    SKIP: {
+        skip "tests" unless $tests;
+
+        ok is_achilles(108, 0), 'example 1 from Wiki';
+        ok !is_achilles(360, 0), 'example 2 from Wiki';
+        ok !is_achilles(784, 0), 'example 3 from Wiki';
+        ok is_achilles(500, 1), 'example 4 from Wiki';
+
+        my $strong_achilles = gen_achilles(1);
+        is [map $strong_achilles->(), 1 .. 35], [500, 864, 1944, 2000,
+            2592, 3456, 5000, 10125, 10368, 12348, 12500, 16875, 19652,
+            19773, 30375, 31104, 32000, 33275, 37044, 40500, 49392,
+            50000, 52488, 55296, 61731, 64827, 67500, 69984, 78608,
+            80000, 81000, 83349, 84375, 93312, 108000],
+            'A194085 - Strong Achilles numbers';
+	}
+
+    done_testing;
+    exit;
+}