Weekly Challenge 136

Challenge, My solutions

TASK #1 › Two Friendly

Task

You are given 2 positive numbers, $m and $n.

Write a script to find out if the given two numbers are Two Friendly.

Two positive numbers, m and n are two friendly when gcd(m, n) = 2^p where p > 0. The greatest common divisor (gcd) of a set of numbers is the largest positive number that divides all the numbers in the set without remainder.

My solution

Pretty straight forward task to start with. It really is broken down to two parts. Both of them are rather crude methods of finding a solution. Given that we are dealing with small numbers, this really isn't a major issue.

1. Calculate the G.C.D. For this I start the lower value of the two inputs, and count down by one until we find a number that divides both inputs with no remainder.
2. Calculate whether the GCD is a power of two. For this I set the variable $i to count from 1. If 2^$i is the GCD, we return 1. If it is larger than the GCD, we return zero. Otherwise we add one to $i and check again.

Now that I think about it (a few days after I wrote this code), a better solution would be to divide both numbers by 2 until their is an odd number. With these two numbers, if any of them are divisible by any other number (between 3 and the smallest), then we know that the combination is not a number of two.

Examples

$ ./ch-1.pl 8 24
1

$ ./ch-1.pl 26 39
0

$ ./ch-1.pl 4 10
1

TASK #2 › Fibonacci Sequence

Task

You are given a positive number $n.

Write a script to find how many different sequences you can create using Fibonacci numbers where the sum of unique numbers in each sequence are the same as the given number.

My solution

I start by generating a list of Fibonacci numbers between one and the input. Although the sequence actually starts with (0, 1), I take a short cut and start with (1, 2).

Like with the above task, there are probably two ways to solve this (although some bright sparks might have an even better solution). The first method is to use a binary switch to compute all possible solutions. This works well when there is a small number of solutions, the possible solutions is 2ⁿ where n is the number of Fibonacci numbers.

In the end I decided to use a recursive function _find_sums. It takes two inputs, the remaining target and the remaining numbers. For each iteration I pop off the largest number. If that number or all remaining numbers match the target then we count this as a solution. If the remaining numbers is larger than the remaining target, we call the function again. If it is less, no solution is possible.

Finally I display the result.

Examples

$ ./ch-2.pl 16
4

$ ./ch-2.pl 9
2

$ ./ch-2.pl 15
2