Merge pull request #5775 from dcw803/master

imported my solutions to this week's (rather tricky) challenge

3 files changed, 256 insertions, 27 deletions

diff --git a/challenge-155/duncan-c-white/README b/challenge-155/duncan-c-white/README
index a0d73dd4d3..5279605b40 100644
--- a/challenge-155/duncan-c-white/README
+++ b/challenge-155/duncan-c-white/README
@@ -1,43 +1,66 @@
-TASK #1 - Missing Permutation
+TASK #1 - Fortunate Numbers
 
-You are given possible permutations of the string 'PERL'.
+Write a script to produce first 8 Fortunate Numbers (unique and sorted).
 
-PELR, PREL, PERL, PRLE, PLER, PLRE, EPRL, EPLR, ERPL,
-ERLP, ELPR, ELRP, RPEL, RPLE, REPL, RELP, RLPE, RLEP,
-LPER, LPRE, LEPR, LRPE, LREP
+According to Wikipedia
 
-Write a script to find any permutations missing from the list.
+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.
 
-MY NOTES: should be easy, find all permutations and set subtract.
-Reuse my Perms module from challenge 149.
+Expected Output
 
+3, 5, 7, 13, 17, 19, 23, 37
 
-TASK #2 - Padovan Prime
+MY NOTES: ok.  Note that the Wikipedia article is not clear whether the
+Nth Fortunate number is the smallest integer m>1 s.t. pN# + m is prime,
+or whether that Nth value found is **A* Fortunate number, but the Fortunate
+numbers themselves are sorted and have duplicates removed - and the Nth
+Fortunate number is the Nth term of the sorted and deduped list.  I think
+we want the latter, because the unsorted Fortunate numbers corresponding to
+pn# for n=1..8 are 3, 5, 7, 13, 23, 17, 19, 23, i.e. they are not sorted and
+contain a duplicate of 23.
 
-A Padovan Prime is a Padovan Number that's also prime.
+Once you sort and dedup these, you get the desired sequence
+3, 5, 7, 13, 17, 19, 23, 37
 
-In number theory, the Padovan sequence is the sequence of integers P(n)
-defined by the initial values.
+HOWEVER, it's not obvious how many unsorted Fortunate numbers we have
+to calculate to know that we've found the first N sorted ones.  Let's keep
+going until we have found N distinct Fortunate numbers and then sort them.
+Is it possible for a later unsorted Fortunate number to be smaller
+than one of the ones we've # found so far?  Yes, blast it:
+The output of this program for N=1 is 3,5,7,13,17,19,23,37,61,67,71
+and for N=12 is 3,5,7,13,17,19,23,37,47,61,67,71
+(showing that the 12th distinct value found is 47, smaller than the 9th..11th
+distinct value found)
 
-P(0) = P(1) = P(2) = 1
+Also, this program won't work for N>12 because the primorial values get so
+enormous, like factorials.  I tried bigint but that slowed everything down
+so much that I couldn't find the answers in the time I had available.
 
-and then followed by
 
-P(n) = P(n-2) + P(n-3)
+TASK #2 - Pisano Period
 
-First few Padovan Numbers are as below:
+Write a script to find the period of the 3rd Pisano Period.
 
-1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, ...
+In number theory, the nth Pisano period, written as pi(n), is the period
+with which the sequence of Fibonacci numbers taken modulo n repeats.
 
