# RabbitFarm

### 2021-10-31

#### Friendly Fibonacci Summands

The examples used here are from The Weekly Challenge problem statement and demonstrate the working solution.

## Part 1

You are given 2 positive numbers, \$m and \$n. Write a script to find out if the given two numbers are Two Friendly.

### Solution

``````
use strict;
use warnings;
use POSIX;
use boolean;

sub euclid {
my(\$a, \$b) = @_;
return (\$b) ? euclid(\$b, \$a % \$b) : \$a;
}

sub two_friendly{
my(\$m, \$n) = @_;
my \$gcd = euclid(\$m, \$n);
my \$p = log(\$gcd) / log(2);
return boolean(ceil(\$p) == floor(\$p));
}

MAIN:{
print two_friendly(8, 24). "\n";
print two_friendly(26, 39). "\n";
print two_friendly(4, 10). "\n";
}
``````

### Sample Run

``````
\$ perl perl/ch-1.pl
1
0
1
``````

### Notes

I've used this code for Euclid's GCD method before in Challenge 089. To determine if `\$p` is an integer we check to see if the `floor()` and `ceiling()` are equal.

## Part 2

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.

### Solution

``````
use strict;
use warnings;
use Data::PowerSet q/powerset/;

sub fibonacci_below_n{
my(\$n, \$fibonaccis) = @_;
\$fibonaccis = [1, 1] if !\$fibonaccis;
my \$f = \$fibonaccis->[@{\$fibonaccis} - 2] + \$fibonaccis->[@{\$fibonaccis} - 1];
if(\$f < \$n){
push @{\$fibonaccis}, \$f;
fibonacci_below_n(\$n, \$fibonaccis);
}
else{
shift @{\$fibonaccis};
return \$fibonaccis;
}
}

sub fibonacci_sum{
my(\$n) = @_;
my \$powerset = powerset(fibonacci_below_n(\$n));
my @summands = grep {
my \$fibonaccis = \$_;
my \$sum = 0;
map{
\$sum += \$_;
} @{\$fibonaccis};
\$sum == \$n;
} @{\$powerset};
return @summands;
}

MAIN:{
for my \$summands (fibonacci_sum(\$ARGV[0])){
print "(" . join(" + ", @{\$summands}) . ") = " . \$ARGV[0] . "\n";
}
}
``````

### Sample Run

``````
\$ perl perl/ch-2.pl 16
(3 + 13) = 16
(1 + 2 + 13) = 16
(3 + 5 + 8) = 16
(1 + 2 + 5 + 8) = 16
``````

### Notes

Instead of using a pre-computed list of Fibonacci numbers we generate them as needed. No particular reason other than it's a little more fun, and also it allows us to flexibly allow for virtually any value for `\$n`.

The sequences are determined by examining the Power Set of all possible sequences and checking the sums.

## References

Challenge 136

Power Set

posted at: 20:09 by: Adam Russell | path: /perl | permanent link to this entry