aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJames Smith <js5@sanger.ac.uk>2021-12-25 02:10:46 +0000
committerGitHub <noreply@github.com>2021-12-25 02:10:46 +0000
commitc139fdc57151c6da87eca44ab018d5e3a2f25ea3 (patch)
treeb48f107ed6c6ab3c8d165da4dc12975fc9968d50
parent77c3dd4216f84bafa208dd4c67018b3f714a932f (diff)
downloadperlweeklychallenge-club-c139fdc57151c6da87eca44ab018d5e3a2f25ea3.tar.gz
perlweeklychallenge-club-c139fdc57151c6da87eca44ab018d5e3a2f25ea3.tar.bz2
perlweeklychallenge-club-c139fdc57151c6da87eca44ab018d5e3a2f25ea3.zip
Update README.md
-rw-r--r--challenge-144/james-smith/README.md7
1 files changed, 7 insertions, 0 deletions
diff --git a/challenge-144/james-smith/README.md b/challenge-144/james-smith/README.md
index 09e1bfe578..d479af154d 100644
--- a/challenge-144/james-smith/README.md
+++ b/challenge-144/james-smith/README.md
@@ -20,6 +20,11 @@ https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-144/ja
## The solution
+Rather than looping through each number to find if it is a semiprime - instead we find all the primes and multiply these together.
+We realise we need the primes up to $N/2, and so compute them. Then for each prime we push all multiples of the prime with all
+the previous primes (filtering for values less than or equal to $N)
+
+This method is faster than the loop method about 9x faster than the loop method for `$N = 10,000`.
```perl
my $N = 1000;
my @primes = (2);
@@ -41,6 +46,8 @@ The standard Ulam sequence (the (1, 2)-Ulam sequence) starts with U1 = 1 and U2
## The solution
+For ulam numbers - we use an array and a hash to store previous ulam numbers. That allows us to quickly find those which have 1 unique partition. We do this with the grep in the 3rd line of the function. We then continue until the the array has the appropriate size. (We know there will be at least one solution the sum of the last two ulam numbers)
+
```perl
sub ulam {
my%seq_hash=map{$_,$_}my@seq=($_[0],my$n=$_[1]);