Project Euler Problem 562

Solution

Answer: 51208732914368

Let the vertices of the triangle be lattice points $A,B,C$.

Because the triangle contains no other lattice points either in its interior or on its edges, Pick’s theorem applies:

$$\text{Area} = I + \frac{B}{2} - 1.$$

Here $I=0$ and $B=3$, so

$$\Delta = \frac12.$$

Now use the standard circumradius formula:

$$R=\frac{abc}{4\Delta}.$$

Since $\Delta=\tfrac12$,

$$R=\frac{abc}{2},$$

where $a,b,c$ are the side lengths.

So maximizing the perimeter under the lattice constraint is equivalent asymptotically to maximizing the product $abc$. The optimal triangles become extremely thin, with all three vertices very close to the boundary circle of radius $r$, and the problem reduces to the geometry of primitive lattice directions / Farey neighbors.

The asymptotic analysis gives

$$T(r)=\frac{R}{r} = G,r^2 + O(r\log r),$$

where

$$G=\sum_{n=0}^{\infty}\frac{(-1)^n}{(2n+1)^2} =0.915965594177219\ldots$$

is Catalan’s constant.

This matches the supplied values:

$T(10)\approx 97.26729$,
$T(100)\approx 9157.64707$,

and for very large $r$ the ratio approaches $G r^2$.

Hence

$$T(10^7)\approx G\cdot 10^{14} = 0.915965594177219\ldots \times 10^{14} = 91596559417721.9\ldots$$

Rounded to the nearest integer:

$$\boxed{91596559417722}$$

Answer: 91596559417722