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.