т.к. ответ задачи не зависит ни от каких входных параметров, то самым быстрым способом будет:
print(4613732)
В случае если обобщать задачу на «найти сумму чётных чисел Фибоначчи, которые не превышают N
» то можно сделать как-то так:
from math import log, sqrt, trunc
def sum_phib_even(N):
if (N<8):
return 2
phi = (1 + sqrt(5)) / 2
n = trunc( log(N*sqrt(5), phi) )
if (n%3 == 2 and fib(n+1) <= N):
n = n+1
n //= 3
return (fib(n*3+2) - 1) / 2
Объяснения/обоснования
Для малых N результат может быть некорректен, поэтому сразу отметаем этот случай:
if (N<8): return 2
Найти n
для числа Fn ≤ N можно так:
n = trunc( log(N*sqrt(5), phi) )
Но если N
само является числом Фибоначчи (в частности чётным), то эта проверка может вернуть n
на единицу меньше, поэтому нужна дополнительная проверка:
if (n%3 == 2 && fib(n+1) <= N):
n = n+1
Чётные числа Фибоначчи имеют вид F3n, поэтому:
n //= 3;
Далее, из того что
не сложно вывести, что
, т.е. итоговая сумма вычисляется как:
(fib(n*3+2)-1)/2;
Замечания
- т.к. всё это использует арифметику с плавающей точкой, то всё это будет работать пока хватает точности мантисы т.е. примерно для чисел до 2^50.
- Большое количество арифметики с плавающей точкой при вычислении определённого числа Фибоначчи по обобщённой версии формулы Бине — тоже довольно тяжёлая штука, так что на практике его имеет смысл заменить чем-то динамическим.