-Write a script to compute first 10 distinct Padovan Primes.
-Expected Output
+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 pi(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, ...
 
-2, 3, 5, 7, 37, 151, 3329, 23833, 13091204281, 3093215881333057
+This sequence has period 8, so pi(3) = 8.
 
-MY NOTES: ok, Padovan numbers are rather like Fibonacci numbers,
-and easy enought to calculate.  Then we must check isprime().
-Should be pretty easy in principle, but in practice I note how big
-answers get very quickly, this code finds the first 8 Padovan
-Primes but would take ludicrously long amounts of time - and ludicrously
-large amounts of RAM to store all the prime numbers.  It's never
-finished for N==9 or 10.
+MY NOTES: ok.  Once we've found a sequence of length L that immediately
+repeats, i.e. that the first 2L entries comprise the same length L sequence
+repeated twice, How do we know that this sequence repeats forever?
diff --git a/challenge-155/duncan-c-white/perl/ch-1.pl b/challenge-155/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..756e0968cd
--- /dev/null
+++ b/challenge-155/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,128 @@
+#!/usr/bin/perl
+# 
+# TASK #1 - Fortunate Numbers
+# 
+# Write a script to produce first 8 Fortunate Numbers (unique and sorted).
+# 
+# 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
+# 
+# MY NOTES: ok.  Note that the Wikipedia article is not clear whether the
+# Nth Fortunate number is the smallest integer m>1 s.t. pN# + m is prime,
+# or whether that Nth value found is **A* Fortunate number, but the Fortunate
+# numbers themselves are sorted and have duplicates removed - and the Nth
+# Fortunate number is the Nth term of the sorted and deduped list.  I think
+# we want the latter, because the unsorted Fortunate numbers corresponding to
+# pn# for n=1..8 are 3, 5, 7, 13, 23, 17, 19, 23, i.e. they are not sorted and
+# contain a duplicate of 23.
+# 
+# Once you sort and dedup these, you get the desired sequence
+# 3, 5, 7, 13, 17, 19, 23, 37
+# 
+# HOWEVER, it's not obvious how many unsorted Fortunate numbers we have
+# to calculate to know that we've found the first N sorted ones.  Let's keep
+# going until we have found N distinct Fortunate numbers and then sort them.
+# Is it possible for a later unsorted Fortunate number to be smaller
+# than one of the ones we've # found so far?  Yes, blast it:
+# The output of this program for N=1 is 3,5,7,13,17,19,23,37,61,67,71
+# and for N=12 is 3,5,7,13,17,19,23,37,47,61,67,71
+# (showing that the 12th distinct value found is 47, smaller than the 9th..11th
+# distinct value found)
+#
+# Also, this program won't work for N>12 because the primorial values get so
+# enormous, like factorials.  I tried bigint but that slowed everything down
+# so much that I couldn't find the answers in the time I had available.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+#use bigint;
+use Function::Parameters;
+use Getopt::Long;
+#use Data::Dumper;
+
+my $debug=0;
+die "Usage: first-n-fortunates [--debug] [N default 8]\n"
+	unless GetOptions( "debug"=>\$debug ) && @ARGV<2;
+my $n = shift // 8;
+
+
+my %tested;		# values we've already tested for primeness
+my %isprime;		# values we've tested and found to be prime
+
+
+#
+# my $isprime = isprime( $x );
+#	Return 1 iff $x is prime.  Memoize the ones we know.
+#
+fun isprime( $x )
+{
+	return $isprime{$x} if $tested{$x};
+
+	$tested{$x}++;
+	$isprime{$x} = 0;
+	my $lim = int(sqrt($x));
+	for( my $i=2; $i<=$lim; $i++ )
+	{
+		return 0 if $x % $i == 0;
+	}
+	$isprime{$x} = 1;
+	return 1;
+}
+
+
+#
+# my $f = smallest_prime_above( $x );
+#	Find and return the first prime number above $x+1
+#	Couldn't use my MakePrimes module for this, as $x
+#	tends to be huge (as it's typically called with a primorial)
+#	and we test a small dense sequence of numbers
+#	from x+2..x+m for primeness.  there's no point computing
+#	all primes in the whole range 1...x+m
+#
+fun smallest_prime_above( $x )
+{
+	my $m;
+	for( $m = 2; ! isprime($x+$m); $m++ )
+	{
+	}
+	return $m;
+}
+
+
+#
+# my $nextprime = next_prime($prime);
+#	Given $prime, a prime number, find and return the next prime number.
+#
+fun next_prime( $p )
+{
+	for( $p++; !isprime($p); $p++ )
+	{
+	}
+	return $p;
+}
+
+
+my $primorial = 1;
+
+my %fortunate;
+my $nf=0;
+
+my $prime = 2;
+
+while( $nf < $n )
+{
+	$primorial *= $prime;	# primorial of the first few primes
+	my $f = smallest_prime_above( $primorial );
+	say "debug: prime $prime, primorial $primorial, fortunate no $f, nbefore $nf" if $debug;
+	$nf++ unless $fortunate{$f}++;
+	$prime = next_prime($prime);
+}
+
+say join( ',', sort { $a <=> $b } keys %fortunate );
diff --git a/challenge-155/duncan-c-white/perl/ch-2.pl b/challenge-155/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..933971a828
--- /dev/null
+++ b/challenge-155/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,78 @@
+#!/usr/bin/perl
+# 
+# TASK #2 - Pisano Period
+# 
+# Write a script to find the period of the 3rd Pisano Period.
+# 
+# In number theory, the nth Pisano period, written as pi(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 pi(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 pi(3) = 8.
+# 
+# MY NOTES: ok.  Once we've found a sequence of length L that immediately
+# repeats, i.e. that the first 2L entries comprise the same length L sequence
+# repeated twice, How do we know that this sequence repeats forever?
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Function::Parameters;
+#use Data::Dumper;
+
+my $debug=0;
+die "Usage: pisano-period [--debug] [N (default 3)]\n" unless
+	GetOptions( "debug" => \$debug ) && @ARGV<2;
+my $n = shift // 3;
+die "pp: n ($n) must be > 1\n" if $n<2;
+
+#
+# my $l = fib_modn_repeat( $n );
+#	Compute terms from the Fibonacci sequence mod $n,
+#	until the sequence repeats; return the length of
+#	the repeated sequence.
+#
+fun fib_modn_repeat( $n )
+{
+	my $a = 0;
+	my $b = 1;
+	say "debug: 0, mod$n 0" if $debug;
+	say "debug: 1, mod$n 1" if $debug;
+
+	my @x = ($a, $b);
+
+	for(;;)
+	{
+		( $a, $b ) =  ( $b, $a+$b );
+		say "debug: $b, mod$n ".($b % $n) if $debug;
+		push @x, $b%$n;
+		my $l = @x;
+		if( $l % 2 == 0 )
+		{
+			$l /= 2;
+			my $firsthalf = join(',', @x[0..$l-1]);
+			my $secondhalf = join(',', @x[$l..$#x]);
+			say "debug: first $firsthalf, second $secondhalf" if $debug;
+			next unless $firsthalf eq $secondhalf;
+			say "found repeat $firsthalf and $secondhalf, length $l" if $debug;
+			return $l;
+		}
+	}
+}
+
+my $l = fib_modn_repeat( $n );
+say $l;