project euler 25 fibonacci

Saying that a number contains 1000 digits is the same as

saying that it's greater than 10**999.

The nth Fibonacci number is [phi**n / sqrt(5)], where the

brackets denote "nearest integer".

So we need 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)

A handheld calculator shows the right hand side to be

4781.8593, so 4782 is the first integer n with the

desired property.

Why bother with a computer on this one?

import time

start = time.time()

sed_2 = 1

sed_1 = 1

for i in range(3,1000000):

    sed = sed_1 + sed_2

  #  print(sed)

    if  len(str(sed)) == 1000:

        res = i

        break

    sed_1,sed_2 = sed,sed_1

print(i)

print(time.time()- start)

>>>

4782

0.15599989891052246

>>>