Сумма четных чисел Фибоначчи

Question

Нужно посчитать сумму четных чисел Фибоначчи, которые не превышают 4 миллиона. Увидел закономерность, что начиная с числа 2(первого парного числа Фибоначчи) парным является каждое 3 число. 2 3 5 8 13 21 34 и т.д. Сделал такое решение, но интересно, есть ли еще более быстрое и красивое решение?

import math
def fib(number): 
    fn=0
    phi = (1 + math.sqrt(5)) / 2
    fn = (1 / math.sqrt(5)) * (phi**number - (math.cos(math.pi * number)) / phi**number)
    print(math.trunc(fn)),
    return math.trunc(fn)

currentFib = 0
i=1
sum=0

while currentFib<4*10**6:
    currentFib = fib(i*3)
    i+=1
    sum+=currentFib
print("\n" + str(sum))

Answer 1

Если понаблюдать за последовательностью, можно попробовать изобразить нечто такое:

def solve(N):
    sum_ = 0
    even, next_ = 0, 1

    while even <= N:
        sum_ += even
        next_, even = (
            3 * next_ + 2 * even,
            2 * next_ + even,
        )

    return sum_

Или даже так:

def solve2(N):
    sum_ = 0 
    a, b = 0, 2

    while b <= N:
        sum_ += b
        a, b = b, a+4*b

    return sum_

assert solve(4e6) == 4613732
assert solve2(4e6) == 4613732

Answer 2

т.к. ответ задачи не зависит ни от каких входных параметров, то самым быстрым способом будет:

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 для числа F_n ≤ N можно так:

n = trunc( log(N*sqrt(5), phi) )

Но если N само является числом Фибоначчи (в частности чётным), то эта проверка может вернуть n на единицу меньше, поэтому нужна дополнительная проверка:

  if (n%3 == 2 && fib(n+1) <= N):
    n = n+1

Чётные числа Фибоначчи имеют вид F_3n, поэтому:

n //= 3;

Далее, из того что

Σ(F_n) = F_n+2 - 1

не сложно вывести, что

Σ(F_3n) = (F_3n+2 - 1) / 2

, т.е. итоговая сумма вычисляется как:

(fib(n*3+2)-1)/2;

Замечания

т.к. всё это использует арифметику с плавающей точкой, то всё это будет работать пока хватает точности мантисы т.е. примерно для чисел до 2^50.
Большое количество арифметики с плавающей точкой при вычислении определённого числа Фибоначчи по обобщённой версии формулы Бине — тоже довольно тяжёлая штука, так что на практике его имеет смысл заменить чем-то динамическим.

Answer 3

Многие факты в моём ответе уже были упомянуты в вопросе и в ответах, но я хочу собрать всё вместе и кое-что добавить.

В вопросе упоминается что чётными являются только числа вида F_3k (доказывается по индукции). Заметим что F_3k = F_3k-2 + F_3k-1. Тогда вместо суммирования чётных чисел можно суммировать все и затем разделить их пополам:

∑_k=1ⁿ F_3k = (∑_j=1³ⁿ F_j) / 2

Сумма ряда Фибоначчи равна послеследующему числу Фибоначчи без единицы:

∑_k=1ⁿ F_k = F_n+2 - 1, доказывается по индукции.

Наша задача свелась к поиску последнего чётного числа Фибоначчи, которое меньше четырёх миллионов. Потом надо сделать два шага по последовательности вперёд и ответ готов.

Последнее число Фибоначчи можно отыскать за логарифм. Из статьи Числа Фибоначчи заимствуем формулу F_n+m = F_n-1F_m + F_nF_m+1. Работать будем с парами чисел: P_k = (F_k-1, F_k). Тогда

P_n+m = (F_n+m-1, F_n+m) = (F_n-1F_m-1 + F_nF_m, F_n-1F_m + F_nF_m+1) = (F_n-1F_m-1 + F_nF_m, F_n-1F_m + F_n(F_m-1 + F_m)).

Обратите внимание что P_n+m вычисляется по значениям P_n и P_m. Введём обозначение P_n+m = P_n ⊕ P_m.

Построим последовательность P₁, P₂, P_2², ..., P_2^k, ... (P_2^k+1 = P_2^k ⊕ P_2^k). Остановимся когда очередной член окажется больше порога.

Двигаясь по последовательности в обратном направлении накопим максимальную сумму (в смысле операции ⊕) членов, которая не превосходит порога.

Найденная пара не обязательно заканчивается чётным числом, надо будет отступить до ближайшего чётного, затем сделать два шага вперёд и вычислить ответ.

Все эти сложности для того чтобы решить задачу за логарифмическое количество арифметических операций.

add(p, q) вычисляет p ⊕ q, где p, q – пары последовательных чисел Фибонначи.

dec вычисляет предыдущую пару, inc следующую.

max_p(n) вычисляет такую пару (F_k-1, F_k), что F_k ≤ n < F_k+1.

main вводит n, находит последнюю пару, откатывается назад до чётного числа Фибоначчи, делает два шага вперёд, вычисляет и печатает результат.

zero = 1, 0  # 0
one = 0, 1   # 1


def add(p, q):
    ''' p + q '''
    return (
        p[0] * q[0] + p[1] *  q[1]         ,
        p[0] * q[1] + p[1] * (q[0] + q[1])
    )


def dec(p):
    ''' p - 1 '''
    return p[1] - p[0], p[0]


def inc(p):
    ''' p + 1 '''
    return p[1], p[0] + p[1] 


def max_p(n):
    ''' (f_k-1, f_k): f_k <= n < f_k+1 '''
    p = one
    ps = []           # p_1, p_2, p_4, ..., p_2^k, ...
    while p[1] < n:
        ps.append(p)
        p = add(p, p)
    s = zero
    for p in reversed(ps):
        s2 = add(s, p)
        if s2[1] <= n:
            s = s2
    return s


def main():
    n = int(input())
    p = max_p(n)
    while p[1] % 2 != 0:
        p = dec(p)
    p = inc(inc(p))
    print((p[1] - 1) // 2)


main()

Одна секунда для n = 10²⁰⁰⁰⁰⁰, причём половину этого времени Питон тратит на печать результата:

$ echo 500 | python even_fib_sum.py
188

$ echo 4000000 | python even_fib_sum.py
4613732

$ time -p python -c "print('1' + '0' * 200000)" | python even_fib_sum.py | wc -L
200000

real 1.05
user 1.06
sys 0.00

БЛОГ НА HUSL

Сумма четных чисел Фибоначчи

Ответы (3 шт):

Объяснения/обоснования

Замечания