Merge pull request #5556 from dcw803/master

imported my solutions to this week's puzzles..

4 files changed, 295 insertions, 34 deletions

diff --git a/challenge-148/duncan-c-white/README b/challenge-148/duncan-c-white/README
index 91d23b989b..586c2b6679 100644
--- a/challenge-148/duncan-c-white/README
+++ b/challenge-148/duncan-c-white/README
@@ -1,47 +1,58 @@
-TASK #1 - Truncatable Prime
+TASK #1 - Eban Numbers
 
-Write a script to generate first 20 left-truncatable prime numbers in base 10.
+Write a script to generate all Eban Numbers <= 100.
 
-In number theory, a left-truncatable prime is a prime number which, in a
-given base, contains no 0, and if the leading left digit is successively
-removed, then all resulting numbers are primes.
+An Eban number is a number that has no letter 'e' in it when the
+number is spelled in English (American or British).
 
 Example
 
-9137 is one such left-truncatable prime since 9137, 137, 37 and 7 are
-all prime numbers.
+2, 4, 6, 30, 32 are the first 5 Eban numbers.
 
-MY NOTES: Very easy, especially (tada) if you happen to have a prime
-generating module that you've already used several times in these
-challenges..
+MY NOTES: Very easy, no doubt there are CPAN modules to "speak" numbers
+in English, but let's do it from first principles..
 
 
-TASK #2 - Pentagon Numbers
+TASK #2 - Cardano Triplets
 
-Write a script to find the first pair of Pentagon Numbers whose sum and difference are also a Pentagon Number.
+Write a script to generate first 5 Cardano Triplets.
 
-    Pentagon numbers can be defined as P(n) = n(3n - 1)/2.
+A triplet of positive integers (a,b,c) is called a Cardano Triplet if
+it satisfies the below condition.
+
+  cuberoot(a+b.sqrt(c)) + cuberoot(a-b.sqrt(c)) = 1
 
 Example
 
