RogerBW's Blog

The Weekly Challenge 164: Happy Palindromes 12 May 2022

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.

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.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 2300ad 3d printing action advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech bayern beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 crime crystal cthulhu eternal cycling dead of winter doctor who documentary drama driving drone ecchi economics en garde espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 essen 2023 essen 2024 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo 2021 hugo 2022 hugo 2023 hugo 2024 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards mpd museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby rust scala science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1