RogerBW's Blog

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.