-	The first 10 Pentagon Numbers are:
-	1, 5, 12, 22, 35, 51, 70, 92, 117 and 145.
-
-	P(4) + P(7) = 22 + 70 = 92 = P(8)
-	but
-	P(4) - P(7) = |22 - 70| = 48 is not a Pentagon Number.
-
-MY NOTES: Ok, reasonably straight forward, calc first N Pentagon numbers,
-form a sethash of them to allow lookups, then iterate over all pairs of
-Pentagon numbers rejecting all pairs where the diff or sum isn't a Pentagon
-number. The diff of any two of the first N Pentagon numbers is obviously
-smaller, so may be looked up directly in the sethash.  The only tricky bit
-concerns the SUM of any two of them, because that sum may be greater than
-the biggest Pentagon number we know as yet, hence not in the sethash because
-we haven't calculated such Pentagon numbers yet - not because it's not a
-Pentagon number.  I can nearly see the structure of an adaptive solution,
-that generates Pentagon numbers incrementally, but it's a bit tricky.
-So instead let's Keep It Simple - just generate the first N Pentagon numbers
-and see if we can find any matching pair of those (where the sum is in the
-first N Pentagon numbers).  If not, run the program again with a bigger value
-of N.  Experimentation reveals that N=2400 finds the solution..
+(2,1,5) is the first Cardano Triplet.
+
+MY NOTES: Ok, two mildly tricky things:
+1. real arithmetic means "=" is imprecise, we can't even use rationals as
+   sqrt() and cuberoot() are involved, so we'll need our old abs(diff)<epsilon
+   trick..   and
+2. the question says (2,1,5) is the "first" Cardano triplet - in what order?
+
+The answer to the latter question sets the basic structure of the program.
+Perhaps we should "order by minimum sum of triplet numbers"?  ch-2.pl does
+that, effectively generating all (a,b,c) where a+b+c=SUM for gradually
+increasing values of SUM, testing whether each (a,b,c) triple is a Cardano
+triple.  It works perfectly well - but quite slowly.
+
+I then built a SECOND VERSION (ch-2FAST.pl) which uses a much more efficient
+parameterised version of Cardano Triplets that I found on the Internet.
+See the top comments in that for a longer explanation, but it turns out
+that we can (nearly) directly pick out Cardano triples by calculating:
+
+a=3k+2 and x=(k+1)**2(8k+5) for each k
+
+(where x represents bsquared*c)
+
+then we need to break x down into b and c - noting that several (b,c) pairs
+may result from a single value of x.
+
+How much faster is this than ch-2.pl?  For n=40, ch-2 takes 30 seconds where
+ch-2FAST takes just under 2 seconds!  And this gets better as n increases,
+ch-2FAST takes 6.9s for n=100, but I gave up on running ch-2 40 after a couple
+of minutes when it had only found about 60 triples.
+
+Can anyone find a faster version?
diff --git a/challenge-148/duncan-c-white/perl/ch-1.pl b/challenge-148/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..19abd9117c
--- /dev/null
+++ b/challenge-148/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,74 @@
+#!/usr/bin/perl
+# 
+# TASK #1 - Eban Numbers
+# 
+# Write a script to generate all Eban Numbers <= 100.
+# 
+# An Eban number is a number that has no letter 'e' in it when the
+# number is spelled in English (American or British).
+# 
+# Example
+# 
+# 2, 4, 6, 30, 32 are the first 5 Eban numbers.
+# 
+# MY NOTES: Very easy, no doubt there are CPAN modules to "speak" numbers
+# in English, but let's do it from first principles..
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Data::Dumper;
+
+my $debug=0;
+die "Usage: twodigit-eban-numbers [--debug]\n"
+	unless GetOptions( "debug"=>\$debug ) && @ARGV==0;
+
+my @digits = qw(zero one two three four five six seven eight nine);
+my @tens = qw(ten twenty thirty forty fifty sixty seventy eighty ninety);
+
+#
+# my $english = convert_to_english( $n );
+#	Convert the two digit $n (n<100) to English form, eg 33->"thirty-three"
+#
+sub convert_to_english ($)
+{
+	my( $n ) = @_;
+
+	die "convert_to_english: $n out of range 0..99\n" if $n<0 || $n>99;
+
+	my $d = $n%10;
+	my $dig = $digits[$d];
+	$n = int($n/10);
+	return $dig if $n==0;
+
+	my $tens = $tens[$n-1];
+	return $tens if $d==0;
+	return $tens.'-'.$dig;
+}
+
+
+#
+# my $iseben = is_eben_2digit($n);
+#	Return 1 iff the two digit $n (n<100) is an Eben
+#	number, 0 otherwise.
+#
+sub is_eben_2digit ($)
+{
+	my( $n ) = @_;
+
+	my $english = convert_to_english( $n );
+
+	# Eben iff english form contains an 'e'..
+	# "? 1 : 0" is just in case we want to print the return
+	# value during debugging (otherwise false would be undef)
+	my $eb = $english !~ /e/ ? 1 : 0;
+
+	say "$n is eben (cos english is $english)" if $debug && $eb;
+
+	return $eb;
+}
+
+
+say join( ',', grep { is_eben_2digit($_) } 1..99 );
diff --git a/challenge-148/duncan-c-white/perl/ch-2.pl b/challenge-148/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..aca65324f3
--- /dev/null
+++ b/challenge-148/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,92 @@
+#!/usr/bin/perl
+# 
+# TASK #2 - Cardano Triplets
+# 
+# Write a script to generate first 5 Cardano Triplets.
+# 
+# A triplet of positive integers (a,b,c) is called a Cardano Triplet if
+# it satisfies the below condition.
+# 
+#   cuberoot(a+b.sqrt(c)) + cuberoot(a-b.sqrt(c)) = 1
+# 
+# Example
+# 
+# (2,1,5) is the first Cardano Triplet.
+# 
+# MY NOTES: Ok, two mildly tricky things:
+# 1. real arithmetic means "=" is imprecise, we can't even use rationals as
+#    sqrt() and cuberoot() are involved, and
+# 2. (2,1,5) is the "first" Cardano triplet - in what order?
+# 
+# The answer to the latter question will set the basic structure
+# of the program.  Perhaps we should "order by minimum sum of triplet numbers"?
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Data::Dumper;
+
+
+my $debug=0;
+my $epsilon = 1e-7;
+
+#
+# my $root = cuberoot($x);
+#	Return the cuberoot of $x; make sure it works even if $x<0
+#
+sub cuberoot ($)
+{
+	my( $x ) = @_;
+	my $r = abs($x)**(1/3);
+	$r = -$r if $x<0;
+	return $r;
+}
+
+
+#
+# my $isc = is_cardano($a,$b,$c);
+#	Return 1 iff $a,$b,$c is a Cardano triplet; 0 otherwise.
+#	Recall that a Cardano triplet has:
+#	cuberoot(a+b.sqrt(c)) + cuberoot(a-b.sqrt(c)) = 1
+#
+sub is_cardano ($$$)
+{
+	my( $a, $b, $c ) = @_;
+	my $x = $b * sqrt($c);
+	my $q = cuberoot($a+$x) + cuberoot($a-$x);
+	#say "iscard($a,$b,$c): x=$x, q=$q";
+
+	return abs( $q-1 ) <= $epsilon ? 1 : 0;
+}
+
+
+#say is_cardano(2,1,5);
+#exit 0;
+
+die "Usage: first-N-cardano-triplets [--debug] [N default 5]\n" unless
+	GetOptions( "debug"=>\$debug ) && @ARGV<2;
+
+my $n = shift // 5;
+
+my $nfound = 0;
+
+for( my $sum=3; $nfound < $n; $sum++ )
+{
+	# find all Cardano triplets whose sum is $sum
+	say "find all Cardano triplets with sum $sum" if $debug;
+	for( my $a=1; $a<$sum-1; $a++ )
+	{
+		for( my $b=1; $a+$b<$sum; $b++ )
+		{
+			my $c = $sum-$a-$b;
+			die "bad structure, a=$a, b=$b, c=$c\n"
+				if $c<1;
+			#say "$a,$b,$c";
+			next unless is_cardano($a,$b,$c);
+			$nfound++;
+			say "Found $a,$b,$c";
+		}
+	}
+}
diff --git a/challenge-148/duncan-c-white/perl/ch-2FAST.pl b/challenge-148/duncan-c-white/perl/ch-2FAST.pl
new file mode 100755
index 0000000000..99608924f7
--- /dev/null
+++ b/challenge-148/duncan-c-white/perl/ch-2FAST.pl
@@ -0,0 +1,84 @@
+#!/usr/bin/perl
+# 
+# TASK #2 - Cardano Triplets
+# 
+# Write a script to generate first N Cardano Triplets.
+# 
+# MY NOTES: This version (ch-2FAST.pl) uses a much more efficient parameterised
+# version of Cardano Triplets that I found on the Internet but frankly don't
+# understand how it was derived. See
+#
+# https://math.stackexchange.com/questions/1885095/parametrization-of-cardano-triplet
+#
+# Specifically the author of that question claimed that the Cardano triplets
+# formula may be expanded to:
+#       8a**3+15a**2+6a - 27x=1
+# where a=3k+2 and
+#       x=(k+1)**2(8k+5)
+#	(x represents b*b*c)
+# 
+# If this is correct, we can just loop directly through k calculating each
+# (a, x), and selecting those for which the 8a**3... formula succeeds.
+# Then we need to break x down into b and c - noting that several (b,c)
+# pairs may result from a single value of x, so this doesn't generate
+# Cardano triplets in anything like the same order as ch-2.pl does.
+#
+# Also, we may need bignum as the numbers get pretty big..
+#
+# In fact, I now realise that each (a,x) pair for every k automatically
+# satisfies the 8a**3... formula so we don't even need to check it:
+# this is now only checked if you specific --paranoid when running this.
+#
+# How much faster is this than ch-2.pl?  For n=40, ch-2.pl takes 30 seconds
+# where this (ch-2FAST.pl) takes just under 2 seconds!  And this gets better
+# as n increases: this version takes 6.9s for n=100, but I gave up on
+# running ch-2.pl 40 after a couple of minutes when it had only found about
+# 60 triples..  of course this version is faster, we are directly finding
+# the (a,x) partial solutions and only have to break x down to one or more
+# (b,c) pairs, whereas ch-2.pl is basically a brute force search.
+# 
+
+use strict;
+use warnings;
+use bignum;
+use feature 'say';
+use Getopt::Long;
+use Data::Dumper;
+
+
+my $debug=0;
+my $paranoid=0;
+
+die "Usage: first-N-cardano-triplets [--debug] [--paranoid] [N default 5]\n"
+	unless GetOptions( "debug"=>\$debug, "paranoid"=>\$paranoid )
+	&&     @ARGV<2;
+
+my $n = shift // 5;
+
+my $nfound = 0;
+
+for( my $k=0; $nfound < $n; $k++ )
+{
+	my $a = 3*$k + 2;
+	my $x = ($k+1)**2 * (8*$k+5);
+	say "k=$k, a=$a, x=$x" if $debug;
+	if( $paranoid )
+	{
+		my $lhs = 8*$a**3+15*$a**2+6*$a - 27*$x;
+		#say "k=$k, a=$a, lhs=$lhs" if $debug;
+		die "Parameterisation error for k=$k, a=$a, x=$x, lhs=$lhs ".
+		    "(lhs is not 1)\n" unless $lhs==1;
+	}
+
+	# ok, now we need to find possible (b,c) values such that
+	# b*b*c == x; note that there can be several for a single x!
+	say "k=$k matches.. breakdown $x" if $debug;
+	my $lim = int(sqrt($x));
+	for( my $b=1; $b<=$lim; $b++ )
+	{
+		my $c = int( $x / ($b*$b) );
+		next unless $b*$b*$c == $x;
+		$nfound++;
+		say "Found $a,$b,$c" if $nfound<=$n;
+	}
+}