Merge pull request #5619 from dcw803/master

imported my solutions to this week's tasks; two nice tasks

3 files changed, 163 insertions, 20 deletions

diff --git a/challenge-150/duncan-c-white/README b/challenge-150/duncan-c-white/README
index 2a58cddb5b..4c7c2d807d 100644
--- a/challenge-150/duncan-c-white/README
+++ b/challenge-150/duncan-c-white/README
@@ -1,31 +1,48 @@
-TASK #1 - Fibonacci Digit Sum
+TASK #1 - Fibonacci Words
 
-Given an input $N, generate the first $N numbers for which the sum of
-their digits is a Fibonacci number.
+You are given two strings having same number of digits, $a and $b.
 
-Example
+Write a script to generate Fibonacci Words by concatenation of the
+previous two strings. Finally print 51st digit of the first term having
+at least 51 digits.
+
+Example:
 
-f(20)=[0, 1, 2, 3, 5, 8, 10, 11, 12, 14, 17, 20, 21, 23, 26, 30, 32, 35, 41, 44]
+    Input: $a = '1234' $b = '5678'
+    Output: 7
 
-MY NOTES: Pretty easy.  Only question: how many Fibonacci numbers do we
-need to compute?  Let's extend the sequence whenever we need..
+    Fibonacci Words:
 
+    '1234'
+    '5678'
+    '12345678'
+    '567812345678'
+    '12345678567812345678'
+    '56781234567812345678567812345678'
+    '1234567856781234567856781234567812345678567812345678'
 
-TASK #2 - Largest Square
+    The 51st digit in the first term having at least 51 digits
+    '1234567856781234567856781234567812345678567812345678' is 7.
 
-Given a number base, derive the largest perfect square with no repeated
-digits and return it as a string. (For base>10, use 'A'..'Z'.)
+MY NOTES: Pretty easy.  Fibonacci words == append two previous strings.
+Use -d (debug mode) to see all the above explanatory info.
 
-Example:
 
-    f(2)="1"
-    f(4)="3201"
-    f(10)="9814072356"
-    f(12)="B8750A649321"
+TASK #2 - Square-free Integer
+
+Write a script to generate all square-free integers <= 500.
+
+In mathematics, a square-free integer (or squarefree integer) is an
+integer which is divisible by no perfect square other than 1. That is,
+its prime factorization has exactly one factor for each prime that
+appears in it. For example, 10 = 2 * 5 is square-free, but 18 = 2 *
+3 * 3 is not, because 18 is divisible by 9 = 3**2.
+
+Example
 
+The smallest positive square-free integers are
+    1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, ...
 
-MY NOTES: Obvious technique is to compute all permutations of 0..B-1 (B the
-base), and check whether each is a perfect square, and track the largest
-perfect square we find.  I hate permutations, but I'm sure I have written
-a permutation generator in previous Perl Challenges...  Oh yes, I've stolen
-code from Challenge 134 (task 1) and made it into a simple Perms module here.
+MY NOTES: also pretty easy.  The second definition above suggests using prime
+numbers, which is easy enough, especially as I have a prime generating module,
+but actually it's simpler to do it without primes as the first definition hints.
diff --git a/challenge-150/duncan-c-white/perl/ch-1.pl b/challenge-150/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..b7572810b1
--- /dev/null
+++ b/challenge-150/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,67 @@
+#!/usr/bin/perl
+# 
+# TASK #1 - Fibonacci Words
+# 
+# You are given two strings having same number of digits, $a and $b.
+# 
+# Write a script to generate Fibonacci Words by concatenation of the
+# previous two strings. Finally print 51st digit of the first term having
+# at least 51 digits.
+# 
+# Example:
+# 
+#     Input: $a = '1234' $b = '5678'
+#     Output: 7
+# 
+#     Fibonacci Words:
+# 
+#     '1234'
+#     '5678'
+#     '12345678'
+#     '567812345678'
+#     '12345678567812345678'
+#     '56781234567812345678567812345678'
+#     '1234567856781234567856781234567812345678567812345678'
+# 
+#     The 51st digit in the first term having at least 51 digits
+#     '1234567856781234567856781234567812345678567812345678' is 7.
+# 
+# MY NOTES: Pretty easy.  Fibonacci words == append two previous strings.
+#	Use -d (debug mode) to see all the above explanatory info.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Data::Dumper;
+use List::Util qw(sum);
+
+my $debug=0;
+die "Usage: fib-words [--debug] A B\n"
+	unless GetOptions( "debug"=>\$debug ) && @ARGV==2;
+my( $a, $b ) = @ARGV;
+
+my @out = "Fibonacci words\n\'$a'\n'$b'";
+
+for(;;)
+{
+	# form next Fibonacci word
+	my $next = $a.$b;
+last if length($b) > 50;
+	push @out, "'$next'";
+	$a = $b;
+	$b = $next;
+}
+
+my $digit51 = substr($b,50,1);
+push @out, "\nThe 51st digit in the first term having at least 51 digits";
+push @out, "'$b', is $digit51";
+
+say "Output: $digit51";
+
+if( $debug )
+{
+	say "";
+	say for @out;
+}
diff --git a/challenge-150/duncan-c-white/perl/ch-2.pl b/challenge-150/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..340c3f49ae
--- /dev/null
+++ b/challenge-150/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,59 @@
+#!/usr/bin/perl
+# 
+# TASK #2 - Square-free Integer
+# 
+# Write a script to generate all square-free integers <= 500.
+# 
+# In mathematics, a square-free integer (or squarefree integer) is an
+# integer which is divisible by no perfect square other than 1. That is,
+# its prime factorization has exactly one factor for each prime that
+# appears in it. For example, 10 = 2 * 5 is square-free, but 18 = 2 *
+# 3 * 3 is not, because 18 is divisible by 9 = 3**2.
+# 
+# Example
+# 
+# The smallest positive square-free integers are
+#     1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, ...
+# 
+# MY NOTES: also pretty easy.  The second definition above suggests using prime
+# numbers, which is easy enough, especially as I have a prime generating module,
+# but actually it's simpler to do it without primes as the first definition hints.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Function::Parameters;
+use Data::Dumper;
+
+my $debug=0;
+
+die "Usage: square-free-integers [--debug] [N default 500]\n" unless
+	GetOptions( "debug"=>\$debug ) && @ARGV<2;
+
+my $limit = shift // 500;
+
+
+#
+# my $squarefree = squarefree( $n );
+#	Given a number $n, return 1 iff $n is a square free number,
+#	ie. one divisible by no perfect square other than one.
+#	Return 0 otherwise.
+#
+fun squarefree( $n )
+{
+	my $max = int(sqrt($n));
+	foreach my $x (2..$max)
+	{
+		return 0 if $n % ($x*$x) == 0;
+	}
+	return 1;
+}
+
+
+my @sqfree = grep { squarefree($_) } 1..$limit;
+
+say "The smallest positive square-free integers (up to $limit) are";
+
+say join(', ', @sqfree);