Merge pull request #1100 from dcw803/master

imported my challenge-041 submissions, 2 easy ones this week

5 files changed, 220 insertions, 37 deletions

diff --git a/challenge-041/duncan-c-white/README b/challenge-041/duncan-c-white/README
index 5bca8e63b0..8fe9330cd4 100644
--- a/challenge-041/duncan-c-white/README
+++ b/challenge-041/duncan-c-white/README
@@ -1,48 +1,26 @@
-Task 1: "Show multiple arrays content:
+Task 1: "Write a script to display attractive numbers between 1 and 50.
 
-You are given two or more arrays. Write a script to display values of
-each list at a given index.
+A number is an attractive number if the number of its prime factors is
+also prime number.
 
-For example:
-Array 1: [ I L O V E Y O U ]
-Array 2: [ 2 4 0 3 2 0 1 9 ]
-Array 3: [ ! ? £ $ % ^ & * ]
-
-We expect the following output:
-
-I 2 !
-L 4 ?
-O 0 £
-V 3 $
-E 2 %
-Y 0 ^
-O 1 &
-U 9 *
+For example: The number 20 is an attractive number, whose prime factors
+are 2, 2 and 5. The total prime factors is 3 which is also a prime number.
 "
 
-My notes: trivial.  Each array on command line as a word, i.e. array elements
-are single characters?  Allow any number of arrays (arguments) >= 2.
-Also handle the case where the arrays are not necessarily of the same length,
-by displaying '?' for any element off the end of an array.
-
+My notes: Think I have a prime-factors finder from an earlier challenge;
+should be easy given that.
 
-Task 2: "Sort SubList
 
-You are given a list of numbers and set of indices belong to the
-list. Write a script to sort the values belongs to the indices.
+Task 2: "Write a script to display the first 20 Leonardo Numbers. Read
+https://en.wikipedia.org/wiki/Leonardo_number for more information.
 
 For example:
+L(0) = 1
+L(1) = 1
+L(2) = L(0) + L(1) + 1 = 3
+L(3) = L(1) + L(2) + 1 = 5
 
-List: [ 10, 4, 1, 8, 12, 3 ]
-Indices: 0,2,5
-
-We would sort the values at indices 0, 2 and 5 i.e. 10, 1 and 3.
-
-Final List would look like below:
-List: [ 1, 4, 3, 8, 12, 10 ]
+and so on.
 "
 
-My notes: looks very easy. I guess the decision is: sort in place, or
-extract items via an array slice, sort them, then update those items
-in the original array (via another array slice?) The latter sounds
-much the easier, so let's do that:-).
+My notes: sounds very nearly as simple as Fibonacci numbers.
diff --git a/challenge-041/duncan-c-white/perl5/MakePrimes.pm b/challenge-041/duncan-c-white/perl5/MakePrimes.pm
new file mode 100644
index 0000000000..7261977c57
--- /dev/null
+++ b/challenge-041/duncan-c-white/perl5/MakePrimes.pm
@@ -0,0 +1,91 @@
+#
+#	mkprimes module (converted from mkprimes.c)
+#
+
+use strict;
+use warnings;
+use Function::Parameters;
+
+
+my $debug = 0;
+my @foundprimes;	# remember all primes we've found..
+
+
+#
+# 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";
+
+	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-041/duncan-c-white/perl5/PrimeFactors.pm b/challenge-041/duncan-c-white/perl5/PrimeFactors.pm
new file mode 100644
index 0000000000..b2c00e6353
--- /dev/null
+++ b/challenge-041/duncan-c-white/perl5/PrimeFactors.pm
@@ -0,0 +1,36 @@
+#
+# Prime factors:
+# 	compute the prime factors of a number.
+#
+
+use v5.10;	# to get "say"
+use strict;
+use warnings;
+use Function::Parameters;
+#use Data::Dumper;
+
+#
+# my @factors = prime_factors( $n, @primes );
+#	Break $n>1 apart into it's PRIME FACTORS (excluding 1),
+#	using @primes as a list of all the prime numbers <= n
+#	Return the list of prime factors, smallest first.
+#	eg. prime_factors( 228 ) = 2,2,3,19
+#
+fun prime_factors( $n, @primes )
+{
+	die "prime_factors: n ($n) must be >1\n" if $n<=1;
+	my @result;
+	foreach my $p (@primes)
+	{
+		while( $n>1 && $n % $p == 0 )
+		{
+			push @result, $p;
+			$n /= $p;
+		}
+		last if $n==1;
+	}
+	return @result;
+}
+
+
+1;
diff --git a/challenge-041/duncan-c-white/perl5/ch-1.pl b/challenge-041/duncan-c-white/perl5/ch-1.pl
new file mode 100755
index 0000000000..a4ec632005
--- /dev/null
+++ b/challenge-041/duncan-c-white/perl5/ch-1.pl
@@ -0,0 +1,41 @@
+#!/usr/bin/perl
+#
+# Task 1: "Write a script to display attractive numbers between 1 and 50.
+# 
+# A number is an attractive number if the number of its prime factors is
+# also prime number.
+# 
+# For example: The number 20 is an attractive number, whose prime factors
+# are 2, 2 and 5. The total prime factors is 3 which is also a prime number.
+# "
+# 
+# My notes: Think I have a prime-factors finder from an earlier challenge;
+# should be easy given that.
+#
+
+use v5.10;	# to get "say"
+use strict;
+use warnings;
+use Function::Parameters;
+#use Data::Dumper;
+
+use lib qw(.);	# I hate this!
+use MakePrimes;
+use PrimeFactors;
+
+die "Usage: ch-1.pl [N//50]\n" if @ARGV>1;
+
+my $n = shift // 50;
+
+my @primes = primes_upto( $n );
+my %isprime = map { $_ => 1 } @primes;
+
+foreach my $x (2..$n)
+{
+	my @factors = prime_factors( $x, @primes );
+	my $nf = @factors;
+	next unless $isprime{$nf};
+	say "$x is an attractive number, factors are: ", join(',',@factors),
+	    ", number factors $nf is prime";
+}
+
diff --git a/challenge-041/duncan-c-white/perl5/ch-2.pl b/challenge-041/duncan-c-white/perl5/ch-2.pl
new file mode 100755
index 0000000000..2b16d4521d
--- /dev/null
+++ b/challenge-041/duncan-c-white/perl5/ch-2.pl
@@ -0,0 +1,37 @@
+#!/usr/bin/perl
+#
+# Task 2: "Write a script to display the first 20 Leonardo Numbers. Read
+# https://en.wikipedia.org/wiki/Leonardo_number for more information.
+# 
+# For example:
+# L(0) = 1
+# L(1) = 1
+# L(2) = L(0) + L(1) + 1 = 3
+# L(3) = L(1) + L(2) + 1 = 5
+# 
+# and so on.
+# "
+# 
+# My notes: sounds very nearly as simple as Fibonacci numbers.
+# 
+
+use v5.10;	# to get "say"
+use strict;
+use warnings;
+#use Data::Dumper;
+
+die "Usage: ch-2.pl [N//20]\n" if @ARGV>1;
+my $n = shift // 20;
+
+my %l;
+$l{0} = 1;
+$l{1} = 1;
+say "leonardo(0) = $l{0}";
+say "leonardo(1) = $l{1}";
+
+foreach my $i (2..$n-1)
+{
+	$l{$i} = $l{$i-2} + $l{$i-1} + 1;
+	say "leonardo($i) = $l{$i}";
+}
+