- Added solutions by Colin Crain.

4 files changed, 352 insertions, 0 deletions

diff --git a/challenge-155/colin-crain/perl/ch-1.pl b/challenge-155/colin-crain/perl/ch-1.pl
new file mode 100755
index 0000000000..92f628e433
--- /dev/null
+++ b/challenge-155/colin-crain/perl/ch-1.pl
@@ -0,0 +1,146 @@
+#!/Users/colincrain/perl5/perlbrew/perls/perl-5.32.0/bin/perl

+#

+#       fortunate-son.pl

+#

+#       Fortunate Numbers

+#         Submitted by: Mohammad S Anwar

+#         Write a script to produce first 8 Fortunate Numbers (unique and

+#         sorted).

+# 

+#         According to Wikipedia

+# 

+#         A Fortunate number, named after Reo Fortune, is the smallest

+#         integer m > 1 such that, for a given positive integer n, pn# + m

+#         is a prime number, where the primorial pn# is the product of the

+#         first n prime numbers.

+# 

+#         Expected Output

+# 

+#           3, 5, 7, 13, 17, 19, 23, 37

+# 

+#         analysis

+# 

+#             We recently had a discussion on the squarefree numbers, and

+#             how they pop up unexpectedly all over topics in numbet

+#             theory. I will take the time to notice that the product of

+#             the first n prime numbers is the same as a prime degeneration

+#             with a maximal amount of discrete factors, with no exponents.

+#             So in other words we are talking about the largest squarefree

+#             number that we can create from n number of factors.

+# 

+#             Sow how about that?

+# 

+#             To rephrase the description then, the fortunate numbers

+#             correspond to a list of positive deltas required to make the

+#             largest squarefree number with that many factors prime.

+# 

+#             So we need to produce a list of primes, and from that list of

+#             cumulative products as we multiply in each successive term.

+#             Then from each of these products we need to first add 3 to

+#             make it odd and check for primality.

+# 

+#             Because the promorial will always be have 2 as a factor it

+#             will always be even. We would make this odd by adding 1, but

+#             1 is always excluded from the fortunate numbers so we

+#             immediately jump to 3.

+# 

+#             Likewise for testing a number for primality we can skip the

+#             calculation for 2, because we know we've made the candidate

+#             odd already. So we can start at 3 and increment upwards by 2s

+#             from there. We test repeatedly until we are prime.

+# 

+#             There's one last step though, which is to find 8 distinct

+#             terms and sort them. We'll need to gather terms until we have

+#             enough. As it's evident the list is not necessarily ordered,

+#             this raises the possibility that somewhere along the line the

+#             value 11 may arise, say at position 1142 or such. I don't see

+#             that happening but at the moment I don't see any reason to

+#             exclude the possiblity.

+# 

+#             What we will do though is assume it will not, and interpret

+#             the directive as "the first 8 distinct terms, sorted", which

+#             is slightly different and less absolute. We will collect

+#             terms until we find 8 values and then dump the buffer. 

+#

+#       © 2022 colin crain

+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

+

+

+

+use warnings;

+use strict;

+use utf8;

+use feature ":5.26";

+use feature qw(signatures);

+no warnings 'experimental::signatures';

+

+

+my $pgen = prime_generator();

+my @primes;

+my $primorial = 1;              ## multiplicative identity

+my %fortunate;

+

+while ( keys %fortunate < 8 ) {

+    push @primes, $pgen->();

+    $primorial *= $primes[-1];

+

+    ## loop through values for $f until a prime number is found

+    my $f = 1;

+    my $candidate;

+    FORTUNATE: while ( $f += 2 ) {

+        $candidate = $primorial + $f;

+        my $sqrt_candidate = int sqrt( $candidate );

+        for ( my $test = 3; $test <= $sqrt_candidate; $test += 2 ) {

+            next FORTUNATE if $candidate % $test == 0;

+        }

+        $fortunate{$f}++;

+        last FORTUNATE;

+    }

+}

+    

+say join ', ', sort {$a<=>$b} keys %fortunate;

+

+

+sub prime_generator ( ) {

+## returns an iterator closure that always delivers the next prime

+    state @primes;

+    

+    return sub {

+        if ( @primes < 2 ) {

+            push @primes, @primes == 0 ? 2 : 3;

+            return $primes[-1];

+        }

+    

+        my $candidate = $primes[-1] ;

+        CANDIDATE: while ( $candidate += 2 ) {

+            my $sqrt_candidate = sqrt( $candidate );

+            for my $test ( @primes ) {

+                next CANDIDATE if $candidate % $test == 0;

+                last if $test > $sqrt_candidate;

+            }

+            push @primes, $candidate;

+            return $candidate;

+        }

+    }

+}

