Detailed mathematical approach

Problem Summary

Let

$G_{m,n}=\{0,1,\dots,m\}\times\{0,1,\dots,n\},\qquad N=(m+1)(n+1).$

We seek \(Q(m,n)\), the number of simple quadrilaterals whose four vertices are distinct lattice points of \(G_{m,n}\). The checkpoint values used by the implementations are

$Q(2,2)=94,\quad Q(3,7)=39590,\quad Q(12,3)=309000,\quad Q(123,45)=70542215894646.$

The actual target is \(Q(12345,6789)\bmod 135707531\).

Mathematical Approach

The solution does not enumerate quadruples directly. Instead it decomposes the problem into four global quantities: collinear triples, collinear quadruples, the total boundary-point count over all lattice triangles, and the total doubled-area count over all lattice triangles.

Step 1: Start from all 4-point sets

There are \(\binom{N}{4}\) ways to choose four lattice points. A set is immediately invalid if at least three of its points are collinear, because then no simple quadrilateral can use all four chosen vertices.

For a segment with displacement \((i,j)\), the number of lattice points on the segment equals \(\gcd(i,j)+1\). Therefore the number of interior lattice points on that segment is \(\gcd(i,j)-1\). This gcd rule is the basic ingredient behind the whole counting argument.

Step 2: Count collinear triples and quadruples by displacement class

Let \(\mathcal{D}\) be the set of all nonzero displacements \((i,j)\) with \(0\le i\le m\) and \(0\le j\le n\). For \((i,j)\in\mathcal{D}\), define

$g_{i,j}=\gcd(i,j),$

with the conventions \(\gcd(i,0)=i\) and \(\gcd(0,j)=j\). The number of segments having that displacement is

$M_{i,j}=\begin{cases} (n+1)(m+1-i), & j=0,\\ (m+1)(n+1-j), & i=0,\\ 2(m+1-i)(n+1-j), & i,j\ge 1. \end{cases}$

The factor \(2\) in the last case accounts for the two slopes \((i,j)\) and \((i,-j)\). Then

$L_3=\sum_{(i,j)\in\mathcal{D}} M_{i,j}\bigl(g_{i,j}-1\bigr),\qquad L_4=\sum_{(i,j)\in\mathcal{D}} M_{i,j}\binom{g_{i,j}-1}{2}.$

Each interior lattice point on a segment produces one collinear triple with the two endpoints, so \(L_3\) is exactly the number of collinear triples. Choosing two interior points on the same segment produces one collinear quadruple, so \(L_4\) is exactly the number of collinear quadruples.

If every collinear triple is extended by an arbitrary fourth point, we count \((N-3)L_3\) bad 4-point sets. A set of four collinear points contains four different triples, so it has been counted four times and must be corrected by subtracting \(3L_4\). Hence

$C_{\mathrm{bad}}=(N-3)L_3-3L_4.$

Step 3: Why triangle interior points matter

Now consider only 4-point sets with no three collinear. Such a set has exactly two possibilities:

1. The four points are in convex position, and there is exactly one simple quadrilateral.

2. One point lies strictly inside the triangle formed by the other three, and there are exactly three simple quadrilaterals.

So every nondegenerate 4-point set contributes \(1+2t\), where \(t\in\{0,1\}\) is the number of chosen points strictly inside the triangle formed by the other three. Summing over all 4-point sets gives

$Q(m,n)=\binom{N}{4}-C_{\mathrm{bad}}+2\Theta,$

where \(\Theta\) is the total number of pairs \((T,P)\) such that \(T\) is a nondegenerate lattice triangle and \(P\) is a lattice point strictly inside \(T\).

Step 4: Use Pick's theorem to convert \(\Theta\)

For any lattice triangle, Pick's theorem states

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

where \(A\) is the area, \(I\) the number of interior lattice points, and \(B\) the number of boundary lattice points. In doubled-area form this becomes

$2A=2I+B-2.$

Summing over all nondegenerate lattice triangles yields

$2\Theta=S_{\mathrm{A}}-S_{\mathrm{B}}+2T,$

