Detailed mathematical approach

Problem Summary

The sequence defines rational points \(P_n=(x_n,y_n)\) on one fixed hyperbola. If

$x_n=\frac{a_n}{b_n},\qquad y_n=\frac{c_n}{d_n}$

are written in lowest terms with positive denominators, the required value is the checksum

$C_n \equiv a_n+b_n+c_n+d_n \pmod{10^9+7}.$

The hard part is that the target index is enormous, so a direct rational simulation of the recurrence is useless. The implementations instead extract a closed form for the point coordinates and evaluate that form purely modulo \(10^9+7\).

Mathematical Approach

Step 1: A Rational Parameter of the Hyperbola

The implementations begin with the auxiliary sequence

$u_1=100,\qquad u_2=-\frac{75}{2},\qquad u_n=\frac{25u_{n-2}}{u_{n-1}}\qquad (n\ge 3).$

The point coordinates are then reconstructed by

$x_n=\frac{3u_n^2+2500}{25u_n},\qquad y_n=\frac{4u_n^2-1875}{25u_n}.$

These formulas immediately yield two useful linear combinations:

$3x_n+4y_n=u_n,\qquad 4x_n-3y_n=\frac{625}{u_n}.$

Multiplying them gives

$\boxed{(3x_n+4y_n)(4x_n-3y_n)=625,}$

so every \(P_n\) lies on the same hyperbola. The sequence \(u_n\) is therefore a rational parameter of that curve.

Step 2: Remove the Constant Factor \(25\)

Set

$q_n=\frac{u_n}{25}.$

Then the recurrence simplifies to

$q_1=4,\qquad q_2=-\frac{3}{2},\qquad q_n=\frac{q_{n-2}}{q_{n-1}}\qquad (n\ge 3).$

This normalized form is the key observation: only the primes \(2\) and \(3\) appear, so the whole problem becomes a recurrence on exponents and signs.

Step 3: Exponent Recurrences Become Fibonacci and Lucas

Write each term as

$q_n=\varepsilon_n\,2^{a_n}3^{b_n},\qquad \varepsilon_n\in\{-1,+1\},$

where negative exponents simply mean factors in the denominator. Taking \(2\)-adic and \(3\)-adic valuations in

$q_n=\frac{q_{n-2}}{q_{n-1}}$

gives the linear recurrences

$a_n=a_{n-2}-a_{n-1},\qquad b_n=b_{n-2}-b_{n-1},$

with initial values

$a_1=2,\ a_2=-1,\qquad b_1=0,\ b_2=1.$

Now define

$A_n=(-1)^{n+1}a_n,\qquad B_n=(-1)^n b_n.$

Then both sequences satisfy the ordinary Fibonacci recurrence

$A_n=A_{n-1}+A_{n-2},\qquad B_n=B_{n-1}+B_{n-2}.$

The initial values identify them uniquely as

$A_n=L_{n-1},\qquad B_n=F_{n-1},$

where \(F_k\) and \(L_k\) are the Fibonacci and Lucas numbers with

$F_0=0,\ F_1=1,\qquad L_0=2,\ L_1=1.$

Therefore

$a_n=(-1)^{n+1}L_{n-1},\qquad b_n=(-1)^nF_{n-1}.$

The sign follows the same recurrence: from \(q_n=q_{n-2}/q_{n-1}\) we get

$\varepsilon_n=\varepsilon_{n-2}\varepsilon_{n-1},\qquad \varepsilon_1=+1,\ \varepsilon_2=-1,$

so

$\varepsilon_n=(-1)^{F_{n-1}}.$

Step 4: Closed Forms for \(u_n\), \(x_n\), and \(y_n\)

Let \(k=n-1\) and define

$\sigma=(-1)^{F_k}.$

Then the normalized recurrence has the exact solution

$q_n=\sigma\begin{cases} \dfrac{2^{L_k}}{3^{F_k}}, & n \text{ odd},\\[6pt] \dfrac{3^{F_k}}{2^{L_k}}, & n \text{ even}. \end{cases}$

Multiplying by \(25\) gives the auxiliary parameter

$u_n=25q_n=25\sigma\begin{cases} \dfrac{2^{L_k}}{3^{F_k}}, & n \text{ odd},\\[6pt] \dfrac{3^{F_k}}{2^{L_k}}, & n \text{ even}. \end{cases}$

To make the coordinate formulas symmetric, define \((\alpha,\beta)\) by parity:

$n \text{ odd}: \alpha=2^{L_k},\ \beta=3^{F_k},\qquad n \text{ even}: \alpha=3^{F_k},\ \beta=2^{L_k}.$

Then in both cases \(u_n=25\sigma\alpha/\beta\), and substitution into the coordinate formulas yields

$\boxed{x_n=\sigma\frac{3\alpha^2+4\beta^2}{\alpha\beta},\qquad y_n=\sigma\frac{4\alpha^2-3\beta^2}{\alpha\beta}.}$

