Weekly Challenge 149

Challenge, My solutions

TASK #1 › Fibonacci Digit Sum

Task

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

My solutions

This is (hopefully) a relatively straight forward task. We have a loop that increments by 1 until we have $N numbers. For each iteration, I have a is_sum_fib to determine if the number meets the criteria. I have a global variable fibs that keeps a count of all Fibonacci numbers, and top up the array if the last computed one is less than the sum of digits.

The Perl code is a transliteration of the Python code, with the fibs array a private persistent variable using the state declaration.

Examples

$ ./ch-1.py 20
0, 1, 2, 3, 5, 8, 10, 11, 12, 14, 17, 20, 21, 23, 26, 30, 32, 35, 41, 44

$ ./ch-1.pl 20
0, 1, 2, 3, 5, 8, 10, 11, 12, 14, 17, 20, 21, 23, 26, 30, 32, 35, 41, 44

TASK #2 › Largest Square

Task

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’.)

Python solution

There appears to be two ways to solve this one. One is to work out the maximum square nⁿ work downwards and see if that number is has no repeating digits. The other is to work downwards from the maximum unique values and see if that number is square. I'm sure they bright sparks in Team PWC may have an even better solution, and am looking forward to reading every ones blog posts.

I choose the second method. It works fine when n <= 12, struggles (takes a wee while to produce a result) on most numbers bases between 13-22, and outright fails on larger number bases. While Python can handle an infinite number of digits in an integer, the math.sqrt function is bound by 2⁶⁴-1.

So on with my explanation. I start by creating a string v with all the digits in reverse order (so A9876543210 for base 11). This is the highest possible value that can be expressed as unique digits. I then use python's itertools.permutations function to work through all possible unique digits in reverse order. As we get to a number that starts with 0, I restart the permutations call with one less digit.

As the permutations call uses the yield command, we don't need to dump all possible permutations into memory. For each uniquely digited number, I convert it to an integer, and see if it is a perfect square.

I did write a Perl solution, but am not happy with it enough that I'm going to share it :-/

Examples

$ ./ch-2.py 2
1 (1² = 1)

$ ./ch-2.py 4
3201 (15² = 225)

$ ./ch-2.py 10
9814072356 (99066² = 9814072356)

$ ./ch-2.py 12
B8750A649321 (2950717² = 8706730814089)