where \(T=\binom{N}{3}-L_3\) is the number of nondegenerate triangles, \(S_{\mathrm{A}}\) is the total doubled area over all nondegenerate triangles, and \(S_{\mathrm{B}}\) is the total boundary-point sum over all nondegenerate triangles.

Step 5: Sum all boundary contributions

For a fixed segment, its contribution to the boundary-point count of every triangle using that segment is exactly \(\gcd(i,j)\). Therefore define

$S_{\mathrm{seg}}=\sum_{(i,j)\in\mathcal{D}} M_{i,j}g_{i,j}.$

If we multiply by \(N\), we temporarily pretend that every lattice point can serve as the third vertex. That overcounts points lying on the same maximal lattice line as the segment. If one such line contains \(k\) lattice points, then

$\sum_{\{A,B\}\subset \ell}\gcd\bigl(|x_B-x_A|,|y_B-y_A|\bigr)=\binom{k+1}{3},$

because pairs separated by \(r\) primitive steps contribute \(r\), and there are \(k-r\) such pairs. Therefore the forbidden same-line contribution of that line is \(k\binom{k+1}{3}\). Using

$k\binom{k+1}{3}=2\binom{k}{2}+6\binom{k}{3}+4\binom{k}{4},$

and summing over all maximal lattice lines, we obtain

$S_{\mathrm{B}}=N\,S_{\mathrm{seg}}-\left(2\binom{N}{2}+6L_3+4L_4\right).$

Step 6: Sum all doubled areas by bounding-box size

Every nondegenerate triangle has positive horizontal span and positive vertical span. Group triangles by the size \(i\times j\) of their minimal axis-aligned bounding box, where \(1\le i\le m\) and \(1\le j\le n\). Such a box can be translated in

$w(i,j)=(m+1-i)(n+1-j)$

different positions.

For a fixed box size, a direct inclusion-exclusion over all boundary placements of the three vertices simplifies to the exact-box doubled-area sum

$E(i,j)=\frac{i^2+j^2+11i^2j^2-\gcd(i,j)^2}{3}.$

This is always an integer. For example, \(E(1,1)=4\) and \(E(2,1)=16\), exactly matching direct enumeration in those boxes. Therefore

$S_{\mathrm{A}}=\sum_{i=1}^{m}\sum_{j=1}^{n} w(i,j)\,E(i,j).$

Step 7: Final closed formula and checkpoint

Substituting the previous pieces gives the formula implemented in all three languages:

$\boxed{Q(m,n)=\binom{N}{4}-\bigl((N-3)L_3-3L_4\bigr)+2\binom{N}{3}-2L_3+S_{\mathrm{A}}-S_{\mathrm{B}}.}$

For \(m=n=2\), we have \(N=9\), \(L_3=8\), \(L_4=0\), \(S_{\mathrm{A}}=140\), and \(S_{\mathrm{B}}=276\). Hence

$Q(2,2)=\binom{9}{4}-(6\cdot 8)+2\binom{9}{3}-2\cdot 8+140-276=94,$

which matches the published checkpoint exactly.

How the Code Works

The C++, Python, and Java implementations evaluate exactly these aggregated sums. They precompute the gcd-derived coefficients, handle horizontal and vertical segments separately, and run the main double loop over positive box widths and heights. The large target is evaluated modulo the prime \(135707531\), while the smaller checkpoints are also verified with exact integer arithmetic.

Complexity Analysis

The dominant work is the double sum over \(1\le i\le m\) and \(1\le j\le n\), so the running time is \(O(mn)\). The auxiliary tables for squares, multiplicities, and gcd-derived coefficients require \(O(m+n)\) memory. Splitting the outer loop across workers improves wall-clock time but does not change the asymptotic complexity.

References

1. Problem page: https://projecteuler.net/problem=453
2. Pick's theorem: Wikipedia — Pick's theorem
3. Lattice points on line segments: Wikipedia — Lattice point
4. Triangle area by determinant: Wikipedia — Shoelace formula
5. Inclusion-exclusion principle: Wikipedia — Inclusion-exclusion principle