This is the exact algebraic form used by the modular solver.

Step 5: Reduce the Fractions to Lowest Terms

The checksum uses reduced fractions, so we must know the common factors of each raw numerator with the raw denominator \(\alpha\beta\).

For odd \(n\), \(\alpha\) is a power of \(2\) and \(\beta\) is a power of \(3\). When \(n\ge 3\), \(\alpha\) is divisible by \(8\) and \(\beta\) is divisible by \(3\). Then:

$3\alpha^2+4\beta^2\ \text{is divisible by}\ 12,$

but after dividing by \(12\) the result is odd and not divisible by \(3\), so no larger common factor with \(\alpha\beta\) remains. By contrast,

$4\alpha^2-3\beta^2\equiv 1 \pmod 3,\qquad 4\alpha^2-3\beta^2\equiv 5 \pmod 8,$

so it is coprime to \(\alpha\beta\). Hence

$\gcd(3\alpha^2+4\beta^2,\alpha\beta)=\begin{cases}4,&n=1,\\12,&n\ge 3\text{ odd},\end{cases}\qquad \gcd(4\alpha^2-3\beta^2,\alpha\beta)=1\ \text{for odd }n.$

For even \(n\), the roles of powers of \(2\) and \(3\) are reversed. Then \(3\alpha^2+4\beta^2\) is odd and congruent to \(1 \pmod 3\), so it is already reduced. The other numerator has exactly one factor \(3\), and for \(n\ge 4\) exactly two factors of \(2\):

$\gcd(3\alpha^2+4\beta^2,\alpha\beta)=1\ \text{for even }n,$

$\gcd(4\alpha^2-3\beta^2,\alpha\beta)=\begin{cases}6,&n=2,\\12,&n\ge 4\text{ even}.\end{cases}$

These fixed divisors are exactly the small reductions used before the checksum is formed.

Step 6: Worked Example at \(n=7\)

This index is one of the implementation checkpoints. Here \(k=6\), so

$F_6=8,\qquad L_6=18,\qquad \sigma=(-1)^8=1.$

Because \(7\) is odd, we take

$\alpha=2^{18}=262144,\qquad \beta=3^8=6561.$

Then

$x_7=\frac{3\alpha^2+4\beta^2}{\alpha\beta}=\frac{206330617092}{1719926784}=\frac{17194218091}{143327232},$

where the reduction factor is \(12\), and

$y_7=\frac{4\alpha^2-3\beta^2}{\alpha\beta}=\frac{274748766781}{1719926784},$

which is already reduced. These are exactly the rational checkpoint values used to verify the formula.

Step 7: Pure Modular Evaluation for Huge \(n\)

Let \(M=10^9+7\). Since \(M\) is prime and neither \(2\) nor \(3\) is divisible by \(M\), Fermat's little theorem allows exponent reduction modulo

$M-1=10^9+6.$

So the implementation computes \(F_k\) and \(F_{k+1}\) modulo \(M-1\), then derives

$L_k=2F_{k+1}-F_k.$

The Fibonacci pair is obtained by fast doubling:

$F_{2m}=F_m(2F_{m+1}-F_m),\qquad F_{2m+1}=F_m^2+F_{m+1}^2.$

Once \(F_k\) and \(L_k\) are known modulo \(M-1\), the powers \(2^{L_k}\) and \(3^{F_k}\) are computed modulo \(M\). Division by \(4\), \(6\), or \(12\) is replaced by multiplication with modular inverses:

$a^{-1}\equiv a^{M-2}\pmod M.$

The sign is also cheap: Fibonacci parity has period \(3\), so \(F_k\) is even exactly when \(k\equiv 0\pmod 3\). Therefore \(\sigma=+1\) in that case and \(\sigma=-1\) otherwise.

How the Code Works

The C++, Python, and Java implementations all follow the same pipeline. They compute \(k=n-1\), obtain \(F_k\) and \(F_{k+1}\) by fast doubling modulo \(10^9+6\), recover \(L_k\), choose the correct parity branch for \((\alpha,\beta)\), form the two raw numerators and the common raw denominator modulo \(10^9+7\), divide by the known reduction factors with modular inverses, and finally add the four reduced pieces. The C++ implementation also checks the formula against exact rational arithmetic for small indices, which confirms that the modular shortcut is mathematically exact.

Complexity Analysis

Fast doubling computes Fibonacci data in \(O(\log n)\) time. Modular exponentiation also costs \(O(\log M)\), which is constant-sized compared with the growth of \(n\). The overall solver therefore runs in \(O(\log n)\) time and \(O(1)\) memory. That is why an index as large as \(11^{14}\) is completely feasible.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=422
2. Fibonacci numbers: Wikipedia — Fibonacci number
3. Lucas numbers: Wikipedia — Lucas number
4. Hyperbola: Wikipedia — Hyperbola
5. Modular multiplicative inverse: Wikipedia — Modular multiplicative inverse