This content originally appeared on DEV Community and was authored by Simon Green
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 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)
This content originally appeared on DEV Community and was authored by Simon Green
Simon Green | Sciencx (2022-01-30T22:17:18+00:00) Weekly Challenge 149. Retrieved from https://www.scien.cx/2022/01/30/weekly-challenge-149/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.