imported my solution to task 1 of this week's tasks, although I've decided not to do task 2 as it's way too mathematical for me

3 files changed, 214 insertions, 58 deletions

diff --git a/challenge-167/duncan-c-white/README b/challenge-167/duncan-c-white/README
index c0f50441d9..e34765e0f0 100644
--- a/challenge-167/duncan-c-white/README
+++ b/challenge-167/duncan-c-white/README
@@ -1,75 +1,51 @@
-TASK 1: Hexadecimal Words
+TASK 1: Circular Prime
 
-As an old systems programmer, whenever I needed to come up with a 32-bit
-number, I would reach for the tired old examples like 0xDeadBeef and
-0xC0dedBad. I want more!
+Write a script to find out first 10 circular primes having at least 3
+digits (base 10).
 
-Write a program that will read from a dictionary and find 2- to 8-letter
-words that can be "spelled" in hexadecimal, with the addition of the
-following letter substitutions:
+Please checkout https://en.wikipedia.org/wiki/Circular_prime for more information.
 
-    o -> 0 (e.g., 0xf00d = "food")
-    l -> 1
-    i -> 1
-    s -> 5
-    t -> 7
+A circular prime is a prime number with the property that the number
+generated at each intermediate step when cyclically permuting its (base
+10) digits will also be prime.
 
-You can use your own dictionary or you can simply open
-../../../data/dictionary.txt (relative to your script's location in
-our GitHub repository) to access the dictionary of common words from
-Week #161.
+Quote from the Wikipedia page:
 
-Optional Extras (for an 0xAddedFee, of course!)
+"For example, 1193 is a circular prime, since 1931, 9311 and 3119 all
+are also prime.[3] A circular prime with at least two digits can only
+consist of combinations of the digits 1, 3, 7 or 9, because having 0, 2,
+4, 6 or 8 as the last digit makes the number divisible by 2, and having
+0 or 5 as the last digit makes it divisible by 5"
 
-    Limit the number of "special" letter substitutions in any one result
-    to keep that result at least somewhat comprehensible. (0x51105010
-    is an actual example from my sample solution you may wish to avoid!)
+OUTPUT
 
-    Find phrases of words that total 8 characters in length (e.g.,
-    0xFee1Face), rather than just individual words.
+113, 197, 199, 337, 1193, 3779, 11939, 19937, 193939, 199933
 
-MY NOTES: ok.  Not a terribly fascinating task, forget the optional extras.
-Should be simple enough.
 
+MY NOTES: ok, sounds relatively easy.  The wikipedia page clarifies it.
+I'm reusing my old favourite MakePrimes.pm.
 
-Task 2: K-Directory Diff
+HOWEVER, my solution finds far more circular primes than the above output
+shows.  If 113 is a CP (and it is cos 131 and 311 are also prime), then SO
+IS 131 AND SO IS 311, but the above list doesn't show it.  Also, my solution
+computes ALL CPs with exactly N digits, rather than the first 10 with N or
+more digits.
 
-Given a few (three or more) directories (non-recursively), display a
-side-by-side difference of files that are missing from at least one of
-the directories. Do not display files that exist in every directory.
 
-Since the task is non-recursive, if you encounter a subdirectory, append
-a /, but otherwise treat it the same as a regular file.
+Task 2: Task 2: Gamma Function
 
-Example
-
-Given the following directory structure:
-
-dir_a:
-Arial.ttf  Comic_Sans.ttf  Georgia.ttf  Helvetica.ttf  Impact.otf  Verdana.ttf  Old_Fonts/
+Implement subroutine gamma() using the Lanczos approximation method.
 
-dir_b:
-Arial.ttf  Comic_Sans.ttf  Courier_New.ttf  Helvetica.ttf  Impact.otf  Tahoma.ttf  Verdana.ttf
+Ryan Thompson wrote an interesting blog explaining the subject in
+details. Highly recommended if you are looking for more information:
+https://ry.ca/2022/05/lanczos-approximation
 
-dir_c:
-Arial.ttf  Courier_New.ttf  Helvetica.ttf  Impact.otf  Monaco.ttf  Verdana.ttf
-
-The output should look similar to the following:
-
-dir_a          | dir_b           | dir_c
--------------- | --------------- | ---------------
-Comic_Sans.ttf | Comic_Sans.ttf  |
-               | Courier_New.ttf | Courier_New.ttf
-Georgia.ttf    |                 |
-               |                 | Monaco.ttf
-Old_Fonts/     |                 |
-               | Tahoma.ttf      |
+Example
 
