## DEV Community is a community of 868,017 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Simon Green

Posted on

# Weekly Challenge 149

## 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.

### 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

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 nn 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 264-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)
``````