Number of ways to represent a number N as sum of K Fibonacci terms

Reading time: 30 minutes | Coding time: 5 minutes

The problem we will solve is that given a number N and K, we need to find the numbers of ways we can represent N as a sum of K fibonacci numbers. Note a fibonacci term can be repeated. We will solve this problem efficiently using a recursive technique in O(N).

What is fibonacci series ?

It is a series of numbers in which each number ( Fibonacci number ) is the sum of the two preceding numbers. The simplest is the series 1, 1, 2, 3, 5, 8, 13, etc.

F(N) = F(N-1) + F(N-2)
with F(0) = 1 and F(1) = 1

Problem

You are given 2 integers, N and K. You have to find the number of ways by which you can represent N as the sum of K fibonacci series numbers.

Suppose you are given :

N = 13 and K = 3

so, the number of ways will be 2, as 2+3+8 and 3+5+5 equals 13.

N = 14 and K = 3
again, the answer would be 2 as 8+5+1 and 8+3+3 equals 14.

Brute force

The brute force approach involves generating all fibonacci numbers less than N which takes O(N) time. In general, there are O(log N) fibonacci terms less than N. This can be dervied from Binet's formula.

Following this, we shall take combinations of all the above Fibonacci series and check for which combinations, the sum is equal to N. This takes O(N) time.

We can improve this by taking a recursive approach and avoid considering combination of fibonacci terms where the sum is > N.

Efficient recursive approach

Base Cases

1. When k=0, means no numbers are required so sum can only be 0, thus our answer will be 0 if N is not 0.
2. When N=0 and K>0, means sum required is zero but K element should be used, here also aour answer would be 0.

Approach

As we have to find fibonacci numbers, thus we will create a fibonacci sequence of n elements first and then, try to find required numbers. Note only fibonacci numbers less than or equal to the given sum is enough. For large sum, this goes to O(log N) numbers of fibonacci terms.

We can go recursively through our fibonacci sequence to find them. There are two cases while we search for answers:

1. Last number of fibonacci series is not in our sum : We will leave that last number fib[n-1] and will consider only n-2 numbers.
2. Last number of fibonacci series is in our sum : We will find the remaining N-fib[n-1] in our fibonacci sequence.

Solution Workflow:

• First, we create a fibbonacci sequence sequence and then we start our fuction.

• We first check for base cases and if it passes from it, we start checking our fibonacci sequence from last element.

• We set out index i at last element of sequence and start a while loop checking i is greater than 0 and (K * fib[i]) is greater than given N or not. We are checking (K * fib[i]) because if the last element itself it not able to complete the sum, no other number prior to it can do so as they all are smaller than it.

• Then we check it the last element is itself greater than the given sum or not, if fib[n-1] is itself greater than given sum than we have to skip this element start again from fib[n-2], and we continue to skip last elements till we find last element smaller than given N.

• Then we subtract the last element we got, from our sum N and call the fuction recursively for N as N-fib[last element] and K as K-1 and continue the process again for fib[:i] part and if we find our base cases, we return 1 or 0.

• The value returned as 1 or 0 is added to add variable and add is returned as final result.

Pseudocode

1. Create the fibonacci sequence.
2. Call the function and check for base conditions.
3. Check the condition for the last element of fibonacci sequence.
4. Call the function again recursivly with N as N-fib[n-1].

def answer(N, K, fib): 

    # base condition applied
    if K == 0: 
        if N == 0: 
            return 1
        return 0
	
    # add is the answer and len is the maximum answer
    add, i = 0, len(fib)-1 
    
    # for recursive function call 
    # fib[i] * K ensures that only fibonacci numbers <= fib[i] 
    # are considered
    while i >= 0 and fib[i] * K >= N: 
        # if fib[i] > N, it cannot be added
        if fib[i] > N: 
            i -= 1 # go to the next lower fibonacci term
            continue
        # recursively consider if fib[i] is added
        add += answer(N - fib[i], K - 1, fib[:i]) 
        i -= 1
    return add

Implementation in Python

# Initializing fibonacci sequence
fib = [0] * 43   # As 42nd fibonacci number is largest possible integer to store

# Make fibonacci sequence 
def fibonacci(): 
    fib[0] = 1
    fib[1] = 2
    for i in range(2, 43): 
        fib[i] = fib[i - 1] + fib[i - 2] 

# Recursive function
def answer(N, K, fib): 

    # base condition applied
    if K == 0: 
        if N == 0: 
            return 1
        return 0
	
    add, i = 0, len(fib)-1 
    
    # for recursive function call 
    while i >= 0 and fib[i] * K >= N: 
        if fib[i] > N: 
            i -= 1
            continue
        add += answer(N - fib[i], K - 1, fib[:i]) 
        i -= 1
    return add

### Calling functions
fibonacci()  # Creating fibonacci sequence
N, K = 13, 4
print(answer(N, K, fib[:]))

How answer function works?

• Suppose we give N=14, K=3 and fib as our arguments to answer funtion.
• First it checks for base cases, as neither K nor N is 0, we pass that check and proceed.
• Then we initialise add and i as two variables with values 0 and len(fib)-1 respectively, add will be our answer and i will work as an iterator from last of fib sequence.
• Then we check, if our iterator i is valid or not (>=0 or not), and the element on which its pointing can itself create more than the sum(N) required or not, as if the number itself k times can't complete the sum, all elements ahead would not do so as they will be even smaller. In our case i is 42 and fib[i] is 267914296 so it satisfies the conditions.
• Now we check if fib[i] is greater than the required N or not, as our N is 14 which is smaller than fib[i] or 267914296 we skip it using continue statement. We did so beacuse we need to use K elements to complete 14, but fib[i] alone makes more than required.
• We continue to skip elements till we find a fib[i] which is smaller than 14, we get that element at i=6 which is 13, now our remaining target is 14-13 which is 1, that we need to complete using k-1 or 2 elements. We call our answer fuction recursively again with N=1, K=2 and fib sequence till 7th element.
• Again, the same process is repeated but if you observe fibonacci series, its impossible to make 1 by adding two elemets. So our recursive call comes back with no solution and we move our iterator i from 6 to 5, we get fib[5] = 8, then we again call our fuction recursively with N=14-8, K=2 and fib till 6th element.
• This process of recursion and iteration continues till we find any base condition. In our case, we get our base condition when we have N=0 and K=0, means we got 14=8+5+1 and 3 elements are used, so according to base conditions, ans is returned as 1 for all recursive calls, and we proceed further to find next solution if exits.
• So, till our i reached 3, where fib[3]* K = 9 which is smaller than 14, we got two solutions for our N (8+5+1 and 8+3+3), and we return 2 as our final answer.

Time complexity

At first sight, the time complexity might seem to be O(N * K) but we need to consider several points to arrive at the better approximation. Consider answering these questions:

• How many fibonacci numbers are less than N?

One can get a good approximation of this term using Binet's equation which involves the golden ratio. In general, we can take it to be O(log N) which is close for larger N.

Hence, in this view, the while loop runs from larger to smaller fibonacci terms which results in avoiding combinations which has sum > N. In this view, we are doing better than a brute force approach.

With this, the time complexity of our approach is the number of combinations with sum <= N. We can find the exact term using Binet's formula but the simple answer is O(N) as there are logN fibonacci terms and there can be no more than 2 ^ (log N) combinations.

One can think that a Dynamic Programming approach may improve this further but it will not help much as there are no significant number of overlapping cases. You can understand it by observing the pattern or parameters of our recursive function.