2

I´m solving a problem in which i have to print all the fibonacci numbers such that:

a <= f <= b

And i would like to start them by the smallest fibonacci number that is greater than or equal to a, in order to make my program run faster. For that, i need to define a variable "n", such that the nth Fibonacci number satisfies the condition above (smallest one that is greater than or equal to a). To define such variable, i need to find the smallest "n" that satisfies the fibonacci(n) general term equation.

I tried to find it by making a for loop, but it just ends up being as slow as if i started to check from the first Fibonacci Number. Anyone has any ideas on how to define it efficiently?

P.S. Here is my attempted code:

from math import sqrt, log, ceil

def Fibo(n):
    if n == 1: return 1
    elif n == 2: return 2
    return Fibo(n-1) + Fibo(n-2)


while True:
    try:
        a, b = [int(i) for i in input().split()]
        cont = 0

        phi = (sqrt(5) + 1) / 2
        i = ceil(log(a * sqrt(5), phi))
        if Fibo(i-1) >= a: i -= 1
        elif Fibo(n) < a: i += 1

        while True:
            if a <= Fibo(i) <= b: cont += 1
            elif Fibo(i) > b:
                break
            i -= 1

        print(cont)
    except input() == "0 0":
        break
Rory Daulton
  • 21,934
  • 6
  • 42
  • 50
Mateus Buarque
  • 255
  • 1
  • 2
  • 9
  • 1
    Sure, you just need to compute Fibonacci numbers in a non-slow way. – bipll Feb 18 '18 at 14:10
  • 5
    There's a constant-time formula for calculating nth fibonacci number: https://stackoverflow.com/a/19892721/125816 – Sergio Tulentsev Feb 18 '18 at 14:11
  • 1
    So you want to have a faster solution, but faster than what? You haven't shown your attempt. – Mr. T Feb 18 '18 at 14:35
  • This is the URI problem 1722. My program is running in 4s, so it doesn´t fit in the time limit of 1s. Here´s my code: https://repl.it/@MateusBuarque/URI-1722 @MrT – Mateus Buarque Feb 18 '18 at 16:58

1 Answers1

0

Probably the most useful formula for your purpose for F(n), the nth Fibonacci number, is

from math import sqrt

phi = (sqrt(5) + 1) / 2  # the golden ratio
F(n) = round(phi**n / sqrt(5))

Therefore, one formula to get the value of n for a given value of a is

from math import sqrt, log, ceil

phi = (sqrt(5) + 1) / 2  # the golden ratio
n = ceil(log(a * sqrt(5), phi))

Due to approximation and rounding issues, you should check the values of n-1, n, and n+1 to ensure you got exactly the desired value. If you do this often, you should pre-define variables holding the value of the golden ratio and of the square root of five. If your value of a is too large for the float type to store it accurately, you would need a more complicated routine to handle the larger number.

Rory Daulton
  • 21,934
  • 6
  • 42
  • 50
  • @MateusBuarque: On this site, show your appreciation by upvoting all the useful answers. You do that by clicking the up-arrow at the top-left of the answer, if you have enough reputation to do so. (You do not have enough reputation yet to do this.) In addition, accept the best answer (if it actually answers your question) by clicking the checkmark near the top-left of the answer. That is better than saying thanks in a comment. It also helps others to see that your question was answered. – Rory Daulton Feb 18 '18 at 17:13