PyPE solution to PE problem 25

    ProjectEuler.net problem 25
    ===========================

    The Fibonacci sequence is defined by the recurrence relation:

        F_(n) = F_(n-1) + F_(n-2), where F_(1) = 1 and F_(2) = 1.

    Hence the first 12 terms will be:

        F_(1) = 1
        F_(2) = 1
        F_(3) = 2
        F_(4) = 3
        F_(5) = 5
        F_(6) = 8
        F_(7) = 13
        F_(8) = 21
        F_(9) = 34
        F_(10) = 55
        F_(11) = 89
        F_(12) = 144

    The 12th term, F_(12), is the first term to contain three digits.

    What is the first term in the Fibonacci sequence to contain 1000 digits?

    Solution
    --------

    The first approach we used was a brute-force method beginning at the index
    n = 3+4*(digits-1). Note that this is not rigorous, however applies for
    this case. This algorithm is not guaranteed to be general.

    Later, the following solution was implemented which dramatically increases
    the performance of the algorithm, effectively reducing it to a mathematical
    equation that scales with Pythons numerical capabilities.

    To say that a number has 1000 digits is to say that the number is greater
    than 10**999. The quick-form of the nth Fibonacci number is [phi**n/sqrt(5)]
    where [] implies "nearest integer" and phi is the golden ratio.

    So, what we are looking for is:

        phi**n / sqrt(5) > 10**999
        n*log(phi) - log(5)/2 > 999*log(10)
        n*log(phi) > 999*log(10) + log(5)/2
        n > (999*log(10) + log(5)/2) / log(phi)

    By taking the ceil of the resulting RHS, we get the index of the first
    Fibonacci number with greater than 1000 digits.

    Answer
    ------

    4782