From 5c9a6c1acf1ba33a1e7bdb5b24526234cd6c6874 Mon Sep 17 00:00:00 2001 From: dcw Date: Sun, 23 Jan 2022 22:03:38 +0000 Subject: imported my solutions to this week's puzzles.. included a bonus ch-2FAST.pl Cardano triple generator.. --- challenge-148/duncan-c-white/README | 79 +++++++++++++---------- challenge-148/duncan-c-white/perl/ch-1.pl | 74 +++++++++++++++++++++ challenge-148/duncan-c-white/perl/ch-2.pl | 92 +++++++++++++++++++++++++++ challenge-148/duncan-c-white/perl/ch-2FAST.pl | 84 ++++++++++++++++++++++++ 4 files changed, 295 insertions(+), 34 deletions(-) create mode 100755 challenge-148/duncan-c-white/perl/ch-1.pl create mode 100755 challenge-148/duncan-c-white/perl/ch-2.pl create mode 100755 challenge-148/duncan-c-white/perl/ch-2FAST.pl 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)\$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; + } +} -- cgit