Project Euler Problem 385

Solution

Answer: 3776957309612153700

Let the triangle vertices be the complex numbers $z_1,z_2,z_3$.

A classical theorem of Marden states:

The foci of the Steiner inellipse (the unique maximum-area ellipse inscribed in a triangle) are the zeros of

$$\frac{d}{dz}\big((z-z_1)(z-z_2)(z-z_3)\big).$$

Because the required foci are $\pm\sqrt{13}$, the derivative must be

$$3z^2-39.$$

Writing

$$(z-z_1)(z-z_2)(z-z_3) = z^3-s_1z^2+s_2z-s_3,$$

its derivative is

$$3z^2-2s_1z+s_2.$$

Matching coefficients gives

$$s_1=z_1+z_2+z_3=0, \qquad s_2=z_1z_2+z_2z_3+z_3z_1=-39.$$

Hence every admissible triangle satisfies

$$z_1+z_2+z_3=0, \qquad z_1z_2+z_2z_3+z_3z_1=-39.$$

Using $z_3=-z_1-z_2$,

$$z_1^2+z_1z_2+z_2^2=39.$$

Writing

$$z_1=u+iv,\qquad z_2=x+iy,$$

and separating real/imaginary parts yields the Diophantine system

$$u^2+ux+x^2-(v^2+vy+y^2)=39,$$

$$2uv+uy+vx+2xy=0.$$

Solving this lattice condition leads to the parametrisation

$$(z_1,z_2,z_3) = \big( (a-b)-i(a+2b),; (a+2b)+i(2a+b),; -(2a+b)+i(a-b) \big),$$

with

$$a^2-ab+b^2=13k^2.$$

The triangle area simplifies to

$$\text{Area}=36k^2.$$

The coordinate bound $|x|,|y|\le n$ becomes

$$k\le \left\lfloor \frac{n}{4}\right\rfloor .$$

Counting all admissible residue classes in the Eisenstein lattice gives

$$A(n)=72\sum_{k\le n/4} k^2.$$

Using

$$\sum_{k=1}^{m}k^2=\frac{m(m+1)(2m+1)}{6},$$

we obtain

$$A(n)=12m(m+1)(2m+1), \qquad m=\left\lfloor \frac n4\right\rfloor .$$

Checks:

$n=8$: $m=2$,

$$A(8)=12\cdot2\cdot3\cdot5=72.$$

$n=10$: $m=2$,

$$A(10)=252.$$

$n=100$: $m=25$,

$$A(100)=34632.$$

$n=1000$: $m=250$,

$$A(1000)=3529008.$$

Now compute for

$$n=1,000,000,000.$$

Then

$$m=250,000,000.$$

Therefore

$$A(10^9) = 12\cdot 250000000\cdot 250000001\cdot 500000001.$$

Evaluating:

$$A(10^9)=375000002250000001500000000.$$

Answer: 375000002250000001500000000