Merge pull request #6296 from dcw803/master

imported solutions tp this week's tasks

5 files changed, 259 insertions, 30 deletions

diff --git a/challenge-168/duncan-c-white/perl/PrimeFactors.pm b/challenge-168/duncan-c-white/perl/PrimeFactors.pm
index 5ec2210764..95c5043d15 100644
--- a/challenge-168/duncan-c-white/perl/PrimeFactors.pm
+++ b/challenge-168/duncan-c-white/perl/PrimeFactors.pm
@@ -40,7 +40,7 @@ fun prime_factors( $n )
 {
 	die "prime_factors: n ($n) must be >1\n" if $n<=1;
 	my @result;
-	my $lim = int(sqrt($n));
+	my $lim = $n;
 	my $orign = $n;
 	foreach my $f (2..$lim)
 	{
@@ -50,8 +50,6 @@ fun prime_factors( $n )
 		{
 			say "pf($orign): n=$n, adding $f to result" if $debug;
 			push @result, $f;
-			my $other = $orign / $f;
-			push @result, $other if isprime($other) && $other != $f;
 			$n /= $f;
 			say "pf($orign): n /= $f (so n=$n now)" if $debug;
 		}
diff --git a/challenge-169/duncan-c-white/README b/challenge-169/duncan-c-white/README
index 17fc15785c..de1ee5c051 100644
--- a/challenge-169/duncan-c-white/README
+++ b/challenge-169/duncan-c-white/README
@@ -1,43 +1,56 @@
-TASK 1: Perrin Prime
+TASK 1: Brilliant Numbers
 
-The Perrin sequence is defined to start with [3, 0, 2]; after that, term
-N is the sum of terms N-2 and N-3. (So it continues 3, 2, 5, 5, 7, ....)
+Write a script to generate first 20 Brilliant Numbers.
 
-A Perrin prime is a number in the Perrin sequence which is also a prime number.
+    Brilliant numbers are numbers with two prime factors of the same length.
 
-Calculate the first 13 Perrin Primes.
+The number should have exactly two prime factors, i.e. it's the product
+of two primes of the same length.
 
-f(13) = [2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977]
+For example,
 
-MY NOTES: ok, sounds relatively easy, except that the 12th and 13th PP are
-enormous.  I normally reusing my old favourite MakePrimes.pm (Sieve of
-Eratosthenes based) but this time I think I'll have to do it the old
-fashioned "try all factors up to sqrt()" approach.
+24287 = 149 x 163
+24289 = 107 x 227
 
+Therefore 24287 and 24289 are 2-brilliant numbers.  These two brilliant
+numbers happen to be consecutive as there are no even brilliant numbers
+greater than 14.
 
-Task 2: Home Prime
+Output
 
-You are given an integer greater than 1.
+4, 6, 9, 10, 14, 15, 21, 25, 35, 49, 121, 143, 169, 187, 209, 221, 247, 253, 289, 299
 
-Write a script to find the home prime of the given number.
+MY NOTES: ok, sounds relatively easy, but I'm getting very bored of
+"tasks to do with Number Theory and (especially) Primes".
 
-In number theory, the home prime HP(n) of an integer n greater than
-1 is the prime number obtained by repeatedly factoring the increasing
-concatenation of prime factors including repetitions.
 
-Further information can be found on Wikipedia
+Task 2: Achilles Numbers
 
-https://en.wikipedia.org/wiki/Home_prime
+Write a script to generate first 20 Achilles Numbers. Please checkout
+wikipedia for more information.
 
-Example
+An Achilles number is a number that is powerful but imperfect (not a
+perfect power). Named after Achilles, a hero of the Trojan war, who was
+also powerful but imperfect.
 
-As given in the Wikipedia page:
+A positive integer n is a powerful number if, for every prime factor p
+of n, p^2 is also a divisor.
 
-HP(10) = 773, as 10 factors as 2x5 yielding HP10(1) = 25, 25 factors
-as 5x5 yielding HP10(2) = HP25(1) = 55, 55 = 5x11 implies HP10(3)
-= HP25(2) = HP55(1) = 511, and 511 = 7x73 gives HP10(4) = HP25(3) =
-HP55(2) = HP511(1) = 773, a prime number.
+A number is a perfect power if it has any integer roots (square root,
+cube root, etc.).
 
-MY NOTES: Ok, yet another prime variant.  I'll have a go, but I note that
-the numbers get enormous, to the point where it's not even known if HP(49)
-can be calculated.  Again can't use MakePrimes.pm..
+For example 36 factors to (2, 2, 3, 3) - every prime factor (2, 3) also
+has its square as a divisor (4, 9). But 36 has an integer square root,
+6, so the number is a perfect power.
+
+But 72 factors to (2, 2, 2, 3, 3); it similarly has 4 and 9 as divisors,
+but it has no integer roots. This is an Achilles number.
+
+Output
+
+ 72, 108,  200,  288,  392,  432,  500,  648,  675,  800,  864, 968, 972, 1125, 1152, 1323, 1352, 1372, 1568, 1800
+
+
+MY NOTES: Ok, yet another prime variant.  I can immediately see some mileage
+in pre-computing a lookup table of all perfect-powers up to N.  Perhaps N=1800
+as we know the answer:-)
diff --git a/challenge-169/duncan-c-white/perl/PrimeFactors.pm b/challenge-169/duncan-c-white/perl/PrimeFactors.pm
new file mode 100644
index 0000000000..129db6d3ae
--- /dev/null
+++ b/challenge-169/duncan-c-white/perl/PrimeFactors.pm
@@ -0,0 +1,63 @@
+#
+# Prime factors:
+# 	compute the prime factors of a number, using the old fashioned
+#	isprime "try all the factors"
+#
+
+use v5.10;	# to get "say"
+use strict;
+use warnings;
+use Function::Parameters;
+#use Data::Dumper;
+
+
+my $debug = 0;
+
+
+#
+# my $isprime = isprime( $n );
+#	Return 1 iff $n is a prime.  Return 0 otherwise.
+#
+sub isprime
+{
+	my( $n ) = @_;
+	my $lim = int(sqrt($n));
+	foreach my $div (2..$lim)
+	{
+		return 0 if $n % $div == 0;
+	}
+	return 1;
+}
+
+
+#
+# my @factors = prime_factors( $n );
+#	Break $n>1 apart into it's PRIME FACTORS (excluding 1).
+#	Return the list of prime factors, smallest first.
+#	eg. prime_factors( 228 ) = 2,2,3,19
+#
+fun prime_factors( $n )
+{
+	die "prime_factors: n ($n) must be >1\n" if $n<=1;
+	my @result;
+	my $lim = $n;
+	my $orign = $n;
+	foreach my $f (2..$lim)
+	{
+		next unless isprime($f);
+		say "pf($orign): considering prime factor $f" if $debug;
+		while( $n>1 && $n % $f == 0 )
+		{
+			say "pf($orign): n=$n, adding $f to result" if $debug;
+			push @result, $f;
+			$n /= $f;
+			say "pf($orign): n /= $f (so n=$n now)" if $debug;
+		}
+		last if $n==1;
+	}
+	say "pf($orign): prime factors are @result" if $debug;
+	return @result;
+}
+
+
+1;
diff --git a/challenge-169/duncan-c-white/perl/ch-1.pl b/challenge-169/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..228e29cb7e
--- /dev/null
+++ b/challenge-169/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,55 @@
+#!/usr/bin/perl
+# 
+# TASK 1: Brilliant Numbers
+# 
+# Write a script to generate first 20 Brilliant Numbers.
+# 
+#     Brilliant numbers are numbers with two prime factors of the same length.
+# 
+# The number should have exactly two prime factors, i.e. it's the product
+# of two primes of the same length.
+# 
+# For example,
+# 
+# 24287 = 149 x 163
+# 24289 = 107 x 227
+# 
+# Therefore 24287 and 24289 are 2-brilliant numbers.  These two brilliant
+# numbers happen to be consecutive as there are no even brilliant numbers
+# greater than 14.
+# 
+# Output
+# 
+# 4, 6, 9, 10, 14, 15, 21, 25, 35, 49, 121, 143, 169, 187, 209, 221, 247, 253, 289, 299
+# 
+# MY NOTES: ok, sounds relatively easy, but I'm getting very bored of
+# "tasks to do with Number Theory and (especially) Primes".  Reuse the
+# PrimeFactors module from last week, the one that doesn't pre-compute
+# primes up to X.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+#use Data::Dumper;
+
+use lib qw(.);
+use PrimeFactors;
+
+my $debug=0;
+die "Usage: brilliant-numebrs [--debug] [N default 20]\n"
+	unless GetOptions( "debug"=>\$debug ) && @ARGV<2;
+my $n = shift // 20;
+
+my @brillig;
+for( my $x = 4; @brillig < $n; $x++ )
+{
+	my @f = prime_factors( $x );
+	next unless @f == 2;
+	next unless length($f[0]) == length($f[1]);
+	push @brillig, $x;
+	say "found briliant number $x, factors $f[0] x $f[1]" if $debug;
+}
+
+say join(', ', @brillig );
diff --git a/challenge-169/duncan-c-white/perl/ch-2.pl b/challenge-169/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..d154f1112b
--- /dev/null
+++ b/challenge-169/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,100 @@
+#!/usr/bin/perl
+# 
+# Task 2: Achilles Numbers
+# 
+# Write a script to generate first 20 Achilles Numbers. Please checkout
+# wikipedia for more information.
+# 
+# An Achilles number is a number that is powerful but imperfect (not a
+# perfect power). Named after Achilles, a hero of the Trojan war, who was
+# also powerful but imperfect.
+# 
+# A positive integer n is a powerful number if, for every prime factor p
+# of n, p^2 is also a divisor.
+# 
+# A number is a perfect power if it has any integer roots (square root,
+# cube root, etc.).
+# 
+# For example 36 factors to (2, 2, 3, 3) - every prime factor (2, 3) also
+# has its square as a divisor (4, 9). But 36 has an integer square root,
+# 6, so the number is a perfect power.
+# 
+# But 72 factors to (2, 2, 2, 3, 3); it similarly has 4 and 9 as divisors,
+# but it has no integer roots. This is an Achilles number.
+# 
+# Output
+# 
+# 72, 108,  200,  288,  392,  432,  500,  648,  675,  800,  864, 968, 972,
+# 1125, 1152, 1323, 1352, 1372, 1568, 1800
+# 
+# MY NOTES: Ok, yet another prime variant.  I can immediately see some mileage
+# in pre-computing a lookup table of all perfect-powers up to N.  Perhaps N=1800
+# as we know the answer:-)
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Function::Parameters;
+use Data::Dumper;
+
+use lib qw(.);
+use PrimeFactors;
+
+my $debug=0;
+die "Usage: achilles-numbers [--debug] [N default 20]\n"
+	unless GetOptions( "debug"=>\$debug ) && @ARGV<2;
+my $n = shift // 20;
+
+#
+# my $ispowerful = ispowerful( $n );
+#	A positive integer n is a powerful number if, for every prime factor p
+#	of n, p^2 is also a divisor.
+#
+fun ispowerful( $n )
+{
+	my @f = prime_factors( $n );
+	foreach my $pf (@f)
+	{
+		return 0 unless $n % ($pf*$pf) == 0;
+	}
+	return 1;
+}
+
+
+#
+# my %perfpower = calc_perf_powers_up_to( $limit );
+#	A number is a perfect power if it has any integer roots (square root,
+#	cube root, etc.).  Precalc all perfectpowers up to $limit, as a set.
+#
+fun calc_perf_powers_up_to( $limit )
+{
+	my %perfpower;
+	$perfpower{1}++;
+	my $l2 = $limit*$limit;
+	for( my $i=2; $i<=$l2; $i++ )
+	{
+		for( my $pow = $i*$i; $pow <= $limit; $pow *= $i )
+		{
+			$perfpower{$pow}++;
+		}
+	}
+	return %perfpower;
+}
+
+
+my %perfpower = calc_perf_powers_up_to( 2000 );
+#my @pp = sort { $a <=> $b } keys(%perfpower);
+#die Dumper \@pp;
+
+my @ach;
+for( my $x=4; @ach<$n; $x++ )
+{
+	next unless ispowerful($x);
+	say "debug: $x is powerful" if $debug;
+	next if $perfpower{$x};
+	say "debug: $x is powerful and not perfect power" if $debug;
+	push @ach, $x;
+}
+say "ach: ". join(', ', @ach );