3

Interview question: How many Fibonacci numbers exists less than a given number k? Can you find a function in terms of k, to get the number of fibonacci number less than k?

Example : n = 6

Answer: 6 as (0, 1, 1, 2, 3, 5)

Easy enough, write a loop or use the recursive definition of Fibonacci. However, that sounds too easy... is there a way to do this using the closed-form definition? (https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression)

  • Why would someone need to know this? Is it just a puzzle question, or homework? Does "sub O(n)" mean you're looking for an O(log(n)) or an O(1) or don't care? – en_Knight Apr 13 '16 at 15:07
  • Would you accept an upper or lower bound on the answer, because that might be very easy.. – en_Knight Apr 13 '16 at 15:08
  • This is an interview question. Let me add that as an edit. That's why I think its too easy to do it O(n) –  Apr 13 '16 at 15:09
  • I think the inverse of the closed form(if the inverse exists) would allows this to be calculated in O(1). It allows for Fib to be seen as a graph of discrete values. –  Apr 13 '16 at 15:18
  • Related: http://math.stackexchange.com/questions/67707/how-many-numbers-are-in-the-fibonacci-sequence – OneCricketeer Apr 13 '16 at 15:20
  • use matrix exponentiation until you exceed the number, O(log n) – uSeemSurprised Apr 13 '16 at 15:29

2 Answers2

1

Here is a close-form Python solution which is O(1). It uses Binet's formula (from the Wikipedia article that you linked to):

>>> from math import sqrt,log
>>> def numFibs(n): return int(log(sqrt(5)*n)/log((1+sqrt(5))/2))

>>> numFibs(10)
6

Which tracks with 1,1,2,3,5,8

The point is that the second term in Binet's formula is negligible and it is easy enough to invert the result of neglecting it.

The above formula counts the number of Fibonacci numbers which are less than or equal to n. It jumps by 1 with each new Fibonacci number. So, for example, numFibs(12) = 6 and numFibs(13) = 7. 13 is the 7th Fibonacci number, so if you want the number of Fibobacci numbers which are strictly smaller than n you have to introduce a lag. Something like:

def smallerFibs(n):
    if n <= 1:
        return 0
    else:
        return min(numFibs(n-1),numFibs(n))

Now smallerFibs(13) is still 6 but then smallerFibs(14) = 7. This is of course still O(1).

John Coleman
  • 51,337
  • 7
  • 54
  • 119
  • This is a great explanation! Thanks! –  Apr 13 '16 at 15:55
  • 1
    The first logic which includes the number itself, fails for the case numFibs(144), numFibs(143) & numFibs(144) both gives 11 – Dhananjayan Santhanakrishnan Apr 21 '18 at 21:13
  • I followed this method, and it is working https://math.stackexchange.com/a/67714/369172 – Dhananjayan Santhanakrishnan Apr 21 '18 at 21:29
  • 1
    @DhananjayanSanthanakrishnan Good observation. The problem seems to be that my formula makes a mistake on every other Fibonnaci number because the second term in Binet's formula alternates in sign. The "fudge factor" in that math article seems like one way. Another way is to check if `numFibs(n)` is odd. If so, also check `numFibs(n+1)`. If that number is even -- return it, otherwise return the original value. – John Coleman Apr 21 '18 at 21:48
0

I think it's fairly easy to see the growth of this number, at least. By the Binet / De-Moivre formula,

fn = (φn - ψn) / 5

Since |ψ| < 1 < φ, then

fn ∼ φn / 5.

From this it follows that the number of Fibonacci numbers smaller than x grows like logφ(5x).

Ami Tavory
  • 74,578
  • 11
  • 141
  • 185