+print gamma(3); # 1.99
+print gamma(5); # 24
+print gamma(7); # 719.99
 
-MY NOTES: this is much more appealing to me; right up my street.  Generally,
-it seems pretty simple, build a "fileindirs" mapping from file -> a list of
-which directories it's in, and form a set of all named files, then iterate
-over the "all named files" set, skipping files present in all the dirs,
-then iterating over all the dirs, using the fileindirs info to determine
-which columns to leave blank.  Need to auto-width each dir column, but that's
-trivial to do.
+MY NOTES: Hell no.  Complex numbers, ridiculously complicated formula,
+plus I've no idea what the Gamma function even is.  This is far too
+mathematical for me, so I've no interest in doing it.
diff --git a/challenge-167/duncan-c-white/perl/MakePrimes.pm b/challenge-167/duncan-c-white/perl/MakePrimes.pm
new file mode 100644
index 0000000000..e268fa06a3
--- /dev/null
+++ b/challenge-167/duncan-c-white/perl/MakePrimes.pm
@@ -0,0 +1,90 @@
+#
+#	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-167/duncan-c-white/perl/ch-1.pl b/challenge-167/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..c9301da291
--- /dev/null
+++ b/challenge-167/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,90 @@
+#!/usr/bin/perl
+# 
+# TASK 1: Circular Prime
+# 
+# Write a script to find out first 10 circular primes having at least 3
+# digits (base 10).
+# 
+# Please checkout https://en.wikipedia.org/wiki/Circular_prime for more information.
+# 
+# A circular prime is a prime number with the property that the number
+# generated at each intermediate step when cyclically permuting its (base
+# 10) digits will also be prime.
+# 
+# Quote from the Wikipedia page:
+# 
+# "For example, 1193 is a circular prime, since 1931, 9311 and 3119 all
+# are also prime.[3] A circular prime with at least two digits can only
+# consist of combinations of the digits 1, 3, 7 or 9, because having 0, 2,
+# 4, 6 or 8 as the last digit makes the number divisible by 2, and having
+# 0 or 5 as the last digit makes it divisible by 5"
+# 
+# OUTPUT
+# 
+# 113, 197, 199, 337, 1193, 3779, 11939, 19937, 193939, 199933
+# 
+# MY NOTES: ok, sounds relatively easy.  The wikipedia page clarifies it.
+# I'm reusing my old favourite MakePrimes.pm.
+#
+# HOWEVER, my solution finds far more circular primes than the above output
+# shows.  If 113 is a CP (and it is cos 131 and 311 are also prime), then SO
+# IS 131 AND SO IS 311, but the above list doesn't show either.  Also, my
+# solution computes ALL CPs with exactly N digits (on the assumption that
+# there are probably 10 or more), rather than only the first 10 with N or
+# more digits.
+#
+# btw, for checking primeness I use
+#  perl -I. -MMakePrimes -E 'say join(",",primes_upto(999))'
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+#use Data::Dumper;
+
+use lib qw(.);
+use MakePrimes;
+
+my $debug=0;
+die "Usage: circular-prime [--debug] [NDIGITS default 3]\n"
+	unless GetOptions( "debug"=>\$debug ) && @ARGV<2;
+my $ndigits = shift // 3;
+
+my %isprime;
+
+
+#
+# my $iscp = iscircularprime($prime);
+#	Check whether prime $prime is a circular prime, using %isprime.
+#	Return 1 iff it is a circular prime, 0 otherwise.
+#
+sub iscircularprime ($)
+{
+	my( $prime ) = @_;
+	my $len = length($prime);
+	print "debug: iscp: checking whether $prime is a cp\n" if $debug;
+	foreach my $i (1..$len-1)
+	{
+		$prime =~ /^(.)(.+)$/;
+		my( $firstdigit, $rest ) = ( $1, $2 );
+		$prime = $2.$1;
+		print "debug: rotate circular gives $prime\n" if $debug;
+		return 0 unless $isprime{$prime};
+	}
+	return 1;
+}
+
+
+my $limit = 10**$ndigits-1;
+print "getting primes up to $limit\n" if $debug;
+my @primes = primes_upto( $limit );
+%isprime = map { $_ => 1 } @primes;
+
+# discard primes not ndigits long, or containing 0,2,4,5, or 8
+@primes = grep { length($_) == $ndigits && $_ !~ /[024568]/ } @primes;
+
+# discard non-circular primes
+@primes = grep { iscircularprime($_) } @primes;
+
+say join(', ', @primes);