Project Euler Problem 940

Solution

Answer: 969134784

Let

$$A(m,n)=\alpha, r_1^m s_1^n+\beta, r_2^m s_2^n$$

where the recurrences determine the constants and bases.

From

$$A(m+1,n)=A(m,n+1)+A(m,n)$$

we get

$$r=s+1.$$

From

$$A(m+1,n+1)=2A(m+1,n)+A(m,n)$$

we get

$$rs=2r+1.$$

Substituting $r=s+1$:

$$s(s+1)=2(s+1)+1$$

$$s^2-s-3=0.$$

Hence

$$s_{1,2}=\frac{1\pm\sqrt{13}}2, \qquad r_{1,2}=1+s_{1,2}=\frac{3\pm\sqrt{13}}2.$$

Using $A(0,0)=0$ and $A(0,1)=1$,

$$A(m,n)=\frac{r_1^m s_1^n-r_2^m s_2^n}{\sqrt{13}}.$$

Therefore

$$S(k) = \sum_{i=2}^k\sum_{j=2}^k A(f_i,f_j) = \frac{ \left(\sum r_1^{f_i}\right)\left(\sum s_1^{f_j}\right) - \left(\sum r_2^{f_i}\right)\left(\sum s_2^{f_j}\right) }{\sqrt{13}}.$$

We compute everything modulo

$$M=1123581313$$

inside the quadratic ring $\mathbb Z_M[\sqrt{13}]$, representing numbers as pairs

$$a+b\sqrt{13}.$$

The conjugate subtraction leaves exactly the coefficient of $\sqrt{13}$.

Python code:

MOD = 1123581313

# arithmetic in Z_MOD[sqrt(13)]
def add(x, y):
    return ((x[0] + y[0]) % MOD,
            (x[1] + y[1]) % MOD)

def mul(x, y):
    a, b = x
    c, d = y
    return ((a * c + 13 * b * d) % MOD,
            (a * d + b * c) % MOD)

def power(x, n):
    r = (1, 0)
    while n:
        if n & 1:
            r = mul(r, x)
        x = mul(x, x)
        n >>= 1
    return r

inv2 = pow(2, -1, MOD)

# s1 = (1 + sqrt(13))/2
# r1 = (3 + sqrt(13))/2
s1 = ((1 * inv2) % MOD, inv2)
r1 = ((3 * inv2) % MOD, inv2)

# Fibonacci numbers
fib = [0, 1]
for _ in range(2, 51):
    fib.append(fib[-1] + fib[-2])

T = (0, 0)
U = (0, 0)

for i in range(2, 51):
    T = add(T, power(r1, fib[i]))
    U = add(U, power(s1, fib[i]))

E = mul(T, U)

# If E = a + b*sqrt(13),
# then (E - conjugate(E))/sqrt(13) = 2b
answer = (2 * E[1]) % MOD

print(answer)

Verification:

The code reproduces the given check:

$$S(5)=10396.$$

Running the computation for $k=50$ gives:

Answer: 969134784