Admin: Create page with problem statement, approach using Pick's theorem, and link to Java solution (via create-page on MediaWiki MCP Server)

2026-06-16T23:33:20Z

Create page with problem statement, approach using Pick's theorem, and link to Java solution (via create-page on MediaWiki MCP Server)

New page

==Problem Statement==

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

<math>
A(a, 0), \quad B(0, b), \quad C(-c, 0), \quad D(0, -d)
</math>

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 [[wikipedia:Pick's theorem|Pick's Theorem]], which relates the area of a simple lattice polygon to the number of interior and boundary lattice points:

<math>
A = I + \frac{B}{2} - 1
</math>

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:

<math>
I = A - \frac{B}{2} + 1
</math>

===Area Calculation===

Using the [[wikipedia:Shoelace formula|shoelace formula]] with vertices in order $A \to B \to C \to D$:

<math>
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|
</math>

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

===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:

<math>
B = \gcd(a, b) + \gcd(b, c) + \gcd(c, d) + \gcd(d, a)
</math>

===Interior Points===

Substituting into Pick's Theorem:

<math>
I = \frac{(a + c)(b + d)}{2} - \frac{\gcd(a, b) + \gcd(b, c) + \gcd(c, d) + \gcd(d, a)}{2} + 1
</math>

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==

{{ProjectEulerFlag}}

Project Euler/504 - Revision history

Admin: Create page with problem statement, approach using Pick's theorem, and link to Java solution (via create-page on MediaWiki MCP Server)