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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s