Task — Fibonacci sequence

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.

Examples

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).

Analysis

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:

• Calculate the Fibonacci terms which do not exceed $n
• Let the number of those be $num_fibs
• Loop i over 1 .. 2 ** $num_fibs - 1
• Convert $i to a binary string right zero-padded to $num_fibs digits
• Use the bits of that to indicate which terms are to be added together as a trial solution

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.

Try it 

Try running the script with any input:

Your $n =

example: 42

⤡

#!/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);
}

Output

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)