imported my solutions to this week's tasks; first nice and easy, second easy in principle but only finds first 8 Padovan Primes in reasonable time..

5 files changed, 318 insertions, 29 deletions

diff --git a/challenge-154/duncan-c-white/README b/challenge-154/duncan-c-white/README
index 918a4a5540..a0d73dd4d3 100644
--- a/challenge-154/duncan-c-white/README
+++ b/challenge-154/duncan-c-white/README
@@ -1,45 +1,43 @@
-TASK #1 - Left Factorials
+TASK #1 - Missing Permutation
 
-Write a script to compute Left Factorials of 1 to 10. Please refer OEIS
-A003422 for more information.
+You are given possible permutations of the string 'PERL'.
 
-(My summary: left factorial N = sum k! for k in (0..N-1), remembering that
- 0! = 1! = 1.  So lf(N+1) = lf(N) + N!)
+PELR, PREL, PERL, PRLE, PLER, PLRE, EPRL, EPLR, ERPL,
+ERLP, ELPR, ELRP, RPEL, RPLE, REPL, RELP, RLPE, RLEP,
+LPER, LPRE, LEPR, LRPE, LREP
 
-Expected Output:
+Write a script to find any permutations missing from the list.
 
-1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114
+MY NOTES: should be easy, find all permutations and set subtract.
+Reuse my Perms module from challenge 149.
 
-MY NOTES: easy, 1 pass, calc N! on the fly (by multiplying (N-1)! by N)
-and add (N-1)! to lf(N-1) to give lf(N).
 
+TASK #2 - Padovan Prime
 
-TASK #2 - Factorions
+A Padovan Prime is a Padovan Number that's also prime.
 
-You are given an integer, $n.
+In number theory, the Padovan sequence is the sequence of integers P(n)
+defined by the initial values.
 
-Write a script to figure out if the given integer is factorion.
+P(0) = P(1) = P(2) = 1
 
-A factorion is a natural number that equals the sum of the factorials of its digits.
+and then followed by
 
-Example 1:
+P(n) = P(n-2) + P(n-3)
 
-  Input: $n = 145
-  Output: 1
+First few Padovan Numbers are as below:
 
-    Since 1! + 4! + 5! => 1 + 24 + 120 = 145
+1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, ...
 
-Example 2:
+Write a script to compute first 10 distinct Padovan Primes.
+Expected Output
 
-  Input: $n = 123
-  Output: 0
+2, 3, 5, 7, 37, 151, 3329, 23833, 13091204281, 3093215881333057
 
