Detailed mathematical approach

Problem Summary

Let \(p=398874989\) and \(G=p^2-1\). The computation is carried out in the two-dimensional algebra

$R=\mathbb{F}_p[u]/(u^2-5),\qquad \beta=u-2,$

where \(u\) plays the role of \(\sqrt5\). For the Fibonacci numbers

$F_1=F_2=1,\qquad F_n=F_{n-1}+F_{n-2},$

define the reduced exponent

$e_n\equiv 5^{F_n}\pmod G.$

If

$\beta^{e_n}=a_n+b_nu,$

then the \(n\)-th contribution is

$s_n=b_n^5+(-a_n)^5\pmod p.$

The goal is to evaluate

$S=\sum_{n=2}^{1{,}618{,}034}s_n\pmod p.$

Directly forming the Fibonacci exponents is hopeless. The successful approach is to keep only a short modular exponent recurrence and to evaluate powers of \(\beta\) inside the fixed algebra \(R\).

Mathematical Approach

The three implementations all exploit the same structure: the golden-looking base \(\sqrt5-2\), the multiplicative behavior of \(5^{F_n}\), and the fact that every relevant power can be reconstructed from a 64-entry binary table.

The split quadratic algebra and the golden element

The algebra \(R\) is represented in the basis \(1,u\) with \(u^2=5\). Multiplication is therefore

$\left(a+bu\right)\left(c+du\right)=(ac+5bd)+(ad+bc)u\pmod p.$

This is exactly the rule used by the implementations. It keeps every power of \(\beta\) in the form \(a+bu\), so the final summand is obtained by reading off two coefficients.

The adjective "golden" is not cosmetic. If

$\phi=\frac{1+\sqrt5}{2},$

then \(\phi^3=2+\sqrt5\), hence

$\beta=\sqrt5-2=\frac{1}{2+\sqrt5}=\phi^{-3}.$

Also,

$\left(u-2\right)\left(u+2\right)=u^2-4=1,$

so \(\beta\) is a unit of the algebra and every positive power is well-defined.

For this specific prime, \(p\equiv 4\pmod 5\). Since \(5\equiv 1\pmod 4\), quadratic reciprocity gives \(\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right)=\left(\frac{4}{5}\right)=1\), so \(u^2-5\) splits over \(\mathbb{F}_p\). In other words, \(R\) is a split quadratic algebra, isomorphic to \(\mathbb{F}_p\times\mathbb{F}_p\). The code does not need that isomorphism explicitly; the coefficient basis \(1,u\) is already enough.

Reducing gigantic exponents to a short modular recurrence

The Fibonacci recurrence immediately gives

$5^{F_n}=5^{F_{n-1}+F_{n-2}}=5^{F_{n-1}}5^{F_{n-2}}.$

Because \(R^\times\cong \mathbb{F}_p^\times\times\mathbb{F}_p^\times\), every unit has multiplicative period dividing \(p-1\). So any multiple of \(p-1\) is a safe modulus for exponents. The implementations use the larger quantity

$G=p^2-1=(p-1)(p+1),$

which is not minimal but is still perfectly valid because \(p-1\mid G\).

That lets us replace the astronomical integer \(5^{F_n}\) by the residue

$e_n\equiv 5^{F_n}\pmod G.$

The residues satisfy the compact recurrence

$e_1=e_2=5,\qquad e_n\equiv e_{n-1}e_{n-2}\pmod G\quad(n\ge 3).$

This is the decisive simplification. Instead of carrying Fibonacci numbers or giant exponentials, the algorithm advances the entire exponent side with one modular multiplication per step.

Conjugation and the norm give a permanent invariant

The algebra has an involution \(u\mapsto -u\), so

$\overline{a+bu}=a-bu.$

The associated norm is

$N(a+bu)=(a+bu)(a-bu)=a^2-5b^2\pmod p.$

For the base element \(\beta=u-2\),

