Solution to challenge 168

1 files changed, 155 insertions, 0 deletions

diff --git a/challenge-168/jo-37/perl/ch-1.pl b/challenge-168/jo-37/perl/ch-1.pl
new file mode 100755
index 0000000000..8351305463
--- /dev/null
+++ b/challenge-168/jo-37/perl/ch-1.pl
@@ -0,0 +1,155 @@
+#!/usr/bin/perl -s
+
+use v5.16;
+use Test2::V0 '!array';
+use bigint;
+use List::Gen qw(:iterate :zip :source);
+use List::Util qw(product);
+use Math::Prime::Util qw(is_prime gcd);
+use experimental qw(signatures postderef);
+
+our ($tests, $examples, $iv, $f);
+$iv ||= '3, 0, 2';
+$f ||= '1, 1';
+
+run_tests() if $tests || $examples;	# does not return
+
+die <<EOS unless @ARGV;
+usage: $0 [-examples] [-tests] [-f=F1,...,Fl] [-iv=S1,...Sk] [N]
+
+-examples
+    run the examples from the challenge
+ 
+-tests
+    run some tests
+
+-f=F1,...,Fl
+    Coefficients for the linear recurrence relation.
+
+-iv=S1,...,Sk
+    Starting values for the generated sequence.
+
+N
+    Print the first N prime numbers from the generated sequence.
+
+    The sequence starts with the values S1,...,Sk and has the
+    linear recurrence relation:
+    S(n) = F(1) * S(n - k) + ... + F(k) * S(n - 1) for n > k.
+    Selecting unique primes from this sequence.
+
+Some known prime sequences:
+IV=0,1   F=1,1: Fibonacci
+IV=2,1   F=1,1: Lucas
+IV=1,1,1 F=1,1: Padovan
+IV=3,0,2 F=1,1: Perrin (default)
+IV=0,1   F=1,2: Pell
+IV=0,1   F=2,1: Jacobsthal
+
+CAUTION: Improper choice of IV and F will cause an endless loop!
+
+EOS
+
+
+### Input and Output
+
+main: {
+    # Explicit conversion to Math::BigInt is required for a set of
+    # variables so that all newly generated values inherit therefrom.
+    # Linear factors:
+    my $f = [map Math::BigInt->new($_), split /, */, $f];
+    # Initial values:
+    my $iv = [split /, */, $iv];
+
+    # "say(n)" prints the first n generated elements.
+    lin_recur_primes($iv, $f)->say(shift);
+}
+
+
+### Implementation
+
+# The solution to task 2 from challenge 154 with different starting
+# values could be reused to solve this task.  But this would by boring
+# and thus the task will be generalized here.
+#
+# The excellent Math::Prime::Util ennobles List::Gen by referencing it in
+# the "SEE ALSO" section.  Indeed, it looks very cool but comes with a
+# serious flaw: There has not been any development for over 10 years and
+# one of the tests is broken.  Needed "--force" to install. IMHO the
+# test result is ok, but the expected outcome is not.
+# "Failed test 'map & \(1 .. 3), 1 .. 2'"
+#
+# Building a generator for a sequence having the initial values
+# S(1),...,S(k) and a recurrence relation defined by a linear
+# combination of preceding elements:
+# S(n) = F(1) * S(n - k) + ... + F(k) * S(n - 1) for n > k.
+# and taking unique primes thereof.
+#
+sub lin_recur_primes ($s, $f) {
+
+    # Lazily extend the initial sequence using the recurrence relation.
+    ($s + iterate {($s = [$s->@[1 .. $#$s],
+                    tuples($f, $s)->map('product @$_')->sum])->[-1]
+        })->uniq->filter(sub {is_prime $_});
+}
+
+
+### Examples and tests
+
+sub run_tests {
+    SKIP: {
+        skip "examples" unless $examples;
+
+        # "take" returns the given number of elements.
+        is lin_recur_primes([3, 0, 2], [1, 1])->take(13),
+        [3, 2, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193,
+            792606555396977], 'task 1';
+    }
+
+    SKIP: {
+        skip "tests" unless $tests;
+
+        # "get" accesses elements by a zero-based index.  Thus "get(15)"
+        # is *three* behind the last from "take(13)".
+        is lin_recur_primes([3, 0, 2], [1, 1])->get(15),
+        '22584751787583336797527561822649328254745329',
+        'Perrin prime from http://oeis.org/A074788';
+
+        is lin_recur_primes([0, 1], [1, 1])->take(11),
+        [2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437,
+            2971215073],
+            'Fibonacci primes from Wiki';
+
+        is lin_recur_primes([1, 1, 1], [1, 1])->take(12),
+        [2, 3, 5, 7, 37, 151, 3329, 23833, 13091204281, 3093215881333057,
+            1363005552434666078217421284621279933627102780881053358473,
+            1558877695141608507751098941899265975115403618621811951868598809164180630185566719],
+            'Padovan primes from Wiki';
+        
+        is lin_recur_primes([2, 1], [1, 1])->take(15),
+        [2, 3, 7, 11, 29, 47, 199, 521, 2207, 3571, 9349, 3010349,
+            54018521, 370248451, 6643838879],
+            'Lucas primes from Wiki';
+
+        is lin_recur_primes([3, 1], [1, 1])->take(20),
+        [3, 5, 23, 37, 97, 157, 1741, 11933, 50549, 214129, 560597,
+            16276621, 180510493, 398386576261, 1042989597313,
+            41305516996050613, 174972977841043309, 13300248193487978669,
+            238663270054423392193, 624828552868675407173],
+            'A091157';
+
+        is lin_recur_primes([0, 1], [1, 2])->take(8),
+        [2, 5, 29, 5741, 33461, 44560482149, 1746860020068409,
+            68480406462161287469],
+            'Pell primes from Wiki';
+
+        is lin_recur_primes([0, 1], [2, 1])->take(15),
+        [3, 5, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883,
+            2932031007403, 768614336404564651, 201487636602438195784363,
+            845100400152152934331135470251,
+            56713727820156410577229101238628035243],
+            'Jacobsthal primes from Wiki';
+	}
+
+    done_testing;
+    exit;
+}