40000000 чисел Фибоначчи - это лютая вещь со всех сторон. Даже если ты врубишь мемоизацию, как посоветовал
Максим Припадчев , то там дохрена вычислений, потому что числа будут длиной в миллионы цифр.
Мы суммируем только четные числа Фибоначчи.
Легко заметить, что F(n) четное, только если n делится на 3, т.е. n = 3m.
То есть тебе нужна сумма F(3*m) для всех m от 0 до floor((40000000-2) / 3) включительно, если правильно понимаю этот ваш range.
я тут пояндексил и промыслил формулы:
1) F(3*n) = F(n+1)^3 + F(n)^3 + F(n-1)^3 (из
википедии)
2) sum[0...N] F(i)^3 = (1/2)*(F(n)*F(n+1)^2 + (-1)^(n-1)*F(n-1) + 1)
отсюда
сумму F(3*n) можно выразить через сумму F(n)^3 и потом применить формулу (2)
в итоге получается
sum[0...N] F(3*i) = (1/2)*(F(n)*F(n+1)^2 + (-1)^(n-1)*F(n-1) + 1) - 1 + F(n)^3 + F(n+1)^3
для этого выражения нам нужны F(n), F(n+1) и F(n-1) = F(n+1) - F(n)
F(n) и F(n+1) вычисляем методом "fast doubling", который делает O(ln(n)) действий вместо O(n) стандартного способа. Ускорение знатное.
Итого:
const fib = (n, a = []) => {
if (n < 1) {
a[0] = 0n;
a[1] = 1n;
} else {
const m = Math.floor(n/2);
fib(m, a);
const x = a[0] * (2n * a[1] - a[0]);
const y = a[0] * a[0] + a[1] * a[1];
if (n % 2) {
a[0] = y;
a[1] = x + y;
} else {
a[0] = x;
a[1] = y;
}
}
return a;
}
const sumFib3n = (n) => {
if (n < 1) { return 0n; }
const [fn, fnp1] = fib(n); // fn = fib(n), fnp1 = fib(n+1),
const fnm1 = fnp1 - fn; // fnm1 = fib(n-1),
const sgn = n % 2 ? 1n : -1n;
const sumPow3 = (fn * fnp1 * fnp1 + sgn * fnm1 + 1n) / 2n;
return sumPow3 - 1n + fn * fn * fn + fnp1 * fnp1 * fnp1;
}
console.log(sumFib3n(Math.floor((40000000 - 2)/3)));
