# 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)){
print "(" . join(" + ", @{\$summands}) . ") = " . \$ARGV . "\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

#### The Weekly Challenge 136 (Prolog Solutions)

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

``````
:-initialization(main).

two_friendly(M, N):-
current_prolog_flag(max_integer, MAX_INTEGER),
between(1, MAX_INTEGER, M),
between(1, MAX_INTEGER, N),
GCD is gcd(M, N),
P is log(2, GCD),
P0 is ceiling(P),
P1 is floor(P),
P0 == P1.

main:-
(two_friendly(8, 24), format("1~n", _); format("0~n", _)),
(two_friendly(26, 39), format("1~n", _); format("0~n", _)),
(two_friendly(4, 10), format("1~n", _); format("0~n", _)),
halt.
``````

### Sample Run

``````
\$ gplc prolog/ch-1.p
\$ prolog/ch-1
1
0
1
``````

### Notes

Evn after years of writing Prolog I still get quite a kick out of its inherent power. Here the `two_friendly/2` predicate not only verifies for any `M` and `N` but also is multi-modal and can generate pairs for any `M` and `N` as well!

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

``````
fibonaccis_below_n(N, Fibonaccis):-
fibonaccis_below_n(N, Fibonaccis, 0, [1, 1]).
fibonaccis_below_n(-1, Fibonaccis, _, Fibonaccis):- !.
fibonaccis_below_n(N, Fibonaccis, Sum, PartialFibonaccis):-
[H0, H1 | _] = PartialFibonaccis,
F is H0 + H1,
F < N,
fibonaccis_below_n(N, Fibonaccis, Sum, [F|PartialFibonaccis]).
fibonaccis_below_n(N, Fibonaccis, Sum, PartialFibonaccis):-
[H0, H1 | _] = PartialFibonaccis,
F is H0 + H1,
F > N,
fibonaccis_below_n(-1, Fibonaccis, Sum, PartialFibonaccis).

sum_x([], 0).
sum_x([X|Xs], X+Xse):-
sum_x(Xs, Xse).

sum_lists(X, N, Xsub):-
sublist(Xsub, X),
sum_x(Xsub, Xe),
N #= Xe.

fibonacci_sum_clp(N, Summands):-
fibonaccis_below_n(N, Fibonaccis),
sum_lists(Fibonaccis, N, Summands).
``````

### Sample Run

``````
\$ gprolog --consult-file prolog/ch-2.p
| ?- setof(Summands, fibonacci_sum_clp(16, Summands), S).

S = [[8,5,2,1],[8,5,3],[13,2,1],[13,3]]

(1 ms) yes
``````

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

I just realized as I am looking at the code that I may have slightly misnamed the `fibonacci_sum_clp/2` predicate! I was experimenting with different approaches including a clpfd one. This is clearly not really using clpfd though! Instead `sublist/2` is used to generate and test all possible sublists of the Fibonacci subsequence with values less than `N`.

## References

Challenge 136

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