$N(\beta)=(u-2)(-u-2)=4-u^2=-1.$

Every \(e_n\) is odd: the sequence starts from \(5,5\), and modulo the even number \(G\) the product of odd residues remains odd. Therefore

$N\!\left(\beta^{e_n}\right)=N(\beta)^{e_n}=(-1)^{e_n}=-1.$

So if

$\beta^{e_n}=a_n+b_nu,$

then the coefficients always satisfy

$a_n^2-5b_n^2\equiv -1\pmod p.$

This Pell-type congruence is not the final answer, but it explains the shape of every coefficient pair and provides a clean mathematical consistency check.

Worked example: the first accumulated terms

Starting from \(\beta=u-2\), repeated multiplication gives

$\beta^1=-2+u,$

$\beta^2=9-4u,$

$\beta^3=-38+17u,$

$\beta^4=161-72u,$

$\beta^5=-682+305u.$

The tiny checkpoint at exponent \(1\) is

$s(1)=1^5+2^5=33,$

because \(\beta^1=-2+u\). The actual sum begins at \(n=2\), where \(e_2=5\), so the first accumulated term is

$s_2=305^5+682^5\equiv 257933744\pmod p.$

The next reduced exponent is

$e_3\equiv e_2e_1\equiv 5\cdot 5\equiv 25\pmod G,$

and evaluating \(\beta^{25}\) in the same basis gives

$s_3\equiv 26500067\pmod p.$

Those two values are exactly the small checkpoints embedded in the implementations. After that, the same recurrence-and-powering pattern continues all the way to \(n=1{,}618{,}034\).

How the Code Works

Representing algebra elements

Each algebra element is stored as a pair of residues \((a,b)\) representing \(a+bu\). Multiplication uses the formula above, so every operation stays in two coordinates modulo \(p\). The quantity \((-a)^5\) is computed modulo \(p\) as the fifth power of the additive inverse of the first coordinate.

Precomputing binary powers of \(\beta\)

The C++, Python, and Java implementations precompute

$\beta^{2^0},\beta^{2^1},\dots,\beta^{2^{63}}$

by repeated squaring. That table is sufficient because the chosen exponent modulus satisfies \(0\le e_n<G<2^{64}\). Any required power \(\beta^{e_n}\) is then reconstructed from the binary expansion of \(e_n\).

Streaming the exponent recurrence and the final sum

The implementations never materialize a Fibonacci number. They keep only the two latest exponent residues, both initially equal to \(5\). The answer is initialized with the \(n=2\) term, and then for each \(n\ge 3\) they compute

$e_n\equiv e_{n-1}e_{n-2}\pmod G,$

rebuild \(\beta^{e_n}\) from the binary table, extract \(a_n\) and \(b_n\), evaluate \(b_n^5+(-a_n)^5\pmod p\), and add it to the running sum. The three language versions differ only in low-level modular-multiplication details; the mathematical pipeline is identical.

Complexity Analysis

Let \(M=1{,}618{,}034\). Precomputing the binary table costs \(64\) algebra multiplications. Each subsequent term uses one modular multiplication for the exponent recurrence and at most \(64\) algebra multiplications to reconstruct \(\beta^{e_n}\) from its bits. Therefore the running time is

$O(M\log G),$

and since \(\log G<64\), this is effectively linear in the number of required indices.

The memory usage is \(O(1)\): a constant-size power table, two current exponents, a running total, and a few temporary algebra elements.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=921
2. Fibonacci number: Wikipedia - Fibonacci number
3. Golden ratio: Wikipedia - Golden ratio
4. Modular arithmetic: Wikipedia - Modular arithmetic
5. Quotient ring: Wikipedia - Quotient ring
6. Field norm: Wikipedia - Field norm
7. Quadratic reciprocity: Wikipedia - Quadratic reciprocity
8. Exponentiation by squaring: Wikipedia - Exponentiation by squaring