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.
Fibonacci Numbers: 1,2,3,5,8,13,21,34,55,89, …
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).
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).
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).
Sequence A000119 in The On-Line Encyclopedia Of Integer Sequences gives the number of partitions of distinct Fibonnacci parts (ignoring 0, and not duplicating the 1).
This is exactly what we want.
One definition this page gives is (Reinhard Zumkeller, Nov 11, 2009):
\[ a(n) = f(n, 1, 1), \text{with } f(x, y, z) = \begin{cases} 0^x & \text{if } x < y \\ f (x - y, y + z, y) + f (x, y + z, y) & \text{if } x \geq y \end{cases} \]
To avoid having to deal with \(0^0\) which may not always be \(1\) in each of the language we will use (and we're too lazy to check), we use a slightly different, but equivalent, definition of \(f\):
\[ f(x, y, z) = \begin{cases} 0 & \text{if } x < y \\ 1 & \text{if } x = y \\ f (x - y, y + z, y) + f (x, y + z, y) & \text{if } x > y \end{cases} \]
A straight implementation of the formula above is easy. Here is one in Perl:
sub count;
sub count ($target, $this_fib = 1, $prev_fib = 1) {
$this_fib > $target ? 0
: $this_fib == $target ? 1
: count ($target - $this_fib, $this_fib + $prev_fib, $this_fib) +
count ($target, $this_fib + $prev_fib, $this_fib)
}
The problem is that it recuses. A lot. Here's a log-log graph showing how often it calls itself when called with a specific value:
Adding a cache, and not recursing if we are to calculate a value we have calculated before is easy:
sub count;
sub count ($target, $this_fib = 1, $prev_fib = 1) {
state $cache = {};
$$cache {$target, $this_fib} //=
$this_fib > $target ? 0
: $this_fib == $target ? 1
: count ($target - $this_fib, $this_fib + $prev_fib, $this_fib) +
count ($target, $this_fib + $prev_fib, $this_fib)
}
This reduces the number of calls dramatically, as shown by the graph below:
Since the graph is log-log, the difference looks less impressive that it is, but for \(n = 1,000,000\), the non-caching algorithm uses \(472,630,993\) calls, while the caching algorithm uses no more than \(3,999,941\) calls.
But while the number of recursive calls rapidly grows, even with caching, the number of different ways to partition an integer into different Fibonacci numbers only grows very slowly. In the graph below, we plotted the number of ways to partition the numbers up to 10,000. No number below 10,000 has more than 89 different ways to be partitioned into different sums of Fibonacci numbers.
Input a number below, and it shows in how many ways it can be
written as a sum of distinct Fibonacci Numbers:
Implementation we made in other languages are very similar to the one we made in Perl. We'll show a selection of implementations, without further comments.
var cache map [int] map [int] int
func _count (target int, this_fib int, prev_fib int) int {
if _, ok := cache [target]; !ok {
cache [target] = make (map [int] int)
}
if _, ok := cache [target] [this_fib]; !ok {
var result int
if target < this_fib {
result = 0
} else if target == this_fib {
result = 1
} else {
result = _count (target - this_fib, this_fib + prev_fib, this_fib) +
_count (target, this_fib + prev_fib, this_fib)
}
cache [target] [this_fib] = result
}
return cache [target] [this_fib]
}
func count (target int) int {
return _count (target, 1, 1)
}
let cache = {}
function count (target, this_fib, prev_fib) {
if (!this_fib) {this_fib = 1}
if (!prev_fib) {prev_fib = 1}
let key = target + ";" + this_fib
if (!(key in cache)) {
cache [key] = target < this_fib ? 0
: target == this_fib ? 1
: count (target - this_fib, this_fib + prev_fib, this_fib) +
count (target, this_fib + prev_fib, this_fib)
}
return cache [key]
}
cache = {}
def _count (target, this_fib, prev_fib):
key = str (target) + ";" + str (this_fib)
if not (key in cache):
if target < this_fib:
cache [key] = 0
elif target == this_fib:
cache [key] = 1
else:
cache [key] = \
_count (target - this_fib, this_fib + prev_fib, this_fib) + \
_count (target, this_fib + prev_fib, this_fib)
return cache [key]
def count (target):
return (_count (target, 1, 1))
We have implementations in AWK, Bash bc, C, Go, Java, Lua, Node.js, Pascal, Perl, Python, R, Ruby, Scheme, and Tcl on GitHub.