+

+

+__END__

+

+

+2

+6

+30

+210

+2310

+30030

+510510

+9699690

+223092870

+6469693230

+200560490130

+7420738134810

+304250263527210

+13082761331670030

+614889782588491410

+3, 5, 7, 13, 23, 17, 19, 23, 37, 61, 67, 61, 71, 47, 107

diff --git a/challenge-155/colin-crain/perl/ch-2.pl b/challenge-155/colin-crain/perl/ch-2.pl
new file mode 100755
index 0000000000..641f3b1a49
--- /dev/null
+++ b/challenge-155/colin-crain/perl/ch-2.pl
@@ -0,0 +1,140 @@
+#!/Users/colincrain/perl5/perlbrew/perls/perl-5.32.0/bin/perl

+#

+#       pisa-time.pl

+#

+#       Pisano Period

+#         Submitted by: Mohammad S Anwar

+#         Write a script to find the period of the 3rd Pisano Period.

+# 

+#         In number theory, the nth Pisano period, written as π(n), is the

+#         period with which the sequence of Fibonacci numbers taken modulo

+#         n repeats.

+# 

+#         The Fibonacci numbers are the numbers in the integer sequence:

+# 

+#             0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 

+#                 233, 377, 610, 987, 1597, 2584, 4181, 6765, ...

+# 

+#         For any integer n, the sequence of Fibonacci numbers F(i) taken

+#         modulo n is periodic. The Pisano period, denoted π(n), is the

+#         value of the period of this sequence. For example, the sequence

+#         of Fibonacci numbers modulo 3 begins:

+# 

+#             0, 1, 1, 2, 0, 2, 2, 1,

+#             0, 1, 1, 2, 0, 2, 2, 1,

+#             0, 1, 1, 2, 0, 2, 2, 1, ...

+

+#         This sequence has period 8, so π(3) = 8.

+

+#       method:

+# 

+#         Ok, so we'll need a list of Fibonacci numbers.

+# 

+#         Check. No trouble there.

+# 

+#         Then, for a general solution, we need to make mappings of this

+#         list modulo various numbers, and make a new set of lists, one for

+#         each modulo.

+# 

+#         And then the hard part: spotting a cycle.

+

+#         You know whats really good for, you know, matching patterns? A

+#         pattern matcher, of course. And we have an excellent one of

+#         these, a world-class model, an inspiration for all the others, in the

+#         Perl regular expression engine.

+# 

+#         So what we do is we construct a string from the array of digits.

+#         Because the first fibonacci number is 0, the first character in

+#         this concatenated string will always be 0, and as such the first

+#         character of any repeated segment will likewise be 0. We can't

+#         just search from 0 to 0 though, as there may be other incidences

+#         of 0 digits within the sequence of remainders; we cannot make the

+#         presumption that there are not. What we need to do is match an

+#         incidence of a 0, followed by some minimal positive number of

+#         characters, with this match captured and followed immediately by

+#         the same matched sequence. 

+# 

+#         We then record the length of the captured sub-expression to an

+#         array of Pisano periods for output. 

+# 

+#         If the recorded period is 0, that's not a possible outcome as

+#         sequential differences in a modulo operation cannot be the same

+#         outside of trivial edge-cases. So what we're really recording is

+#         the failure of a match. This requires the list of Fibonacci

+#         numbers to be extended to provide enough values to match 2

+#         complete cycles. 

+# 

+#         As the Fibonacci list is extended, though, the values get large

+#         quickly. Fortunately the simplicity of the underlying math in

+#         constructing the sequence is not complex, and so adding the

+#         directive `use bigint` does not cripple the processing time.

+#         Things move along at a rapid pace.

+# 

+#         Except, though, when everything breaks after 10 values. The

+#         problem here is that our concatenation worked fine for

+#         single-digit remainders, but gets thrown off starting at 10, when

+#         that becomes a valid result. We can no longer simply count

+#         characters, as a single instance of 10 will count as 2 instead of

+#         1 and throw off the result. 

+# 

+#         I see two ways to resolve this. One way would be to extend the

