Integer lattice

The integer lattice $\mathbb{Z}^n$ is the set of points whose coordinates are all integers. It is the most natural place a geometry question can live on a computer: no rounding, no tolerance, every coordinate an exact int. That is why Project Euler keeps returning to it. Put a circle, a triangle or a parabola on the grid and ask how many lattice points it touches, and a continuous question becomes a counting question, which you can answer exactly. The problems below vary a great deal on the surface, from right triangles and tilted rectangles to hyperballs, tangent ellipses, hexagonal orchards and chess pieces. Underneath, they lean on a short list of facts about the grid, and this page is about those facts.

Three facts the grid gives you for free

1. Directions are fractions, and the gcd reduces them. A step $(a, b)$ between two lattice points has a primitive version $(a/g, b/g)$ with $g = \gcd(a, b)$, the shortest lattice step pointing the same way. The segment from $(0,0)$ to $(a,b)$ passes through exactly $g + 1$ lattice points, and $(a, b)$ is "visible" from the origin, with nothing in the way, exactly when $g = 1$. Nearly every direction-sensitive question on the grid comes down to the greatest common divisor. Problem 91 is the cleanest public example. To place a right angle at $P = (x, y)$, the perpendicular step has to be the primitive vector $(-y/m,\ x/m)$ with $m = \gcd(x, y)$, and the number of lattice points reachable along it before you leave the square is a plain integer division:

