Merge pull request #5419 from dcw803/master

imported my solutions to this week's tasks; particularly enjoyed task 2 (the Ulam sequence one)

4 files changed, 335 insertions, 40 deletions

diff --git a/challenge-144/duncan-c-white/README b/challenge-144/duncan-c-white/README
index 917ee497cb..fe2fd0f394 100644
--- a/challenge-144/duncan-c-white/README
+++ b/challenge-144/duncan-c-white/README
@@ -1,63 +1,57 @@
-TASK #1 - Calculator
+TASK #1 - Semiprime
 
-You are given a string, $s, containing mathematical expression.
+Write a script to generate all Semiprime number <= 100.
 
-Write a script to print the result of the mathematical expression. To
-keep it simple, please only accept + - * ().
+For more information about Semiprime, please checkout the wikipedia page
+https://en.wikipedia.org/wiki/Semiprime
 
-Example 1:
+In mathematics, a semiprime is a natural number that is the product of
+exactly two prime numbers. The two primes in the product may equal each
+other, so the semiprimes include the squares of prime numbers.
 
-    Input: $s = "10 + 20 - 5"
-    Output: 25
+Example
 
-Example 2:
+	10 is Semiprime as 10 = 2 x 5
+	15 is Semiprime as 15 = 3 x 5
 
-    Input: $s = "(10 + 20 - 5) * 2"
-    Output: 50
+MY NOTES: Sounds easy, using my existing factors function, and
+my existing prime generation code.
 
-MY NOTES: Ok, so a mini parser of a string in one or more command
-   line arguments.   What's the easiest way?
-   - use Parse::RecDescent?
-   - hand write a recursive descent parser?
-   - convert to RPN and evaluate RPN?
 
+TASK #2 - Ulam Sequence
 
-TASK #2 - Stealthy Number
+You are given two positive numbers, $u and $v.
 
-You are given a positive number, $n.
+Write a script to generate Ulam Sequence having at least 10 Ulam numbers
+where $u and $v are the first 2 Ulam numbers.
 
-Write a script to find out if the given number is Stealthy Number.
+For more information about Ulam Sequence, please checkout the website
+https://en.wikipedia.org/wiki/Ulam_number
 
-A positive integer N is stealthy, if there exist positive integers
-a, b, c, d such that a * b = c * d = N and a + b = c + d + 1.
+The standard Ulam sequence (the (1, 2)-Ulam sequence) starts with U1 =
+1 and U2 = 2. Then for n > 2, Un is defined to be the smallest integer
+that is the sum of two distinct earlier terms in exactly one way and
+larger than all earlier terms.
 
 Example 1
 
-	Input: $n = 36
-	Output: 1
-
-	Since 36 = 4 (a) * 9 (b) = 6 (c) * 6 (d) and
-	4 (a) + 9 (b) = 6 (c) + 6 (d) + 1.
+	Input: $u = 1, $v = 2
+	Output: 1, 2, 3, 4, 6, 8, 11, 13, 16, 18
 
 Example 2
 
-	Input: $n = 12
-	Output: 1
-
-	Since 2 * 6 = 3 * 4 and 2 + 6 = 3 + 4 + 1
+	Input: $u = 2, $v = 3
+	Output: 2, 3, 5, 7, 8, 9, 13, 14, 18, 19
 
 Example 3
 
-	Input: $n = 6
-	Output: 0
-
-	Since 2 * 3 = 1 * 6 but 2 + 3 != 1 + 6 + 1
-
+	Input: $u = 2, $v = 5
+	Output: 2, 5, 7, 9, 11, 12, 13, 15, 19, 23
 
-MY NOTES: hmm..  need some kind of brute force search, presumably.
-what are the limits of a..d?  first thought: each <= $n,
-hang on, (a,b) must be a factor pair of n (where a is a factor of n
-<= sqrt(n) and b is n/a), and (c,d) must also be a factor pair of n.
 
