Fibonacci sums and unrepeatable digits

Fibonacci sums

Task 1 of week 149 asks us for the first 20 numbers, the sum of whose digits is a Fibonacci number.

It's easy to see that such numbers are quite common, so scanning up from 0 will work quickly enough. So only two functions are required:

sum_of_digits($j)

is_a_fibonacci_number($k)

The first of these doesn't need a sub as it can be done in one line of Perl:

$s = eval(join('+', split(//, $j)))

The 'split' splits the number into an array of digits, the 'join' joins them together with plus signs, and the 'eval' evaluates the string of plusses.

The Fibonacci series is easy to extend, so let's start with just (0, 1), and when we are testing a number for being in the series, we'll extend the series far enough that the last member is more than the number we're testing.

And there you have it.

Unrepeatable digits

Task 2 says given a number base, derive the largest perfect square with no repeated digits and return it as a string.

A number base b is made up from a pallete of b different digits - for example a base 4 number can only contain digits from the set 0, 1, 2 and 3.  So the largest number, base b, with no repeated digits can't be more than b digits long and it comprises the digits b - 1, b -2 ... 0.  For example, if b is 6, the largest number with no repeated digits is 543210. Generalising that, the number (call it z) is:

sum from j = 1 to b - 1 of j * (b**j)

z may not of course be a perfect square, but any number meeting the 'largest perfect square with no repeated digits' criterion must be no more than z.  So let's take the square root of z and truncate it to an integer, m.  We can then scan downwards from m to 1, checking each m**2 to see if it has no repeating digits, and the first one that meets that test is our answer.

This works fine up to b = 16.  Beyond that, Perl (or possibly my computer) cannot represent z as an integer and while my algorithm still holds, converting the initial m**2 to a string fails because it isn't held to sufficient precision. Fortunately Mohammad doesn't ask us to go that high.