I’ve been doing the Weekly
Challenges. The
latest
involved some interesting mathematical sequences. (Note that this is
open until 26 December 2021.)
Task 1: Semiprime
Write a script to generate all Semiprime number <= 100.
where a semiprime number is
the product of exactly two primes.
I did this in two steps: (1) get all the relevant prime numbers (sieve
of Eratosthenes), (2) multiply them to get semiprimes. In Raku:
sub semiprime($mx) {
my @primes;
{
Make a list of candidate primes. (Use a lower ceiling here; if the
semiprimes are going up to 100, we only need primes in the range
2..50.)
my $mxx=floor($mx/2);
my $primesh=(2..$mxx).SetHash;
Start with a test divisor.
my $p=2;
If the square is higher than the maximum, bail out because there will
be no more numbers to be removed.
while ($p*$p <= $mxx) {
See whether this number is still regarded as plausibly prime. If it's
not, we've already removed all its multiples from earlier passes.
if ($primesh{$p}:exists) {
Start at number-squared, because again any smaller factors have been
removed. (E.g. 5×2
and 5×3
were already removed when we did 2×5
and 3×5
.)
my $i=$p*$p;
Iterate deleting multiples of this number.
while ($i <= $mxx) {
$primesh{$i}:delete;
$i += $p;
}
}
(All the non-Perl languages offer me some easy way of iterating on a
range with a step; for example in Ruby
(p*p..mxx).step(p) do |i|
primesh.delete?(i)
end
which I find easier to comprehend at a glance than the while-loop
approach.)
Jump to the next plausible-prime (all the odd numbers after 2); I
could generate candidates using the (6k-1,6k+1)
loop I had for
challenge 139 task 2, but given that all we're doing for each
non-prime is a hash lookup this seems like optimisation enough. If
this were performance-critical I'd write both versions and profile
them. Maybe eventually I'll write a library function to generate all
primes up to a set limit, with all the optimisations, in each
language I use for these things.
if ($p==2) {
$p--;
}
$p+=2;
}
Take the remaining list of primes, sort it, and drop it into an array.
@primes=$primesh.keys.sort;
}
That's part 1 done. Part 2 is quite similar in that it builds up an
unordered list with deduplication. This time we start with an empty list:
my $semiprimesh=SetHash();
Iterate over the primes.
for 0..@primes.end -> $i {
Iterate from this prime to the end of the list (so we'll multiply a
number by itself, but we don't calculate both a×b
and b×a
).
for $i..@primes.end -> $j {
Calculate the product, and store if it's within the maximum value.
(Otherwise bail out of the inner loop, since we know @primes
is
sorted, so all values calculated in the rest of this loop would also
be too high.)
my $t=@primes[$i]*@primes[$j];
if ($t <= $mx) {
$semiprimesh{$t}++;
} else {
next;
}
}
}
Get it out as a list.
return $semiprimesh.keys.map({$_+0}).sort;
}
This works in PostScript too (using a dict
in place of the Set
).
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.
where the next entry in an Ulam
sequence is the lowest
number larger than the previous entry, that can be made by summing
exactly one combination of previous entries. (Yes, that Ulam.)
I used a sieving algorithm. sieve[0]
is the sieve value for
candidate number 1
, etc. I'll show this one in Kotlin.
fun ulam(u: Int, v: Int, ccount: Int): ArrayList<Int> {
var ulams=arrayListOf<Int>(u,v)
var sieve=ArrayList<Int>()
var uc=v
while (ulams.size < ccount) {
Extend the sieve list with zeroes until it's large enough to account
for the next number (which can't be higher than the sum of the last
two numbers found). (Several languages have ways of generating a list
of a set number of zeroes; it's quite possible Kotlin does too and I
simply haven't found it yet.)
for (i in sieve.size..uc+ulams[ulams.size-2]) {
sieve.add(0)
}
For each number in the candidate space (from the most recent up to the
sum of the most recent two), add 1 to its sieve value – i.e. increment
the number of ways of constructing it. (If it's constructible from an
earlier pair of numbers, we'll have checked that on a previous pass.)
for (i in 0..ulams.size-2) {
sieve[uc + ulams[i] - 1] += 1
}
Then look through the sieve list: the first sieve entry we find with a
value of 1 (i.e. which has exactly one possible construction) is the
next number in the sequence.
for (i in uc..sieve.size-1) {
if (sieve[i] == 1) {
uc=i+1
ulams.add(uc)
break
}
}
}
return ulams
}
And because I am a glutton for punishment I've added Lua to the
languages I'm doing this in. (As with Ruby, it's the language needed
for code that runs within something I already work with – in this case
Tabletop Simulator – so I want to get some facility with it on a
"proper" system before I try to get things working in a restricted
environment.) The main weirdness is that it really wants you to
start your array indices at 1… and its arrays are hashes really. Not
fast, but readily embeddable, which is its point.
Full code on
github.
Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.