Generating nth Non-Fibonacci Number

Fibonacci Sequence:

1 1 2 3 5 8 13 21 ….

Non-Fibonacci Sequence:

4 6 7 9 10 11 12 14 15 16 17 18 19 20 …

Generating Non-Fibonacci Sequence is based on the fact that difference between adjacent Fibonacci numbers is also a Fibonacci number.


fibs[n] - fibs[n - 1] = fibs[n - 2]

So the number of Non-Fibonacci numbers between adjacent Fibonacci numbers is a Fibonacci Number

First of all lets find the sequence whose nth term is number of Non-Fibonacci Numbers between (n + 1)th fibonacci number and nth fibonacci number.

This sequence will look like: 0 0 0 1 2 4 7 12 …

lets crop that sequence to 0 0 1 2 4 7 12 …

this basically nth fibonacci number – 1, lets call this special sequence GAPS

now to find the nth fibonacci number one can easily do a linear search on the partial sum of the GAPS.

https://gist.github.com/9da4a824bb28efd7c6c8

for all practical values of n, linear search is better as nth of GAPS increases rapidly(nth term crosses 10**10 at 44th term itself), if there are lot of such queries then complexity wise a binary search would be better as GAPS is a non decreasing sequence.

Advertisements