Задача 25 «1000-Значное число Фибоначчи»:

Условие:

Последовательность Фибоначчи определяется рекурсивным правилом:

F_n = F_n−1 + F_n−2, где F₁ = 1 и F₂ = 1.

Таким образом, первые 12 членов последовательности равны:

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

Двенадцатый член F₁₂ — первый член последовательности, который содержит три цифры.

Каков порядковый номер первого члена последовательности Фибоначчи, содержащего 1000 цифр?

Решение:

# 
# Решение задачи Проекта Эйлера номер 25
# 

import itertools

# Т.к желаемое число не такое и большое то мы просто идем простым циклом
def compute():
	DIGITS = 1000
	prev = 1
	cur = 0
	for i in itertools.count():
		# На этом шаге, prev = fibonacci(i - 1) и cur = fibonacci(i)
		if len(str(cur)) > DIGITS:
			raise RuntimeError("Not found")
		elif len(str(cur)) == DIGITS:
			return str(i)
		
		# Пересчитываем prev и cur по формуле чисел Фибоначчи
		prev, cur = cur, prev + cur


if __name__ == "__main__":
    print(compute())