Self-descriptive Numbers

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Challenge #2 this week (43) is to generate Self-descriptive Numbers in arbitrary bases. A self-descriptive number, as described by Wikipedia, is an integer m that in a given base b is b digits long in which each digit d at position n (the most significant digit being at position 0 and the least significant at position b – 1) counts how many instances of digit n are in m.

For example, 6210001000 is a base-10 self-descriptive number, because there are:

• 6 zeroes,
• 2 ones,
• 1 two,
• 1 six,
• and nothing else

For a good description of the number theory involved, check out the Wikipedia page, or this discussion between some of my absolute favourite math(s) YouTubers, James Grime, Matt Parker, and Katie Steckles:

If you want to know more about the math, including proofs for optimizations I’ve used, I encourage you to use the resources above.

Perl Solution

To handle arbitrary bases (I’ve gone up to base-35, but you’re really only limited by your imagination and your favourite Unicode font, I guess), I set up my own symbol table, with a reverse value mapping:

my @base = (0..9, 'a'..'z');
my %val  = map { $base[$_] => $_ } 0..$#base;

Now, for the function which will return all self-descriptive numbers of a given base:

sub self_descriptive_base {
    my $b = shift;

    return "$base[$b-4]21" . '0' x ($b-7) . '1000' if $b >= 7;

    grep { is_self_descriptive($_) }
     map { 10 * $_ } 10**($b-2) .. 10**($b-1) - 1;
}

You’ll see that if the base is 7 or greater, we can stitch together the answer (the only answer) from the known formula \((b-4)b^{b-1}+2b^{b-2}+b^{b-3}+b^3\).

For bases less than 7, I basically brute force the results. You may have noticed something slightly strange, however: I’m not iterating over base-n values, as you might expect. I’m iterating over n-digit numbers in base 10. I could have easily iterated over all n-digit numbers in base-n. Doing so would cut our iterations by more than half (for base 6, our worst-case), but with a much higher constant number of operations. Performance really isn’t the main driver, here.

Now, what’s with the map { 10 * $_ } ? Every self-descriptive number must be divisible by its base. Since the number is base-digits long, all self-descriptive numbers must end in zero. So I’m cutting my search space by 90% by only looking for multiples of 10, since I’m iterating in base-10.

If working in base-10 for base-1..6 numbers makes you uncomfortable, ordinarily I’d agree, but in this case we will never need to perform any operations where that will make a difference. Trust the math! Do the math!

Is a number descriptive?

We are now in need of an is_descriptive_number() sub, which will return a true value if the given number is self-descriptive. Here is that sub:

sub is_self_descriptive {
    my @s = split '', shift;

    return if @s != sum @s; # Not a Niven number

    my %count;
    $count{ $s[$_] }++ for 0..$#s;

    all { $count{$_} == $s[$_] } 0..$#s;
}

First, we split the number into digits.

Next, there is an easy optimization we can do: self-descriptive numbers are also Niven (or Harshad) numbers. That means a self-descriptive number’s sum of digits must be equal to its base, which is what we check on line 4.

If we have a Niven number, we then get the count of each digit. For example, 21200 would result in %count = ( 0 => 2, 1 => 1, 2 => 2 ).

Finally, using the definition of a self-descriptive number, we check that the $_^th digit is equal to $count{$_} for all digits.

Putting it all together

All that’s left to do is to loop through the user-supplied base and print out the results. I opted to allow the user to specify multiple bases. Simply:

for my $base (@ARGV) {
    printf "base-%2d: %s\n", $base, join ', ', self_descriptive_base($base);
}

Here are the results for bases 1 through 10, plus 15 and 35 for good measure. This runs in 200ms on my system.

[pwc/rjt_043] challenge-043/⋯/perl5 %> ./ch-2.pl 1 2 3 4 5 6 7 8 9 10 15 35
base- 1: 
base- 2: 
base- 3: 
base- 4: 1210, 2020
base- 5: 21200
base- 6: 
base- 7: 3211000
base- 8: 42101000
base- 9: 521001000
base-10: 6210001000
base-15: b21000000001000
base-35: v2100000000000000000000000000001000

There is one further optimization that can be made, and that is to use the knowledge that bases 2, 3, and 6 do not have any self-descriptive numbers. However, that was a bridge too far for me, personally, since after that there was nothing really stopping me from just returning a list of the known numbers without any computation, which would be extremely fast, but also pointless and boring.

Raku Solution

I was a bit pressed for time this week, so my Raku solution isn’t much more than a simple translation of the Perl one. Here is the main routine:

sub self-descriptive( Int $b ) {
    return @base[$b-4] ~ '21' ~ '0' x ($b-7) ~ '1000' if $b >= 7;

    ((10**($b-2) .. 10**($b-1)-1) »*» 10).grep: { is-self-descriptive($_) };
}

It is slightly more concise with the use of the »*» hyperoperator, but that’s about it. is-self-descriptive() is similar:

sub is-self-descriptive( Int $n ) {
    my @s = $n.comb;

    return False if $n.chars ≠ @s.sum; # Not a Niven number

    my %count;
    %count{ @s[$_] }++ for 0..^@s.elems;

    (0..^$n.chars).map({ (%count{$_} // 0) == @s[$_] }).all
}

Given infinite time, I’d have made this a little more Raku-ish, but I’m still happy with it as-is.