-    Since 1! + 2! + 3! => 1 + 2 + 6 <> 123
-
-MY NOTES: cool, precompute 0..9! in a 10 element array, split number into
-digits, sum their factorials and check if the result if the number you
-first thought of.  Let's add a tabulating mode (invoked if --tab given) that
-shows, which numbers (1..$n) are factorian.  Running this as:
-	./ch-2.pl -t 1000000
-reveals that the only base 10 factorians under 1000000 are:
-        1, 2, 145, 40585
+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.
diff --git a/challenge-154/duncan-c-white/perl/MakePrimes.pm b/challenge-154/duncan-c-white/perl/MakePrimes.pm
new file mode 100644
index 0000000000..6b5cd8e9fe
--- /dev/null
+++ b/challenge-154/duncan-c-white/perl/MakePrimes.pm
@@ -0,0 +1,97 @@
+#
+#	mkprimes module (converted from mkprimes.c)
+#
+
+use strict;
+use warnings;
+use Function::Parameters;
+
+
+my $debug = 0;
+my @foundprimes;	# remember all primes we've found..
+
+
+fun prime_debug( $d )
+{
+	$debug = $d;
+}
+
+
+#
+# my @primes = primes_upto( $n );
+#	Find all primes up to N; return a list of all such primes
+#	(note that 1 is not usually considered a prime)
+#
+fun primes_upto( $n )
+{
+	my @isprime;
+
+	for( my $i=1; $i<=$n; $i++ )
+	{
+		$isprime[$i] = 1;		# initially
+	}
+
+	# now sieve the non-primes out..
+	my $upper = int(sqrt($n));
+	printf( "debug: n=%d, upper=%d\n", $n, $upper ) if $debug;
+	for( my $i=2; $i<=$upper; $i++ )
+	{
+		if( $isprime[$i] )
+		{
+			#printf( "debug: crossing out multiples of %d\n", $i );
+			for( my $j=$i*$i; $j<=$n; $j+=$i )
+			{
+				$isprime[$j] = 0;
+			}
+		}
+	}
+
+	# after sieving, extract the primes
+	my @primes = grep { $isprime[$_] } 2..$n;
+
+	# remember them
+	@foundprimes = @primes;
+
+	return @primes;
+}
+
+
+#
+# my @moreprimes = more_primes( $n, $m );
+#	Need more primes!  Have @foundprimes up to $n, but need
+#	to sieve primes from $n+1..$m, so re-sieve, return
+#	a list of all new primes (in the range $n+1..$m) that we find.
+#
+fun more_primes( $n, $m )
+{
+	my %isprime;
+
+	print "finding more primes from ", $n+1, "..$m\n" if $debug;
+
+	for( my $i=$n+1; $i<=$m; $i++ )
+	{
+		$isprime{$i} = 1;	# pre-sieving
+	}
+
+	# now sieve the non-primes out..
+	foreach my $prime (@foundprimes)
+	{
+		# find first multiple of $prime > $n
+		my $mult = $prime * (int($n/$prime)+1);
+
+		#print "debug: xo multiples of $prime from $mult to $m\n";
+
+		for( my $j=$mult; $j<=$m; $j+=$prime )
+		{
+			delete $isprime{$j};
+		}
+	}
+
+	# after sieving, extract the primes
+	my @primes = grep { $isprime{$_} } $n+1..$m;
+	push @foundprimes, @primes;
+	return @primes;
+}
+
+
+1;
diff --git a/challenge-154/duncan-c-white/perl/Perms.pm b/challenge-154/duncan-c-white/perl/Perms.pm
new file mode 100644
index 0000000000..ce65b89760
--- /dev/null
+++ b/challenge-154/duncan-c-white/perl/Perms.pm
@@ -0,0 +1,46 @@
+package Perms;
+
+# 
+# Generate permutations, one at a time, using a
+# standard lexicographic permutation algorithm.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+#use Data::Dumper;
+
+#
+# my $next = next_perm( $val );
+#	Find and return the next permutation in lexicographic order
+#	of $val.  Return undef is $val is the last permutation (in order).
+#	Algorithm treats $val as an array of digits a[n]:
+#	1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists,
+#	   the permutation is the last permutation.
+#       2. Find the largest index l greater than k such that a[k] < a[l].
+#       3. Swap the value of a[k] with that of a[l].
+#       4. Reverse the sequence from a[k + 1] up to and including the final element a[n].
+#
+sub next_perm ($)
+{
+	my( $val )= @_;
+	my @a = split( //, $val );
+	my( $k, $l );
+	my $n = @a-1;
+	for( $k=$n-1; $k>=0 && ord($a[$k])>=ord($a[$k+1]); $k-- )
+	{
+	}
+	return undef if $k<0;
+	for( $l=$n; $l>$k && ord($a[$k])>=ord($a[$l]); $l-- )
+	{
+	}
+	( $a[$k], $a[$l] ) = ( $a[$l], $a[$k] );
+
+	# reverse a[k+1]..a[n]
+	@a[$k+1..$n] = reverse @a[$k+1..$n];
+
+	return join( '', @a );
+}
+
+
+1;
diff --git a/challenge-154/duncan-c-white/perl/ch-1.pl b/challenge-154/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..820ce8e088
--- /dev/null
+++ b/challenge-154/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,44 @@
+#!/usr/bin/perl
+# 
+# TASK #1 - Missing Permutation
+# 
+# You are given possible permutations of the string 'PERL'.
+# 
+# PELR, PREL, PERL, PRLE, PLER, PLRE, EPRL, EPLR, ERPL,
+# ERLP, ELPR, ELRP, RPEL, RPLE, REPL, RELP, RLPE, RLEP,
+# LPER, LPRE, LEPR, LRPE, LREP
+# 
+# Write a script to find any permutations missing from the list.
+# 
+# MY NOTES: should be easy, find all permutations and set subtract.
+# Reuse my Perms module from challenge 149.  As a bonus, added the
+# --baseword WORD flag to set the base word (default PERL).
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+#use Data::Dumper;
+
+use lib qw(.);
+use Perms;
+
+my $debug=0;
+my $baseword = "PERL";
+die "Usage: missing-perl-perms [--debug] [--baseword W] list(permutations_of_perl)\n"
+	unless GetOptions( "debug"=>\$debug, "baseword=s" => \$baseword ) && @ARGV>1;
+my %given = map { uc($_) => 1 } @ARGV;
+
+# first perm has to be in lexicographic order
+my $perm = join( '', sort split( //, $baseword ) );
+say "first perm is $perm" if $debug;
+
+my @missing;
+do {
+	say "perm=$perm" if $debug;
+	push @missing, $perm unless $given{$perm};
+	$perm = Perms::next_perm($perm);
+} while defined $perm;
+
+say "missing: ". join(',', @missing);
diff --git a/challenge-154/duncan-c-white/perl/ch-2.pl b/challenge-154/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..f54d905569
--- /dev/null
+++ b/challenge-154/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,104 @@
+#!/usr/bin/perl
+# 
+# TASK #2 - Padovan Prime
+# 
+# A Padovan Prime is a Padovan Number that's also prime.
+# 
+# In number theory, the Padovan sequence is the sequence of integers P(n)
+# defined by the initial values.
+# 
+# P(0) = P(1) = P(2) = 1
+# 
+# and then followed by
+# 
+# P(n) = P(n-2) + P(n-3)
+# 
+# First few Padovan Numbers are as below:
+# 
+# 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, ...
+# 
+# Write a script to compute first 10 distinct Padovan Primes.
+#
+# Expected Output
+# 
+# 2, 3, 5, 7, 37, 151, 3329, 23833, 13091204281, 3093215881333057
+# 
+# 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
+# the 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.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Function::Parameters;
+#use Data::Dumper;
+
+use lib qw(.);
+use MakePrimes;
+
+my $debug=0;
+die "Usage: first-N-padovan-primes [--debug] [N (default 10)]\n" unless
+	GetOptions( "debug" => \$debug ) && @ARGV<2;
+my $n = shift // 10;
+
+prime_debug( $debug );
+
+# Padovan sequence:
+
+my @pad = (1,1,1);
+
+#
+# my $p = nextpad();
+#	Extend @pad by one, pad(n) = pad(n-2) + pad(n-3)
+#	return the newest (last) element.
+#
+fun nextpad(  )
+{
+	my $n = @pad;
+	$pad[$n] = $pad[$n-2] + $pad[$n-3];
+	return $pad[$n];
+}
+
+
+#
+# my @pp = find_first_n_pad_primes( $n );
+#	Find and return the first $n Padovan primes,
+#	calculating primes along the way.
+#
+fun find_first_n_pad_primes( $n )
+{
+	my $band = 1000000;
+	my @result;
+
+	my $upto = $band;
+	my %isprime;
+	$isprime{$_}++ for primes_upto( $upto );
+	my %seen;
+	for(;;)
+	{
+		my $x = nextpad();
+		if( $x > $upto )		# need more primes
+		{
+			my $newupto = $upto + $band;
+			$isprime{$_}++ for more_primes( $upto, $newupto );
+			$upto = $newupto;
+		}
+		next unless $isprime{$x};	# find Prime Pad nos
+		next if $seen{$x}++;		# remove duplicates
+		push @result, $x;
+		my $nfound = @result;
+		say "debug: found ${nfound}th pp: $x"; # if $debug;
+
+		return @result if @result==$n;
+	}
+}
+
+my @pp = find_first_n_pad_primes( $n );
+
+say join( ', ', @pp );