RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved just-in-time Fibonacci and squares without repeating digits. (Note that this is open until 30 January 2022.)

And, I should say, these are both puzzles that I sent in myself, so I hope my solutions turn out well…

Task 1: Fibonacci Digit Sum

Given an input $N, generate the first $N numbers for which the sum of their digits is a Fibonacci number,

This is of course OEIS A028840.

This is obviously a two-parter: for each number, get the sum of its digits, then see whether that's a Fibonacci number. I use a set (or hash in the languages that don't explicitly support sets) to store which numbers are Fibonacci, and if I have a sum-of-digits that's higher than the highest Fibonacci I've seen yet, I generate more. Raku:

sub fds($n) {
    my @o;

Seed the sequence, and the set.

    my @f=[1,0];
    my $ft=SetHash.new(@f);
    my $k=0;
    while (@o.elems < $n) {

Get the sum of digits. Could do this with a conversion to string, but it feels cleaner to do it purely in arithmetic-space.

        my $ds=0;
        my $j=$k;
        while ($j > 0) {
            $ds += ($j % 10);
            $j div= 10;
        }

Make sure the Fibonacci set is sufficiently populated.

        while (@f[0] < $ds) {
            @f=[@f[1]+@f[0],@f[0]];
            $ft{@f[0]}++;
        }

Then test the sum of digits, push a successful candidate to the output queue, and continue.

        if ($ft{$ds}:exists) {
            push @o,$k;
        }
        $k++;
    }
    return @o;
}

Task 2: Largest Square

Given a number base, derive the largest perfect square with no repeated digits and return it as a string. (For base>10, use 'A'..'Z'.)

The largest number with no repeated digits in its base-N expression is going to be a little less than N^N-1. So this demands reasonably solid large-number handling.

One pitfall is shown up in the answer to f(2) – the solution is not always going to be a permutation of all the digits. (For more examples to prove that this isn't just an edge case, f(5)="4301" contains no "2", and f(13)="CBA504216873" contains no "9".)

So this looks like a brute-force search across the space of perfect squares. I start with the highest possible value (all the digits in descending order), find the highest perfect square that's no higher than that, and check each perfect square down from there.

I could convert the whole number to its in-base representation and then check it, but it's quicker to do it step by step, because then I can avoid all the divs and mods that aren't needed if a candidate has already been rejected.

JavaScript numbers are all IEEE doubles, which gives me 53 bits of actual precision – enough to solve with input 13 (48.1 bits), but not 14 (53.3 bits). (Yes, there are external int64 libraries, but I'm trying to avoid using too much in the way of external dependencies for these things.)

My test suite was N=2, 4, 10 and 12, and I got some unexpected timing results: Raku finished in 2.1 seconds, reasonably consistent with this 2018.12 interpreter I've been using, but normally Python and Ruby are about as nippy as Perl – and yet Python took 20 seconds and Ruby 27. All the other languages managed it in less than a second, all on the same unloaded machine. (Python and Ruby people, I welcome your telling me how I was doing maths wrong.)

Rust with compiler optimisations gets to N=16 in about two seconds on my fastest machine. (That's in single-threaded processing; this is obviously quite parallelisable, fitting the classic model of workers and a FIFO queue.)

• 2 1
• 3 1
• 4 3201
• 5 4301
• 6 452013
• 7 6250341
• 8 47302651
• 9 823146570
• 10 9814072356
• 11 A8701245369
• 12 B8750A649321
• 13 CBA504216873
• 14 DC71B30685A924
• 15 EDAC93B24658701
• 16 FED5B39A42706C81

Here's the Lua:

function ls(base)

Build the highest possible value.

   max=0
   for i = base-1, 0, -1 do
      max = max * base + i
   end

Find the highest perfect square no higher than that, and store its square root.

   t=math.floor(math.sqrt(max))
   digits="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
   while true do

Generate the perfect square.

      s=t*t
      v=true

Set up an array of digit counters.

      c={}
      for i = 0,base-1 do
         table.insert(c,0)
      end
      dg=""

Convert the number to the target base (starting at the least significant). If any of the digit counts exceeds 1, we have a repeated digit, so we abandon the effort immediately. Otherwise prepend that digit to the output string. (Note 1-based arrays.)

      while s > 0 do
         d = s % base + 1
         c[d] = c[d] + 1
         if c[d] > 1 then
            v=false
            break
         end
         s=math.floor(s/base)
         dg = string.sub(digits,d,d) .. dg
      end

If we got the answer, return it; otherwise decrement t and keep trying. (1 will always be a valid answer, so the loop will always terminate eventually.)

      if v then
         return dg
      end
      t = t - 1
   end
end

Full code on github.