Find the fibonacci sum that is less than a given number in less than O(n)

Question

I am trying to work on a problem and part of the solution is to find the sum of finbonacci numbers that is less than an input number. Now the upper limit of the input number is 10**9. I have reduced the problem to the following O(n) solution, I was wondering if there is a more efficient solution.

b=[1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986, 1596, 2583, 4180, 6764, 
10945, 17710, 28656, 46367, 75024, 121392, 196417, 317810, 514228, 832039, 
1346268, 2178308, 3524577, 5702886, 9227464, 14930351, 24157816, 
39088168, 63245985, 102334154, 165580140, 267914295, 433494436, 701408732, 1134903169, 1836311902]

def test_lambda(a):
    list_numbers= filter(lambda x: x<=a, b)
    return len(list_numbers)

As you can see I am comparing the values of the list b with the given input and returning the elements that are less than the given number.

b is the list of sum of fibonaccis numbers upto that index, so the 1st number is 1, the sum is 1, the 2nd is 1 the sum is 2, the 3rd 2 the sum 4...

Do you know there is a solution of less than O(n), or you just want one? — Eugene Sh., Aug 03 '17 at 15:09
I don't know if there is a solution that is less than O(n)... — fazkan, Aug 03 '17 at 15:10
I have considered binary search but the input does not necessarily have to be in the list. So the binary search will return -1.. atleast from what I know.. — fazkan, Aug 03 '17 at 15:11
@fazkan The only thing I can think of is to use the formula for the n'th element: https://www.math.hmc.edu/funfacts/ffiles/10002.4-5.shtml — Eugene Sh., Aug 03 '17 at 15:11
Ah.. I've misread the question. You have a precalculated list. Then yes, use the binary search... — Eugene Sh., Aug 03 '17 at 15:12
@EugeneSh. yea i have used that, you are talking about the binets formula. its an approximation and it fails for large numbers... — fazkan, Aug 03 '17 at 15:12
@EugeneSh.: well the list is a running sum, so it is ordered. And we actually want to know the number of sums before the "virtual" insertion point `a`. — Willem Van Onsem, Aug 03 '17 at 15:13
@WillemVanOnsem Yeah, I have missed the fact the list is already precalculated. — Eugene Sh., Aug 03 '17 at 15:13
The sum of the first n Fibonacci numbers is fib(n+2)-1. As for efficiently finding the nearest Fibonacci number to a given number, please see https://stackoverflow.com/a/40683466/4014959 — PM 2Ring, Aug 03 '17 at 15:22
[@PM2Ring: you *did* notice the literals in array `b`, didn't you?] — greybeard, Aug 04 '17 at 08:23

Willem Van Onsem · Answer 1 · 2017-08-03T15:23:21.823

You can simply use binary search (for instance using the bisect_right function) for that:

from bisect import bisect_right

def test_lambda(a):
    return bisect_right(list_numbers,a)

Or if you want the sum that is less than the input number, you can use:

from bisect import bisect_right

def less_than(a):
    return a[bisect_right(list_numbers,a)-1]

This works since the list is pre-calculated and is strictly incrementing. So that means that it is an ordered list. Binary search works in O(log n) so searching is done efficiently. Furthermore I would add 0 to the list (at the first position), such that queries with 0 as input are resolved as well:

from bisect import bisect_right

b=[0, 1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986, 1596, 2583, 
   4180, 6764, 10945, 17710, 28656, 46367, 75024, 121392, 196417, 317810,
   514228, 832039, 1346268, 2178308, 3524577, 5702886, 9227464, 14930351,
   24157816, 39088168, 63245985, 102334154, 165580140, 267914295, 433494436,
   701408732, 1134903169, 1836311902
  ]

def less_than(a):
    return a[bisect_right(list_numbers,a)-1]

@fazkan: it is definitely *O(log n)* for searching (definitely given the elements are all different), as is documented in the `insort_left` function. — Willem Van Onsem, Aug 03 '17 at 15:15

score 0 · Answer 2 · answered Aug 03 '17 at 15:34

This can be done in O(logn)*O(logn) using matrix exponentiation please refer to the link below
https://math.stackexchange.com/questions/1102452/modulus-of-sum-of-sequence-of-fibonacci-numbers
incase you don't have enough memory to store all 10^9 sums you can use this O(logn) to calculate the i'th sum, if you want the sum less than equal to the given input you can just binary search for i

Find the fibonacci sum that is less than a given number in less than O(n)

2 Answers2