+#         concatenation to make the number of characters allocated to each

+#         remained consistent, say by padding with some arbitrary null.

+#         This would deliver a character count in some multiple of the

+#         actual period, and we could divide to arrive at the final value.

+#         This is a perfectly good strategy, albeit a little complicated,

+#         and makes for very long strings. Peeking ahead we see one of the

+#         distant results is 120. Doubling the characters could be done

+#         with a map and allow us to look for Pisanos up to 99. The strings

+#         would however get quite huge. 

+# 

+#         On the other hand we could quickly map the values 0 through 35 to

+#         an alphanumeric character set. Each value gets one character

+#         again. We don't care what the numerical representation is, after

+#         all, only that it be unique so we can match a pattern. This would

+#         allow us access to he Pisanos up to 35 which seems like a

+#         reasonable ask. Actually there's no reason not to tack on a

+#         lowercase alphabet, extending our reach another 26 places, as

+#         again we don't care what characters we're using. 

+# 

+#         It appears that 256 Fibonaccis are enough to compute the Pisanos

+#         up to 61. I think that'll be plenty. 

+# 

+# 

+# 

+#       © 2022 colin crain

+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

+

+

+

+use warnings;

+use strict;

+use utf8;

+use feature ":5.26";

+use feature qw(signatures);

+no warnings 'experimental::signatures';

+use bigint;

+

+sub fibonaccis ( $count ) {

+## generates sequence of Fibonacci numbers up to and not greater than limit

+    state @fs = (0,1);

+    push  @fs, $fs[-1] + $fs[-2] while @fs <= $count;

+    return @fs;

+}

+

+

+my @fs = fibonaccis(256);

+my @pisas;

+

+for my $mod (2..61) {

+    my $modstr = join '', 

+                 map { (0..9, "A".."Z", "a".."z")[$_] } 

+                 map { $_ % $mod } 

+                 @fs;

+

+    $modstr =~ /(0.+?)\1/;

+    push @pisas, length $1;

+}

+

+say join ', ', @pisas;

+

diff --git a/challenge-155/colin-crain/raku/ch-1.raku b/challenge-155/colin-crain/raku/ch-1.raku
new file mode 100755
index 0000000000..5f24f7a8ea
--- /dev/null
+++ b/challenge-155/colin-crain/raku/ch-1.raku
@@ -0,0 +1,36 @@
+#!/usr/bin/env perl6
+#
+#
+#       155-1-fortunate-son.raku
+#
+#       method:
+
+#         In Raku the process becomes one complex chained function. In the
+#         first line w take the triangular reduction product of an infinite
+#         prime sequence that has been sliced to the first $quan number of
+#         elements, corresponding to the number of furtuante numbers we
+#         want to create. This creates a list of primorials to work with.
+# 
+#         In the second line we map individual elements from that list to
+#         the result of creating an infinite list of values starting at the
+#         initial element value plus 2 and then finding the first prime
+#         number in the sequence. The we subtract the initial value to
+#         arrive at the difference, which is the fortunate number.
+# 
+#         Then we output the final list of fortunate numbers we've created.
+# 
+#         I love this data flow. 
+#
+#       © 2022 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+
+
+unit sub MAIN ($quan = 20) ;
+
+    ([\*] ((1..*).grep: *.is-prime)[0..$quan])
+        .map({($_+2...Inf).first(*.is-prime) - $_})
+        .say ;
+        
+
+
diff --git a/challenge-155/colin-crain/raku/ch-2.raku b/challenge-155/colin-crain/raku/ch-2.raku
new file mode 100755
index 0000000000..14ce601e66
--- /dev/null
+++ b/challenge-155/colin-crain/raku/ch-2.raku
@@ -0,0 +1,30 @@
+#!/usr/bin/env perl6
+#
+#
+#       pisa-party.raku
+#
+#
+#
+#       © 2022 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+
+
+unit sub MAIN ($fibs = 256) ;
+
+my @fs = ( 0, 1, * + * ... * )[^$fibs];
+my @pisas = gather {
+    for 2..35 -> $mod {
+        $_ = @fs.map({$_ % $mod}) 
+                .map({ (|(0..9), |('A'..'Z'))[$_] }) 
+                .join ;
+        /(0.+?){}$0/ ;
+        take $0.chars;
+    }
+}
+
+
+for @pisas.kv -> $p, $q {
+    say ($p+2, $q).fmt("%3d", ' → ');
+}
+