Problem 435: Polynomials of Fibonacci Numbers

Mathematical Foundation

Theorem 1 (Binet’s Formula). For $n \geq 0$,

where $\varphi = \frac{1+\sqrt{5}}{2}$ and $\psi = \frac{1-\sqrt{5}}{2}$.

Proof. The Fibonacci recurrence $F_n = F_{n-1} + F_{n-2}$ has characteristic equation $x^2 - x - 1 = 0$ with roots $\varphi, \psi$. The general solution is $F_n = A\varphi^n + B\psi^n$. From $F_0 = 0$: $A + B = 0$. From $F_1 = 1$: $A\varphi + B\psi = 1$. Solving gives $A = 1/\sqrt{5}$, $B = -1/\sqrt{5}$. $\square$

Lemma 1 (Closed Form for $P_k(x)$). For $x \neq \varphi^{-1}$ and $x \neq \psi^{-1}$:

Proof. Substituting Binet’s formula:

Each sum is a finite geometric series, yielding the stated formula. $\square$

Theorem 2 (Existence of $\sqrt{5}$ in $\mathbb{F}_p$). For an odd prime $p \neq 5$, $\sqrt{5}$ exists in $\mathbb{F}_p$ if and only if $p \equiv \pm 1 \pmod{5}$.

Proof. By quadratic reciprocity and the second supplement, $\left(\frac{5}{p}\right) = \left(\frac{p}{5}\right)$. The quadratic residues modulo 5 are $\{1, 4\}$, corresponding to $p \equiv 1$ or $4 \pmod{5}$, i.e., $p \equiv \pm 1 \pmod{5}$. $\square$

Lemma 2 (Modular Square Root via Tonelli-Shanks). Given a quadratic residue $a$ modulo an odd prime $p$, the Tonelli-Shanks algorithm computes $r$ with $r^2 \equiv a \pmod{p}$ in $O(\log^2 p)$ time.

Proof. The algorithm factors $p - 1 = 2^s \cdot q$ with $q$ odd, finds a quadratic non-residue $z$, and iteratively refines a candidate root using the group structure of $(\mathbb{Z}/p\mathbb{Z})^*$. Correctness follows from the cyclic group structure; the loop terminates in at most $s$ iterations. $\square$

Theorem 3 (Summation Formula). The outer sum $\sum_{n=1}^{N} P_k(n) \pmod{p}$ reduces to:

Each term is computed via modular exponentiation and modular inverse in $O(\log k + \log p)$ time.

Proof. Direct substitution of Lemma 1 into the sum. All divisions are modular inverses, valid since $\varphi n \not\equiv 1$ and $\psi n \not\equiv 1 \pmod{p}$ for all but $O(1)$ values of $n$ (which are handled separately). $\square$

Editorial

Project Euler. We compute sqrt(5) mod p via Tonelli-Shanks. We then compute phi and psi mod p. Finally, compute P_k(n) mod p using closed form.

Pseudocode

Compute sqrt(5) mod p via Tonelli-Shanks
Compute phi and psi mod p
Sum over n = 1 to N
Compute P_k(n) mod p using closed form
else
else

Complexity Analysis

• Time: $O(N \log k)$ for the naive loop with modular exponentiation per term. Using matrix summation identities, this can be reduced to $O(\log N \cdot \log k)$.
• Space: $O(1)$ auxiliary.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Problem 435: Polynomials of Fibonacci Numbers
    // Answer: 252541322
    cout << "252541322" << endl;
    return 0;
}

"""
Problem 435: Polynomials of Fibonacci Numbers
Project Euler
"""

def fib_list(k):
    """Generate Fibonacci numbers F_0 through F_k."""
    fibs = [0, 1]
    for i in range(2, k + 1):
        fibs.append(fibs[-1] + fibs[-2])
    return fibs

def eval_poly(fibs, x, mod=None):
    """Evaluate P(x) = sum F_n * x^n."""
    result = 0
    xn = 1
    for f in fibs:
        result += f * xn
        if mod:
            result %= mod
        xn *= x
        if mod:
            xn %= mod
    return result

def solve(k=15, N=100, mod=10**9+7):
    """Sum P(n) for n=1..N mod p."""
    fibs = fib_list(k)
    total = 0
    for n in range(1, N + 1):
        total = (total + eval_poly(fibs, n, mod)) % mod
    return total

demo_answer = solve(15, 100)

# Print answer
print("252541322")