My solutions to challenge 144

3 files changed, 119 insertions, 0 deletions

diff --git a/challenge-144/peter-campbell-smith/blog.txt b/challenge-144/peter-campbell-smith/blog.txt
new file mode 100644
index 0000000000..41721af4c7
--- /dev/null
+++ b/challenge-144/peter-campbell-smith/blog.txt
@@ -0,0 +1 @@
+https://pjcs-pwc.blogspot.com/2021/12/illuminating-ulam.html
diff --git a/challenge-144/peter-campbell-smith/perl/ch-1.pl b/challenge-144/peter-campbell-smith/perl/ch-1.pl
new file mode 100755
index 0000000000..b78ddba1e4
--- /dev/null
+++ b/challenge-144/peter-campbell-smith/perl/ch-1.pl
@@ -0,0 +1,62 @@
+#!/usr/bin/perl
+
+# Peter Campbell Smith - 2021-12-20
+# PWC 144 task 1
+
+use v5.20;
+use warnings;
+use strict;
+
+# Write a script to generate all Semiprime number <= 100.
+# 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.  This definition excludes either of the primes
+# being 1.
+
+my ($limit, $sqrt_limit, @is_prime, @semiprimes, $j, $k, $p);
+
+# find semiprimes <= $limit
+$limit = 100;
+
+# find primes up to $limit / 2
+@is_prime = make_sieve(int($limit / 2));   # $j is prime if $primes[$j] == 1
+say qq[Semiprimes no greater than $limit are:];
+
+# the smaller prime cannot exceed sqrt($limit)
+for $j (2 .. int(sqrt($limit))) {
+	next unless $is_prime[$j];
+	
+	# the larger one cannot exceed $limit / the smaller one
+	for $k ($j .. int($limit / $j)) {
+		next unless $is_prime[$k];
+		@semiprimes[$j * $k] = 1;
+	}
+}
+
+for $j (1 .. $limit) {
+	print qq[$j ] if (defined $semiprimes[$j]);
+}
+say '';
+		
+sub make_sieve {
+	
+	# make sieve of Eratosthenes
+	my ($arg, $j, $k, @sieve);
+	
+	# set all values provisionally to 1 (ie prime)
+	$arg = $_[0];
+	for $j (0 .. $arg) {
+		$sieve[$j] = 1;
+	}
+	
+	# for each prime in turn, set its multiples to 0 (ie not prime)
+	for $j (2 .. $arg) {
+		next unless $sieve[$j];   # $j is not prime		
+		last if $j ** 2 > $arg;
+		for $k ($j .. $arg) {
+			last if $k * $j > $arg;
+			$sieve[$k * $j] = 0;
+		}
+	}
+	return @sieve;
+}
\ No newline at end of file
diff --git a/challenge-144/peter-campbell-smith/perl/ch-2.pl b/challenge-144/peter-campbell-smith/perl/ch-2.pl
new file mode 100755
index 0000000000..454683be11
--- /dev/null
+++ b/challenge-144/peter-campbell-smith/perl/ch-2.pl
@@ -0,0 +1,56 @@
+#!/usr/bin/perl
+
+# Peter Campbell Smith - 2021-12-20
+# PWC 144 task 2
+
+use v5.20;
+use warnings;
+use strict;
+
+# 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.
+# The first two numbers in an Ulam sequence are the lesser (U1) and the greater (U2) of $u and $v.
+# 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.
+
+my (@tests, $test, $max_terms, @times, $t, @ulam, $j, $k, $try, $next, $last, $ulam_j);
+
+#          u  v  max
+@tests = ([1, 2, 10], [2, 3, 10], [2, 5, 100], [123, 456, 500]);
+
+for $test (@tests) {
+	($ulam[1], $ulam[2], $max_terms) = @$test;
+	say qq[\n$max_terms terms of the Ulam sequence starting with $ulam[1], $ulam[2]:];
+	
+	# loop over terms
+	for $t (3 .. $max_terms) {
+		
+		# try all the preceding pairs
+		@times = ();
+		$last = $ulam[$t - 1];
+		for $j (1 .. $t - 2) {
+			$ulam_j = $ulam[$j];   # to optimise the inner loop
+			for $k ($j + 1 .. $t - 1) {
+				$times[$ulam_j + $ulam[$k]] ++;   # no of times that $try has been found
+			}
+		}
+		
+		# now find the smallest $try where $times[$try] == 1 (which will always exist, 
+		# because ulam[$t - 1] + $ulam[$t - 2] must be a unique sum)
+		for $try ($last + 1 .. $last + $ulam[$t - 2]) {
+			next unless defined $times[$try];
+			if ($times[$try] == 1) {   # got it!
+				$ulam[$t] = $try;
+				last;
+			}
+		}		
+	}
+	
+	# and show the answer
+	for $j (1 .. $max_terms) {
+		print qq[$ulam[$j] ];
+	}
+	say '';
+}
+
+	
\ No newline at end of file