min(x * m // y, m * (coordinate_limit - y) // x)   # for m = gcd(x, y)

The gcd is what makes both divisions exact. A floating-point slope would get the same answer most of the time and the wrong one on exactly the cases that matter.

Counting distinct directions, as opposed to points, means counting primitive vectors, and the standard tool is Möbius inversion. Count every vector, then subtract the ones whose coordinates share a factor $d$: $\#\text{primitive} = \sum_d \mu(d)\,\#\{\text{vectors in the region scaled down by } d\}$. This is also where the familiar density $6/\pi^2$ of coprime pairs comes from. Problem 388 (distinct lines through the origin in a cube) and Problem 351 (points hidden from the centre of a hexagonal orchard) are both this sum. Problems 184 and 478 use the same fact in a different role: they group lattice points by primitive ray, so that an angular sweep can deal with collinear points as a whole group instead of tripping over ties.

The same gcd counts collinear triples, and Problem 994 shows how far that goes. Its picture is a fan of segments joining two rows of points, and three segments that meet pairwise fail to make a triangle when all three meet in one point: a shared endpoint, or a common crossing inside. Under projective duality, lines through a common point become points on a common line, so the segment $(i, j)$ becomes the cell $(i, j)$ of an $m \times n$ index grid, and the defect is the number of collinear lattice triples in that box. Fix the two outer points at offset $(a, b)$. There are $\gcd(a, b) - 1$ lattice points strictly between them, so the count is $\sum (m-a)(n-b)\bigl(\gcd(a,b) - 1\bigr)$. With $m$ and $n$ near $10^{11}$ you cannot loop over offsets. But $\gcd(a,b) = \sum_{d \mid a,\ d \mid b} \varphi(d)$ (Euler's totient) separates the coordinates: the sum becomes $\sum_d \varphi(d)\,F(d)\,G(d)$, where $F$ depends only on $m$ and $G$ only on $n$. That is a sum over floor-quotient blocks, finished in sublinear time by the totient summatory recursion.

2. Points in a region are a sum over columns; points on a curve are a number-theory function. The number of lattice points inside the disc $x^2 + y^2 \le r^2$ is $\sum_{x=-r}^{r} \bigl(2\lfloor\sqrt{r^2 - x^2}\rfloor + 1\bigr)$. That is one exact integer square root per column, $O(r)$ work for a count that grows like $\pi r^2$. The error term is the Gauss circle problem, and the same column-by-column idea counts the points under a parabola (Problem 403) or inside an ellipse (Problem 229). In four dimensions (Problem 596) slicing no longer scales, and the count turns into a divisor sum through Jacobi's four-square theorem, which is the move described next for circles, two dimensions up. The points on a circle are a different kind of question. $x^2 + y^2 = n$ has $r_2(n) = 4\bigl(d_1(n) - d_3(n)\bigr)$ solutions by Jacobi's two-square theorem, where $d_k(n)$ counts the divisors of $n$ that are $k \bmod 4$. So "how many lattice points lie on this circle?" becomes "how is the squared radius factored?". Problem 233 is that translation and nothing else; the geometry disappears once you have written the equation down. More general shapes $a x^2 + b xy + c y^2 = n$ lead to binary quadratic forms.

Summing over $n$ turns the second question back into the first. If $g(n)$ counts the solutions of $Q(x, y) = n$, then $\sum_{n \le N} g(n)$ counts each lattice point with $0 < Q(x, y) \le N$ exactly once: it is the number of points inside an ellipse. Problem 804 asks for that sum with $Q = x^2 + xy + 41y^2$ and $N = 10^{16}$, and never needs a single $g(n)$. Completing the square gives $4Q = (2x + y)^2 + 163y^2$, so each row $y$ is a symmetric interval of $u = 2x + y$, one integer square root per row. The substitution is not unimodular, so only the $u$ with the parity of $y$ map back to lattice points (the parity check from the next section). The ellipse's area, $2\pi N/\sqrt{163}$, predicts the leading digits before you run anything.

When the curve is a conic and one rational point on it is known, there is a third way to reach its points: parametrise them. Every line through the known point with rational slope $\beta/\alpha$ meets the conic in exactly one more rational point. Clearing denominators then lists the primitive integer solutions, one per reduced slope, which is where Pythagorean triples come from. In Problem 962, "this length is an integer" reduces, after the gcds and square-free parts are split off, to $g^2 - w^2 = D m^2$. The line through $(1 : 1 : 0)$ turns a search for perfect squares among $10^{10}$ triangles into a loop over slopes, and each slope contributes a whole family of multiples in one step. Fact 1 is back here as well: the gcd of the three coordinates depends only on $\gcd(\alpha, D)$ and the parity of $\alpha$, so the admissible slopes can be counted by Möbius inclusion–exclusion instead of walked.

Problem 983 uses the same count in a different role. It doesn't ask for the count; it uses it as a budget. Equal circles of radius $\sqrt{N}$ centred on lattice points meet at two lattice points exactly when the difference of their centres is $u + v$ for two distinct norm-$N$ vectors $u \ne \pm v$, and the crossing points are then $c + u$ and $c + v$. So the solutions of $x^2 + y^2 = N$ act as the alphabet the whole configuration is built from. Because the lattice is a group, every centre and every crossing point is a signed sum of letters from that alphabet. The problem's large configurations turn out to be hypercubes projected into the plane: pick $K$ norm-$N$ vectors and take every subset sum. A $K$-cube needs $K$ distinct $\pm$ classes, which is $r_2(N)/2$, so the two-square formula throws out most radii before any search starts. That is cheap checks first. What remains is a question about which signed sums $\sum \delta_i a_i$, $\delta \in \{-1, 0, 1\}^K$, collide or land somewhere they shouldn't.

3. Area is exact, and Pick's theorem ties it to the count. The signed area of a lattice polygon is half an integer, given by the cross product (the shoelace formula), with no division and no square root. Pick's theorem, $A = I + B/2 - 1$, links that area to the number of interior points $I$ and boundary points $B$, and $B$ is a sum of edge gcds by fact 1. So if you know the vertices, you can count every lattice point inside a polygon without enumerating any of them. Problems 742 (minimum-area convex grid polygons) and 453 (simple lattice quadrilaterals) live in this territory, where area, convexity and lattice-point counts all come out of determinants.

Moving onto the lattice

Many of these problems don't start on $\mathbb{Z}^n$. Part of the work is choosing coordinates that put them there, and the rule is to pick a map that sends lattice points to lattice points in both directions:

  • Translate to a lattice-point centre. Problem 246's ellipse is centred at an integer point, so shifting it to the origin is a bijection on the grid and the equation loses its linear terms.
  • Scale away the halves. Problem 147 doubles every coordinate so that the cross-hatch's cell centres and edge midpoints become integer points. Problem 233 writes $u = 2x - N$ so that a circle with centre $(N/2, N/2)$ becomes $u^2 + v^2 = 2N^2$. In both cases you then have to check that only the right parity class maps back to the original lattice.
  • Apply an affine map that sends the problem's natural frame to the standard one. Problem 478 maps the mixture simplex onto the plane with the target at the origin. The hexagonal orchard is the triangular lattice, which is $\mathbb{Z}^2$ under a shear, so the gcd and Möbius machinery carries straight over.

A map with integer entries and determinant $\pm 1$ (a unimodular map) keeps the lattice exactly, so counts, gcds and areas all survive the change. Problem 507 asks for the shortest vector of a two-dimensional sub-lattice of $\mathbb{Z}^3$. That is lattice reduction: a sequence of unimodular basis changes (the Lagrange–Gauss step in two dimensions) that never changes which points are in the lattice, only how short the basis vectors are.

Sometimes the lattice is more than a group: it is a ring. $\mathbb{Z}^2$ is the Gaussian integers $\mathbb{Z}[i]$, and the hexagonal lattice is the Eisenstein integers $\mathbb{Z}[\omega]$, whose squared length is the norm $a^2 - ab + b^2$. In a ring, rotating and scaling a lattice vector is a multiplication, so you can see at once which directions are lattice directions. Problem 883 asks for hexagonal-lattice triangles with a $60^\circ$ angle whose incentre is also a lattice point. Pinning the incentre at the origin removes translations, leaving one representative per class. The two sides at the $60^\circ$ vertex $\alpha$ run $30^\circ$ either side of $-\alpha$, and multiplying by $1 - \omega = \sqrt{3}\,e^{-i\pi/6}$ is exactly that rotation, so both sides are lattice directions for every $\alpha$. What is left is a divisor count on the content of $\alpha(1 - \omega)$, the largest integer dividing it, which is the ring's version of the gcd in fact 1. The Möbius grouping over primitive points then carries over with one twist: the prime $1 - \omega$ lying over 3 has to be split out separately, and it turns into an alternating series over $Y/3^j$.

A few of the tagged problems (331, 289, 763, 790) use the grid mostly as a board, cells with neighbours, and the lattice structure there is just indexing. The habits below still apply to them, but the three facts do the heavy lifting elsewhere.

When the count is a polynomial in N

Some lattice counts need no number theory at all, because each object being counted is described by a fixed number of integer parameters, each bounded linearly in $N$. The lattice points of a polytope scaled by $N$ are counted by a polynomial in $N$ (Ehrhart's theorem), or by a quasi-polynomial, one polynomial per residue class of $N$, when the vertices are rational rather than integral. The practical move is to establish that the count has this shape, compute enough exact small values, and interpolate.

Problem 984 is the clearest case. The sets it counts look combinatorial: knight-connected, and closed under the blocking rule of the Chinese-chess horse. An exhaustive search of the $5 \times 5$ board shows that every one of them is a lattice octagon, the squares cut out by lower and upper bounds on the four forms $r$, $c$, $r + c$ and $r - c$. An octagon on the board is fixed by eight numbers (box size, position, four corner cuts), so the count is a degree-8 quasi-polynomial, one polynomial for each parity of $N$, and ten exact values per parity carry it to $N = 10^{18}$. That is small cases reveal the closed form, with the lattice telling you the degree in advance.

The same octagons drive Problem 968 from the other side. Its constraints $x_i + x_j \le X_{ij}$ on five non-negative variables cut out a polytope of about $10^{40}$ points, each weighted by a product of prime powers. Constraints of the form $\pm x_i \pm x_j \le k$ are octagonal, and the class is closed under projection. Summing one variable out is a geometric series between its tightest lower and upper bounds, and the case split on which bound is tightest leaves only octagonal constraints on the variables that remain. That is Fourier–Motzkin elimination applied to a weighted sum. Five eliminations reach a closed form whose cost does not depend on the size of the bounds at all.

How to reason about it

  • Stay in integers on purpose. Lattice inputs produce exact ties: collinear triples, points exactly on the boundary, rays that share a direction. Floating point turns each of those into a coin toss. Use math.isqrt, the gcd and the cross product, and compare squared lengths rather than lengths. See computational geometry for how much of the work is getting the boundary cases right. When the coordinates are bounded, you can also pack a vector into one integer with a linear key such as $x \cdot 2^{21} + y$. Then the sum of two vectors is the sum of their keys, so a set of lattice points becomes a hash set or a sorted array of ints. Problem 983 tests tens of thousands of signed sums for membership this way.
  • Read the boundary convention as part of the problem. "Strictly inside" versus "on or inside" changes $I$ versus $I + B$ in Pick's formula, and changes the $\le$ in every column count. Decide it once and make every predicate follow it.
  • Use symmetry, then put the axes back. The disc, the square and the ellipse have four-fold or eight-fold symmetry, so count one octant and multiply, then add back the points on the axes and diagonals separately, since multiplying counts them more than once. That is exploit symmetry, and most off-by-a-few errors here come from it.
  • Ask whether the count is a number-theory function. If the question is about points on a curve or along a direction, there is usually a divisor-sum or Möbius formula behind it, and enumerating the points is the slow path. That is reduce before coding in its lattice form: a problem that asks about $10^{10}$ or $10^{12}$ is telling you the answer is a sum over divisors, not over points. If the question has no number-theoretic structure but its objects have a fixed number of linearly bounded parameters, the answer is a (quasi-)polynomial in $N$ instead.
  • Eliminate from the closure, not from the original constraints. When you sum a variable out of a region and prune the bounds that can never be tightest, a bound that is redundant for one variable can still be the only cap on another. Problem 968's first version dropped such a bound and summed over far too large a range. Rebuilding the child region from the tight closure's projection keeps every consequence, and a randomised check against direct enumeration is what found the bug.
  • Brute-force the small case. Every problem here ships small worked values. A triple loop over a $10 \times 10$ grid is the reference that catches a missing axis point or a gcd that should have been a gcd minus one. Brute force can also tell you what shape to search for, not just check the answer. The hypercube picture in Problem 983 is a conjecture until an exhaustive search at the smallest radius finds that every perfect set there has exactly a cube's size. That is calibrate theory on known answers.

Problems15 / 50

  • ● 0091 — Right Triangles with Integer Coordinates
  • ● 0147 — Rectangles in Cross-hatched Grids
  • ● 0184 — Triangles Containing the Origin
  • ● 0229 — Four Representations Using Squares
  • ● 0233 — Lattice Points on a Circle
  • ● 0246 — Tangents to an Ellipse
  • ○ 0264 — Triangle Centres
  • ○ 0270 — Cutting Squares
  • ○ 0279 — Triangles with Integral Sides and an Integral Angle
  • ○ 0283 — Integer Sided Triangles with Integral Area/perimeter Ratio
  • ○ 0289 — Eulerian Cycles
  • ○ 0292 — Pythagorean Polygons
  • ○ 0295 — Lenticular Holes
  • ○ 0296 — Angular Bisector and Tangent
  • ○ 0299 — Three Similar Triangles
  • ● 0331 — Cross Flips
  • ○ 0332 — Spherical Triangles
  • ○ 0353 — Risky Moon
  • ○ 0360 — Scary Sphere
  • ○ 0373 — Circumscribed Circles
  • ○ 0385 — Ellipses Inside Triangles
  • ○ 0388 — Distinct Lines
  • ○ 0403 — Lattice Points Enclosed by Parabola and Line
  • ○ 0415 — Titanic Sets
  • ○ 0450 — Hypocycloid and Lattice Points
  • ○ 0453 — Lattice Quadrilaterals
  • ○ 0465 — Polar Polygons
  • ● 0478 — Mixtures
  • ○ 0507 — Shortest Lattice Vector
  • ○ 0514 — Geoboard Shapes
  • ○ 0562 — Maximal Perimeter
  • ○ 0577 — Counting Hexagons
  • ○ 0579 — Lattice Points in Lattice Cubes
  • ○ 0596 — Number of Lattice Points in a Hyperball
  • ○ 0604 — Convex Path in Square
  • ○ 0662 — Fibonacci Paths
  • ○ 0664 — An Infinite Game
  • ○ 0723 — Pythagorean Quadrilaterals
  • ○ 0736 — Paths to Equality
  • ○ 0742 — Minimum Area of a Convex Grid Polygon
  • ○ 0763 — Amoebas in a 3D Grid
  • ○ 0790 — Clock Grid
  • ● 0804 — Counting Binary Quadratic Representations
  • ○ 0879 — Touch-screen Password
  • ● 0883 — Remarkable Triangles
  • ● 0962 — Angular Bisector and Tangent 2
  • ● 0968 — 5D Summation
  • ● 0983 — Consonant Circle Crossing
  • ● 0984 — Knights and Horses
  • ● 0994 — Counting Triangles