We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #25: N-digit Fibonacci number
  4. Discussions

Project Euler #25: N-digit Fibonacci number

  • cafelatte
     + 0 comments

    Could make up my mind whether to use a formula or run through all Fibo numbers up to 5000 digits, so I did both: 

    import sys
sys.set_int_max_str_digits(5010)
from decimal import *
import random

def fib():
    a, b = 1, 1
    while ...:
        yield a
        a, b = b, a+b

def main():
    # preload n[digits]
    n = [0]
    lastd = 0
    for i, f in enumerate(fib(), 1):
        d = len(str(f))
        if d > lastd:
            lastd = d
            n.append(i)
            if d == 5000: break
            # if d == 50: break
    # do queries
    r5 = Decimal(5**.5)
    lphi = Decimal((1+r5)/2).ln()
    
    for _ in range(int(input())):
        q = int(input())
        n_formula = (r5 * 10**(q-1)).ln() / lphi
        print( random.choice([
            n_formula.to_integral_value(rounding = ROUND_CEILING),
            n[q]
        ]))

main()