John Lekberg


JUNTO Practice - "Project Euler Problem 25"

Discussed on 2018-11-08.

Project Euler Problem 25


Solution - John

import math

from decimal import Decimal


def way1():
    def fibonacci():
        a, b = 1, 1
        while True:
            yield a
            a, b = b, a + b

    threshold = 10 ** (1000 - 1)

    fib_above = (
        (i, n)
        for i, n in enumerate(fibonacci(), start=1)
        if n >= threshold
    )

    i, _ = next(fib_above)

    return i


def way2():
    phi = (1 + Decimal(5).sqrt()) / 2

    # Binet’s Formula
    estimate = (999 + Decimal(5).sqrt().log10()) / phi.log10()

    return math.ceil(estimate)


print(way1())
print(way2())

Solution - Oscar

# This code runs into the maxiumum recursion depth and so cannot reliably be used.

import sys

sys.setrecursionlimit(5000)


def fib(n_prime=1):
    n_prime += n_prime
    if len(str(n_prime)) <= 1000:
        return fib(n_prime)
    else:
        return n_prime


print(fib())

# %%

# This yields the answer

ind = 0
i = 1
while len(str(i)) < 1000:
    i += i
    ind += 1
len(str(i))
print(f"The index of the fibonacci number {i} is {ind}.")