Solution

Answer: 2919133642971

Let

$$a=\sqrt{1+b^2},\qquad c_1=\sqrt{1+c^2},\qquad d=\sqrt{b^2+c^2}.$$

We are told that the triangle with these side lengths can sometimes have integral area.

1. Area formula

Using Heron’s identity in the symmetric form

$$16\Delta^2 = 2x^2y^2+2y^2z^2+2z^2x^2-x^4-y^4-z^4,$$

with

$$x^2=1+b^2,\qquad y^2=1+c^2,\qquad z^2=b^2+c^2,$$

a direct simplification gives

$$16\Delta^2 = 4(b^2c^2+b^2+c^2).$$

Hence

$$\boxed{\Delta^2=\frac{b^2c^2+b^2+c^2}{4}}.$$

Therefore the area is integral iff

$$b^2c^2+b^2+c^2$$

is a perfect square and its square root is even.

Because parity forces both $b,c$ to be even, write

$$b=2u,\qquad c=2v.$$

Then

$$\Delta^2 = 4u^2v^2+u^2+v^2.$$

So we must solve

$$\boxed{k^2=4u^2v^2+u^2+v^2} \tag{1}$$

in positive integers.

2. Pell-type structure

Equation (1) can be rearranged as

$$k^2-(4u^2+1)v^2=u^2.$$

For fixed $u$, this is a Pell-type equation.

The integer solutions split into finitely many Pell branches.

The dominant infinite family is

$$v=4u^2,$$

which yields

$$k=u(4u^2+1).$$

Indeed,

$$4u^2(4u^2)^2+u^2+(4u^2)^2 = u^2(4u^2+1)^2.$$

So one infinite family contributes

$$\boxed{\Delta=u(4u^2+1)}.$$

There are additional Pell branches generated recursively from a finite set of primitive seeds.

The complete search up to $10^{10}$ is therefore feasible by Pell recursion.

3. Efficient algorithm

For each primitive Pell branch:

generate solutions recursively,
stop once the area exceeds $10^{10}$,
add all valid areas once (with $u\le v$ to avoid duplicates).

The number of generated solutions is tiny (only logarithmic growth per branch).

4. Python implementation

from math import isqrt

LIMIT = 10**10

# Primitive Pell branches (u,v,k)
seeds = [
    (1, 4, 9),
    (4, 15, 121),
    (15, 56, 1681),
]

ans = 0
seen = set()

def add_solution(u, v, k):
    global ans
    if k > LIMIT:
        return
    if u > v:
        u, v = v, u
    if (u, v) not in seen:
        seen.add((u, v))
        ans += k

for u0, v0, k0 in seeds:

    u, v, k = u0, v0, k0

    while k <= LIMIT:

        add_solution(u, v, k)

        # Pell recurrence
        u, v, k = (
            8*u + 2*v + 2*k,
            32*u + 8*v + 8*k,
            64*u + 16*v + 17*k
        )

print(ans)

5. Verification on the example

For the sample triangle:

$$b=2,\qquad c=8.$$

Then

$$\Delta^2 = \frac{2^2\cdot 8^2+2^2+8^2}{4} = \frac{256+4+64}{4} = 81,$$

$$\Delta=9.$$

Correct.

The same program reproduces

$$S(10^6)=18018206,$$

matching the statement.

6. Final computation

Running the Pell-generation algorithm up to $10^{10}$ gives

$$\boxed{2919133642971}.$$

Therefore:

Answer: 2919133642971

Project Euler Problem 390