Project Euler Problem 422

Solution

Answer: 92060460

Let

$$Q(x,y)=12x^2+7xy-12y^2.$$

The hyperbola is

$$H:\quad Q(x,y)=625,$$

and $X=(7,1)\in H$.

We define $P_n$ recursively by the geometric condition:

$P_1=(13,\tfrac{61}{4})$,
$P_2=(-\tfrac{43}{6},-4)$,
for $n>2$, $P_n$ is the second intersection of $H$ with the line through $P_{n-1}$ parallel to $XP_{n-2}$.

We must compute $P_n$ for

$$n=11^{14}$$

and return

$$(a+b+c+d)\bmod 1{,}000{,}000{,}007$$

where

$$P_n=\left(\frac ab,\frac cd\right)$$

in lowest terms.

1. Mathematical analysis

Step 1: Parametrize the hyperbola through $X$

Take a line through $X=(7,1)$ with slope $u$:

$$(x,y)=(7+t,1+ut).$$

Substitute into $Q(x,y)=625$:

$$12(7+t)^2+7(7+t)(1+ut)-12(1+ut)^2=625.$$

Factoring gives:

$$t\left(12tu^2-7tu-12t-25u-175\right)=0.$$

One root is $t=0$ (the point $X$); the second intersection is

$$t=\frac{25u+175}{12u^2-7u-12}.$$

Thus every point on $H$ (except asymptotic directions) corresponds to a parameter $u$.

The quadratic denominator factors:

$$12u^2-7u-12 = 12\left(u-\frac43\right)\left(u+\frac34\right).$$

This suggests the substitution

$$z = \frac{u-\frac43}{u+\frac34}.$$

Solving for $u$,

$$u=\frac{\frac43+\frac34 z}{1-z}.$$

Substituting into the point coordinates simplifies beautifully:

$$x=3z+\frac4z, \qquad y=\frac{16}{3z}-\frac94 z.$$

Step 2: Find the recurrence in $z_n$

Let $z_n$ correspond to $P_n$.

The condition “$P_nP_{n-1}$ parallel to $XP_{n-2}$” can be translated algebraically.

After substitution and simplification, the recurrence becomes:

$$z_n=\frac{4z_{n-2}}{3z_{n-1}}.$$

Initial values:

$$z_1=\frac13, \qquad z_2=-\frac89.$$

Checking:

$$z_3 = \frac{4(1/3)}{3(-8/9)} = -\frac12,$$

$$z_4 = \frac{4(-8/9)}{3(-1/2)} = \frac{64}{27},$$

matching the problem data.

Step 3: Prime-exponent form

Since everything starts as powers of $2$ and $3$, write

$$z_n=\pm 2^{A_n}3^{B_n}.$$

The recurrence gives:

$$A_n=A_{n-2}-A_{n-1}+2,$$

$$B_n=B_{n-2}-B_{n-1}-1,$$

with

$$A_1=0,\ A_2=3,$$

$$B_1=-1,\ B_2=-2.$$

For $n=11^{14}$:

$n$ is odd,
$n\equiv 1\pmod 3$,

so $z_n>0$, and for large odd $n$,

$$A_n<0,\qquad B_n>0.$$

Thus

$$z_n=\frac{3^{B_n}}{2^{-A_n}}.$$

Let

$$p=3^{B_n}, \qquad q=2^{-A_n}.$$

Then

$$z_n=\frac pq.$$

Coordinates become:

$$x=\frac{3p^2+4q^2}{pq},$$

$$y=\frac{64q^2-27p^2}{12pq}.$$

For odd $n$ here, both fractions are already reduced.

Step 4: Modular exponent computation

We only need the final sum modulo

$$M=1{,}000{,}000{,}007.$$

Since $M$ is prime, exponents are reduced modulo $M-1$.

Fast matrix exponentiation on the affine recurrences gives:

$$A_n \equiv 852174610 \pmod{M-1},$$

$$B_n \equiv 218412851 \pmod{M-1}.$$

Since $A_n<0$,

$$-A_n \equiv 147825396 \pmod{M-1}.$$

Hence

$$p\equiv 3^{218412851}\pmod M,$$

$$q\equiv 2^{147825396}\pmod M.$$

Then:

$$a=3p^2+4q^2,$$

$$b=pq,$$

$$c=64q^2-27p^2,$$

$$d=12pq.$$

Finally:

$$(a+b+c+d)\bmod M = 92060460.$$

2. Python implementation

MOD = 1_000_000_007
PHI = MOD - 1

n = 11**14

def matrix_mul(A, B, mod):
    """Multiply two 3x3 matrices modulo mod."""
    return [
        [
            sum(A[i][k] * B[k][j] for k in range(3)) % mod
            for j in range(3)
        ]
        for i in range(3)
    ]

def recurrence_mod(n, x1, x2, c):
    """
    Solve:
        x_n = x_{n-2} - x_{n-1} + c
    modulo PHI.
    """
    if n == 1:
        return x1 % PHI
    if n == 2:
        return x2 % PHI

    # State vector:
    # [x_n, x_{n-1}, 1]
    M = [
        [-1 % PHI, 1, c % PHI],
        [1, 0, 0],
        [0, 0, 1]
    ]

    # Fast exponentiation
    power = n - 2
    result = [
        [1, 0, 0],
        [0, 1, 0],
        [0, 0, 1]
    ]

    while power:
        if power & 1:
            result = matrix_mul(result, M, PHI)
        M = matrix_mul(M, M, PHI)
        power >>= 1

    vec = [x2 % PHI, x1 % PHI, 1]

    xn = sum(result[0][i] * vec[i] for i in range(3)) % PHI
    return xn

# Compute exponent residues
A_mod = recurrence_mod(n, 0, 3, 2)
B_mod = recurrence_mod(n, -1, -2, -1)

# Since A_n is negative for this n
exp2 = (-A_mod) % PHI
exp3 = B_mod

p = pow(3, exp3, MOD)
q = pow(2, exp2, MOD)

# Coordinates modulo MOD
a = (3 * p * p + 4 * q * q) % MOD
b = (p * q) % MOD

c = (64 * q * q - 27 * p * p) % MOD
d = (12 * p * q) % MOD

answer = (a + b + c + d) % MOD

print(answer)

3. Code walkthrough

We convert the geometric recurrence into the simple rational recurrence

$$z_n=\frac{4z_{n-2}}{3z_{n-1}}.$$ 2. We represent $z_n$ as powers of $2$ and $3$:

$$z_n=\pm 2^{A_n}3^{B_n}.$$ 3. The exponent recurrences are affine linear:

$$A_n=A_{n-2}-A_{n-1}+2,$$

$$B_n=B_{n-2}-B_{n-1}-1.$$ 4. We compute $A_n,B_n$ modulo $M-1$ using fast matrix exponentiation. 5. Reconstruct modular versions of $p,q$. 6. Compute the rational coordinates in reduced form modulo $M$. 7. Sum numerator and denominator pieces.

Small verification

For $n=7$, the same method reproduces:

$$806236837,$$

exactly matching the problem statement.

4. Final verification

The recurrence reproduces all supplied sample points ($P_3,P_4,P_7$).
The $n=7$ checksum matches the official value.
Modular exponentiation is valid because $10^9+7$ is prime.
Fraction reductions for this parity class ($n$ odd, $n\equiv1\pmod3$) are trivial (gcd $=1$).

Answer: 92060460