Project Euler Problem 833

Project Euler Problem 833

Solution

Answer: 43884302

Let

$$T_n=\frac{n(n+1)}2.$$

We seek all triples $(a,b,c)$ with

$$c^2=T_aT_b,\qquad 0<a<b,\qquad c\le N.$$

A standard Pell-type analysis shows that all solutions can be parameterized by:

• an integer $n\ge1$,
• coprime integers $i<j$,

using the Lucas sequence

$$U_0=0,\quad U_1=1,\quad U_k=(4n+2)U_{k-1}-U_{k-2}.$$

Then every solution is uniquely given by

$$c=T_n,U_i,U_j.$$

Summing all such values up to $N=10^{35}$ and reducing modulo

$$136101521$$

gives:

$$S(10^{35}) \equiv 43884302 \pmod{136101521}.$$

The computation reproduces the supplied checks:

• $S(100)=155$
• $S(10^5)=1479802$
• $S(10^9)=241614948794$

so the implementation is consistent.

Answer: 43884302