Project Euler/504

Problem Statement

Let $ABCD$ be a quadrilateral whose vertices are lattice points lying on the coordinate axes as follows:

$A(a, 0), \quad B(0, b), \quad C(-c, 0), \quad D(0, -d)$

where $1 \le a, b, c, d \le m$ and $a, b, c, d, m$ are integers.

It can be shown that for $m = 4$ there are exactly $256$ valid ways to construct $ABCD$. Of these $256$ quadrilaterals, $42$ of them strictly contain a square number of lattice points.

How many quadrilaterals $ABCD$ strictly contain a square number of lattice points for $m = 100$?

Approach

Pick's Theorem

The core of the solution is Pick's Theorem, which relates the area of a simple lattice polygon to the number of interior and boundary lattice points:

$A = I + \frac{B}{2} - 1$

where:

$A$ is the area of the polygon
$I$ is the number of interior lattice points (those strictly inside the polygon)
$B$ is the number of boundary lattice points (those on the edges or vertices)

Rearranging to solve for interior points:

$I = A - \frac{B}{2} + 1$

Area Calculation

Using the shoelace formula with vertices in order $A \to B \to C \to D$:

$A = \frac{1}{2} \left| (a \cdot b + 0 \cdot 0 + (-c) \cdot (-d) + 0 \cdot 0) - (0 \cdot 0 + b \cdot (-c) + 0 \cdot 0 + (-d) \cdot a) \right|$

$A = \frac{1}{2} \left| ab + cd + bc + ad \right| = \frac{(a + c)(b + d)}{2}$

Boundary Points

The number of lattice points on a line segment between two lattice points $(x_1, y_1)$ and $(x_2, y_2)$ is $\gcd(|x_2 - x_1|, |y_2 - y_1|) + 1$ (including both endpoints). For the four edges:

Edge $AB$: $\gcd(a, b) + 1$ points
Edge $BC$: $\gcd(b, c) + 1$ points
Edge $CD$: $\gcd(c, d) + 1$ points
Edge $DA$: $\gcd(d, a) + 1$ points

Summing these and subtracting the 4 vertices (counted twice) gives the total boundary count:

$B = \gcd(a, b) + \gcd(b, c) + \gcd(c, d) + \gcd(d, a)$

Interior Points

Substituting into Pick's Theorem:

$I = \frac{(a + c)(b + d)}{2} - \frac{\gcd(a, b) + \gcd(b, c) + \gcd(c, d) + \gcd(d, a)}{2} + 1$

Since $(a + c)(b + d)$ is always even for this quadrilateral, integer division by 2 is exact.

Algorithm

Pre-compute a GCD table for all pairs of values from $1$ to $m$ using the Euclidean algorithm. Then iterate over all quadruples $(a, b, c, d)$ with $1 \le a, b, c, d \le m$:

Compute the area term: $\mathtt{area} = (a + c) \times (b + d)$
Compute the boundary term by summing four GCD table lookups
Calculate interior points: $I = \mathtt{area}/2 - \mathtt{boundary}/2 + 1$
Check if $I$ is a perfect square by computing its integer square root and squaring it

Count all quadruples where $I$ is a perfect square.

Complexity

The quadruple nested loop runs in $O(m^4)$ time. Pre-computing the GCD table takes $O(m^2 \log \max(a,b))$ time. For $m = 100$, the total number of quadruples is $100^4 = 100{,}000{,}000$, which is feasible in Java with efficient inner-loop operations.

Solution

Link: https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem504.java

Flags