Two are friendly and
Fibonacci combos
Weekly challenge 136 — 25 October 2021
Week 136: 25 Oct 2021
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.
Example 1 Input: $n = 16 Output: 4 Reason: There are 4 possible sequences that can be created using Fibonacci numbers i.e. (3 + 13), (1 + 2 + 13), (3 + 5 + 8) and (1 + 2 + 5 + 8). Example 2 Input: $n = 9 Output: 2 Reason: There are 2 possible sequences that can be created using Fibonacci numbers i.e. (1 + 3 + 5) and (1 + 8). Example 3 Input: $n = 15 Output: 2 Reason: There are 2 possible sequences that can be created using Fibonacci numbers i.e. (2 + 5 + 8) and (2 + 13).
I did not submit a solution at the time, but have written this later.
There are a number of ways to tackle this. Perhaps the most obvious one
is to create a sub fill_gap
recursive subroutine that attempts to add
Fibonacci series terms one at a time until the correct number is reached.
However, recusrion in perl is quite slow, and this challenge can be met without its use.
Note that the challenge requires each Fibonacci term to be used only once, so
the maximum number of terms to be added together cannot exceed the number of terms
which are less than $n
. For example, if $n == 11
, there are 5 smaller
terms - 1, 2, 3, 5 and 8 - and clearly a sum involving any larger term - 13, say - will be greater than 11.
So here is my algorithm:
$n
$num_fibs
i
over 1 .. 2 ** $num_fibs - 1
$i
to a binary string right zero-padded to $num_fibs
digits
So for our example of $n == 11
, $i
will range from 00001
to
11111
. We use these 0s and 1s to select the terms to add together.
For example 01010
means
(0 * 8) + (1 * 5) + (0 * 3) + (1 * 2) + (0 * 1) = 7
- which isn't 11, so that isn't a solution. But we will cover every possible combination, and will therefore find all the solutions.
Is this efficient? Well, not very, but we can short circuit it slightly
by abandoning the sum as soon as it exceeds $n
. On my machine, values up
to 1000 produce a result in under a second, and 10 000 takes 6 seconds.
Will it work for any $n
? No, because Perl integers only go up to
64 bits, so the binary conversion fails if $n
exceeds the 63rd member
of the Fibonacci series, which is 17167680177565. But I think that's good enough.
#!/usr/bin/perl # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge use v5.26; # The Weekly Challenge - 2021-10-25 use utf8; # Week 136 - task 2 - Fibonacci sequence 17167680177565 use warnings; # Peter Campbell Smith binmode STDOUT, ':utf8'; fibonacci_sequence(9); fibonacci_sequence(16); fibonacci_sequence(21); fibonacci_sequence(1000); fibonacci_sequence(10000); sub fibonacci_sequence { my ($n, @fibs, $j, $next, $num_fibs, $i, $bits, $sum, $explain, $count, $output); $n = shift; # make the fibonacci series up to $n @fibs = (1, 2); for $j (2 .. 999) { $next = $fibs[$j - 2] + $fibs[$j - 1]; last if $next > $n; $fibs[$j] = $next; } $num_fibs = scalar @fibs; $output = ''; $count = 0; # find combinations I: for $i (1 .. 2 ** $num_fibs - 1) { $bits = sprintf("%0${x}b", $i); $sum = 0; $explain = ''; # loop over items in series for $j (0 .. @fibs - 1) { if (substr($bits, $j, 1) == 1) { $sum += $fibs[$j]; next I if $sum > $n; $explain .= qq[$fibs[$j] + ]; } } if ($sum == $n) { $count ++; $output .= '(' . substr($explain, 0, -3) . '), '; } } say qq[\nInput: \$n = $n]; say qq[Output: $count\n] . substr($output, 0, -2); }
Input: $n = 9 Output: 2 (1 + 8), (1 + 3 + 5) Input: $n = 16 Output: 4 (3 + 13), (3 + 5 + 8), (1 + 2 + 13), (1 + 2 + 5 + 8) Input: $n = 1000 Output: 15 (13 + 987), (13 + 377 + 610), (13 + 144 + 233 + 610), (13 + 55 + 89 + 233 + 610), (13 + 21 + 34 + 89 + 233 + 610), (5 + 8 + 987), (5 + 8 + 377 + 610), (5 + 8 + 144 + 233 + 610), (5 + 8 + 55 + 89 + 233 + 610), (5 + 8 + 21 + 34 + 89 + 233 + 610), (2 + 3 + 8 + 987), (2 + 3 + 8 + 377 + 610), (2 + 3 + 8 + 144 + 233 + 610), (2 + 3 + 8 + 55 + 89 + 233 + 610), (2 + 3 + 8 + 21 + 34 + 89 + 233 + 610) Input: $n = 10000 Output: 21 (2 + 5 + 34 + 610 + 2584 + 6765), (2 + 5 + 34 + 610 + 987 + 1597 + 6765), (2 + 5 + 34 + 610 + 987 + 1597 + 2584 + 4181), (2 + 5 + 34 + 233 + 377 + 2584 + 6765), (2 + 5 + 34 + 233 + 377 + 987 + 1597 + 6765), (2 + 5 + 34 + 233 + 377 + 987 + 1597 + 2584 + 4181), (2 + 5 + 34 + 89 + 144 + 377 + 2584 + 6765), (2 + 5 + 34 + 89 + 144 + 377 + 987 + 1597 + 6765), (2 + 5 + 34 + 89 + 144 + 377 + 987 + 1597 + 2584 + 4181), (2 + 5 + 13 + 21 + 610 + 2584 + 6765), (2 + 5 + 13 + 21 + 610 + 987 + 1597 + 6765), (2 + 5 + 13 + 21 + 610 + 987 + 1597 + 2584 + 4181), (2 + 5 + 13 + 21 + 233 + 377 + 2584 + 6765), (2 + 5 + 13 + 21 + 233 + 377 + 987 + 1597 + 6765), (2 + 5 + 13 + 21 + 233 + 377 + 987 + 1597 + 2584 + 4181), (2 + 5 + 13 + 21 + 89 + 144 + 377 + 2584 + 6765), (2 + 5 + 13 + 21 + 89 + 144 + 377 + 987 + 1597 + 6765), (2 + 5 + 13 + 21 + 89 + 144 + 377 + 987 + 1597 + 2584 + 4181), (2 + 5 + 13 + 21 + 34 + 55 + 144 + 377 + 2584 + 6765), (2 + 5 + 13 + 21 + 34 + 55 + 144 + 377 + 987 + 1597 + 6765), (2 + 5 + 13 + 21 + 34 + 55 + 144 + 377 + 987 + 1597 + 2584 + 4181)
Any content of this website which has been created by Peter Campbell Smith is in the public domain