RogerBW's Blog

The Weekly Challenge 149: Fibonacci Squares 27 January 2022

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.

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 3d printing action advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech aviation base commerce battletech 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 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 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 2022 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