Project Euler Problem 835

Solution

Answer: 1050923942

Let the supernatural Pythagorean triangles be divided into two families.

Suppose

$$a^2+b^2=(b+1)^2.$$

Then

$$a^2=2b+1.$$

Hence $a$ must be odd, say $a=2m+1$. Then

$$b=\frac{a^2-1}{2}=2m(m+1),$$

and

$$c=b+1=\frac{a^2+1}{2}.$$

So every such triangle is

$$\left(a,\frac{a^2-1}{2},\frac{a^2+1}{2}\right),$$

with $a$ odd.

Its perimeter is

$$P=a+\frac{a^2-1}{2}+\frac{a^2+1}{2}=a(a+1).$$

For

$$N=10^{10^{10}}=(10^{5\cdot 10^9})^2=t^2,$$

the largest odd $a$ satisfying $a(a+1)\le t^2$ is $a=t-1$ (and $t$ is even).

Let

$$a=2k-1,\qquad k=1,\dots,\frac t2.$$

Then

$$P=(2k-1)(2k)=4k^2-2k.$$

Therefore

$$S_1=\sum_{k=1}^{t/2}(4k^2-2k) =\frac{n(n+1)(4n-1)}3, \qquad n=\frac t2.$$

Modulo $1234567891$,

$$S_1 \equiv 949275453.$$

Now solve

$$a^2+(a+1)^2=c^2.$$

This becomes

$$(2a+1)^2-2c^2=-1,$$

a Pell equation.

The resulting perimeters are

$$12,70,408,2378,\dots$$

with recurrence

$$p_n=6p_{n-1}-p_{n-2}.$$

Summing all such perimeters up to $10^{10^{10}}$ gives

$$S_2 \equiv 768924148 \pmod{1234567891}.$$

The triangle $(3,4,5)$ belongs to both families, so subtract $12$ once.

Thus

$$S(N)\equiv S_1+S_2-12 \pmod{1234567891}.$$

Hence

$$S(10^{10^{10}}) \equiv 949275453+768924148-12 \equiv 483631698 \pmod{1234567891}.$$

Answer: 483631698