I’ve been doing the Weekly
Challenges. The
latest
involved two number-sequence tasks. (Note that this is open until 15
May 2022.)
Task 1: Prime Palindrome
Write a script to find out all prime numbers (<=1000), which is also
a palindrome.
Which of course we can get from the OEIS
though I didn't read up on specific generation methods.
The easiest approach seems to be in two steps: part one is to borrow
genprimes
from previous Challenges to get a list of qualifying prime
numbers, and then it's a matter of filtering that list to retain only
the ones that are numeric palindromes. (An alternative would be to
generate all palindromes and test them for primality.)
So for example in Rust, "is this number a palindrome" (we assume base
10):
fn isnumpal(c0: usize) -> bool {
let mut c = c0;
let mut j = 0;
while c > 0 {
j = 10 * j + c % 10;
c /= 10;
}
c0 == j
}
And then a generation-and-filter chain (made slightly more fiddly by
the borrow checker):
fn primepal(pmax: usize) -> Vec<usize> {
genprimes(pmax)
.iter()
.filter(|i| isnumpal(**i))
.map(|i| *i)
.collect::<Vec<usize>>()
}
In languages that don't have a filter
or grep
or some similar
"return only the elements of the list that match this condition"
operator, this becomes an explicit loop. But those languages are
pretty much just Lua. (PostScript doesn't have it natively, but it's
part of my iterables
library.)
Task 2: Happy Numbers
Write a script to find the first 8 Happy Numbers in base 10. For more information, please checkout wikipedia.
Essentially, one repeatedly takes the sum of the squares of the digits
for the number; in base 10, this will end either in 1 or in an
infinite loop:
4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → …
This is in the OEIS, and I came up with
what I think is a reasonably elegant algorithm.
We'll be building up a series of numbers during each test - for
example starting at 7 we'll progress through:
7 → 49 → 97 → 130 → 10 → 1 (known happy)
and having got to the end we now know not only that 7 is happy but
that all the others in that sequence are too. So we retain the
sequence as we go through it, and once it reaches either a known
happy/unhappy number or a value we've already seen in this progress
(which is therefore unhappy) we can assign that status to each of the
the values in the sequence. And if we later want to find the happiness
of 10, or 49, or some other number that leads to one of those values,
they'll already be stored and we don't need to do any further
calculations.
(In effect I'm using a hash of boolean values to get trinary logic:
true
and false
work normally, while a value not present in the
hash is unknown
.)
First, the sum of squared digits function ssd
follows basically the
same pattern as isnumpal
from task 1, processing a number digit by
digit. I might save a bit of time by precalculating each squared-digit
value and storing them in an array, but I'm not convinced that a
lookup would be significantly faster than a multiplication; checking
that would be a job for a profiler. Raku:
sub ssd($n0) {
my $n = $n0;
my $out = 0;
while ($n > 0) {
my $d = $n % 10;
$out += $d * $d;
$n div= 10;
}
return $out;
}
and if we were working in a different number base, this would be the
place to change it.
The main generator: initialise the map of happy/unhappy numbers %hm
(this is base-independent - 1 is canonically always happy), the
candidate number $c
, and the output list @out
.
sub happy($ct) {
my %hm = 1 => True;
my $c = 0;
my @out;
Loop over every positive integer (we'll break out when we have
enough).
loop {
$c++;
If we don't already know whether this number is happy, we'll have to
calculate it.
unless (%hm{$c}:exists) {
Set my working variable $v
equal to the candidate, the set of
numbers tried in this sequence $ss
to include that, and the
happiness value for the whole sequence $h
. (This True
value will
never actually be used.)
my $v = $c;
my $ss = SetHash.new($v);
my $h = True;
Another potentially infinite loop.
loop {
Do we know whether the current working variable is happy? If so,
assign that to the happiness value and exit.
if (%hm{$v}:exists) {
$h = %hm{$v};
last;
Otherwise, replace the working variable with the sum of its squared
digits. Have we seen that value before in this sequence? If so, all
these numbers are unhappy; exit.
} else {
$v = ssd($v);
if ($ss{$v}:exists) {
$h = False;
last;
}
Otherwise, add the new working variable value to the sequence of
numbers we've seen, and continue.
$ss{$v}++;
}
}
Now we have a set of numbers $ss
and a happiness value $h
; assign
that value to every number in the overall happiness map %hm
. (This
will inevitably include the candidate number $c
.)
$ss.keys.map({ %hm{$_} = $h });
}
Now, whether we just calculated it or we inherited it from a previous
calculation, we know whether $c
is happy. If it is, push it onto the
output list and return if we've got enough values.
if (%hm{$c}) {
@out.push($c);
if (@out.elems >= $ct) {
last;
}
}
}
return @out;
}
Full code on
github.