-As a bonus, I've also implemented the --firstn flag which makes it
-find and display the first $n stealthy numbers.
+MY NOTES: hmm..  sounds relatively straightforward.  I'm slightly puzzled
+by "in exactly one way", but the wikipedia gives an example that clarifies it.
+So presumably we're going to check each distinct pair of earlier terms,
+checking whether the sum of that pair is an Ulam number at all, whether it's
+greater than the last term we've found, and then pick the smallest of all
+such numbers found.  Obviously O(N**2) or worse.
diff --git a/challenge-144/duncan-c-white/perl/MakePrimes.pm b/challenge-144/duncan-c-white/perl/MakePrimes.pm
new file mode 100644
index 0000000000..7261977c57
--- /dev/null
+++ b/challenge-144/duncan-c-white/perl/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-144/duncan-c-white/perl/ch-1.pl b/challenge-144/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..18516cef9f
--- /dev/null
+++ b/challenge-144/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,79 @@
+#!/usr/bin/perl
+# 
+# TASK #1 - Semiprime
+# 
+# Write a script to generate all Semiprime number <= 100.
+# 
+# For more information about Semiprime, please checkout the wikipedia page
+# https://en.wikipedia.org/wiki/Semiprime
+# 
+# In mathematics, a semiprime is a natural number that is the product of
+# exactly two prime numbers. The two primes in the product may equal each
+# other, so the semiprimes include the squares of prime numbers.
+# 
+# Example
+# 
+# 	10 is Semiprime as 10 = 2 x 5
+# 	15 is Semiprime as 15 = 3 x 5
+# 
+# MY NOTES: Sounds easy, using my existing factors function, and
+# my existing prime generation code.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Data::Dumper;
+use Function::Parameters;
+
+use lib ".";
+use MakePrimes;
+
+my $debug=0;
+my %isprime;
+
+
+#
+# my @div = divisors( $n );
+#       Find and return all the divisors of $n, excluding 1.
+#
+fun divisors( $n )
+{
+        my @d = ();
+        my $halfn = int($n/2);
+        for( my $i=2; $i<=$halfn; $i++ )
+        {
+                push @d, $i if $n%$i==0;
+        }
+        return @d;
+}
+
+
+#
+# my $issp = semiprime( $x );
+#	Return 1 iff $x is semi-prime.
+#
+fun semiprime( $x )
+{
+	my @div = divisors( $x );
+	push @div, $div[0] if @div == 1;
+	return 0 unless @div == 2;
+	return 0 unless $isprime{$div[0]} && $isprime{$div[1]};
+	return 1;
+}
+
+
+die "Usage: semiprimes-lesseq-N [--debug] [N (default 100)]\n" unless
+	GetOptions( "debug"=>\$debug ) && @ARGV<2;
+
+my $n = shift // 100;
+
+%isprime = map { $_ => 1 } primes_upto( $n );
+
+my @sp;
+for( my $i=1; $i<=$n; $i++ )
+{
+	push @sp, $i if semiprime($i);
+}
+say join(', ', @sp );
diff --git a/challenge-144/duncan-c-white/perl/ch-2.pl b/challenge-144/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..f0e629bb5e
--- /dev/null
+++ b/challenge-144/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,131 @@
+#!/usr/bin/perl
+# 
+# TASK #2 - Ulam Sequence
+# 
+# You are given two positive numbers, $u and $v.
+# 
+# Write a script to generate Ulam Sequence having at least 10 Ulam numbers
+# where $u and $v are the first 2 Ulam numbers.
+# 
+# For more information about Ulam Sequence, please checkout the website
+# https://en.wikipedia.org/wiki/Ulam_number
+# 
+# The standard Ulam sequence (the (1, 2)-Ulam sequence) starts with U1 =
+# 1 and U2 = 2. Then for n > 2, Un is defined to be the smallest integer
+# that is the sum of two distinct earlier terms in exactly one way and
+# larger than all earlier terms.
+# 
+# Example 1
+# 
+# 	Input: $u = 1, $v = 2
+# 	Output: 1, 2, 3, 4, 6, 8, 11, 13, 16, 18
+# 
+# Example 2
+# 
+# 	Input: $u = 2, $v = 3
+# 	Output: 2, 3, 5, 7, 8, 9, 13, 14, 18, 19
+# 
+# Example 3
+# 
+# 	Input: $u = 2, $v = 5
+# 	Output: 2, 5, 7, 9, 11, 12, 13, 15, 19, 23
+# 
+# 
+# MY NOTES: hmm..  sounds relatively straightforward.  I'm slightly puzzled
+# by "in exactly one way", but an article linked from the Wikipedia page
+# gives the clearer definition:
+#
+# Un+1 is the smallest integer > Un that can be written Uj+Uk for exactly
+# one pair (j,k) where 1<=j<k<=n.
+#
+# The "exactly one pair" suggests to me a frequency hash of pair-sums.
+# So I propose:
+# - we check each distinct pair of earlier terms Uj, Uk,
+# - building a frequency hash of all $freq{Uj+Uk > Un} we find.
+# Then pick all keys of %freq whose frequency is 1.
+# Then pick the smallest.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Data::Dumper;
+use Function::Parameters;
+
+
+my $debug=0;
+
+
+#
+# my $next = next_ulam( @terms );
+#	Given @terms, an array of Ulam terms found so far,
+#	find and return the next Ulam term.
+#	Remember: Un+1 is the smallest integer > Un that can be written
+#	  Uj+Uk for exactly one pair (j,k) where 1<=j<k<=n.
+#
+#	The "exactly one pair" suggests to me a frequency hash.
+#	So I propose:
+#	- we check each distinct pair of earlier terms Uj, Uk,
+#	- building a frequency hash of all $freq{Uj+Uk > Un} we find.
+#	Then pick all keys of %freq whose frequency is 1.
+#	Then pick the smallest.
+#
+fun next_ulam( @terms )
+{
+	my $min = 1+$terms[-1];		# next term must be >= $min
+
+	my %freq;			# frequency hash of all pairsums
+
+	# foreach distinct pair of terms ($t1,$t2)..
+	for( my $i=0; $i<@terms-1; $i++ )
+	{
+		my $t1 = $terms[$i];
+		for( my $j=$i+1; $j<@terms; $j++ )
+		{
+			my $t2 = $terms[$j];
+			my $sum = $t1 + $t2;
+
+			$freq{$sum}++ if $sum >= $min;
+		}
+	}
+	say "debug: ", Dumper \%freq if $debug;
+
+	# select values with frequency 1
+	my @f1 = grep { $freq{$_}==1 } keys %freq;
+
+	# sort values numerically
+	@f1 = sort { $a <=> $b } @f1;
+	
+	# return first (smallest) of the sorted values
+	return $f1[0];
+}
+
+
+#
+# my @ulam = ulam_seq( $u, $v, $n );
+#	Find the Ulam sequence with $n terms, of which the first two
+#	are $u and $v.  See the main definition at the top of this file
+#	for full definitions of Ulam sequences.
+#
+fun ulam_seq( $u, $v, $n )
+{
+	my @us = ( $u, $v );		# ulam sequence so far;
+	for( my $i=3; $i<=$n; $i++ )
+	{
+		# find the next ulam sequence term
+		my $nextterm = next_ulam( @us );
+		push @us, $nextterm;
+	}
+	return @us;
+}
+
+
+die "Usage: ulam-sequence [--debug] U V [NTerms default 10]\n" unless
+	GetOptions( "debug"=>\$debug ) && (@ARGV==2 || @ARGV==3);
+my $u = shift;
+my $v = shift;
+my $n = shift // 10;
+
+my @ulam = ulam_seq( $u, $v, $n );
+say join(', ', @ulam );