Detailed mathematical approach

Problem Summary

The goal is to count lattice polygons whose edge lengths are integers and whose perimeter is at most \(N\). For the Project Euler target we need \(P(120)\). The code does not brute-force polygons directly; instead it builds them from admissible edge directions and uses dynamic programming on displacement and remaining perimeter.

Mathematical Approach

1. Which edge directions are allowed?

An edge vector \((x,y)\) has integer Euclidean length exactly when

$x^2+y^2=\ell^2$

for some integer \(\ell\). To avoid representing the same direction many times, the code keeps only primitive vectors

$\gcd(x,y)=1,$

and later allows any positive multiple \(g(x,y)\), whose length is \(g\ell\). Because no edge of a genuine polygon can exceed half the total perimeter, it is enough to generate primitive vectors with

$\ell \le \left\lfloor \frac{N-1}{2}\right\rfloor.$

2. Why directions are processed in polar-angle order

The primitive directions are sorted by angle \(\theta=\operatorname{atan2}(y,x)\). This gives a canonical way to describe a polygon boundary: after choosing a distinguished lowest vertex as the origin, the boundary edges can be read in nondecreasing angular order. Without this step, the same polygon could be generated many times from different cyclic starting points or different presentations of parallel edges.

3. DP state: current displacement and remaining perimeter

The state stored by the program is

$ (X,Y,r), $

where \((X,Y)\) is the current displacement from the chosen origin and \(r\) is the remaining perimeter budget. If we use the current primitive direction \((dx,dy)\) with primitive length \(\ell\) and multiplicity \(g\ge 1\), then the transition is

$ (X,Y,r)\longrightarrow (X+g\,dx,\;Y+g\,dy,\;r-g\ell). $

In other words, the DP is not guessing whole polygons at once; it is appending one angularly ordered edge block at a time.

4. The two pruning rules in the code

The transition is accepted only if two geometric filters hold.

Upper-half-plane rule. The code requires

$Y_{\text{new}}\ge 0.$

This chooses the lowest vertex of the polygon as the origin and forbids the partial walk from going below it. That gives one canonical representative instead of counting vertical translations or cyclic rotations of the same boundary.

Return-to-origin feasibility. The code also requires

$X_{\text{new}}^2+Y_{\text{new}}^2\le r_{\text{new}}^2.$

By the triangle inequality, if the Euclidean distance back to the origin already exceeds the remaining perimeter, closure is impossible. This single test removes a huge number of hopeless states.

5. Why returning to the origin is almost enough

After all directions have been processed, every state with displacement \((0,0)\) corresponds to a closed walk built from admissible integer-length edges. So the DP sums all states with origin key over every remaining budget level.

However, this raw count still includes two non-polygonal artifacts:

The empty walk. The initial state at the origin contributes one trivial closure and must be removed.

Two-edge backtracks. For any primitive direction of length \(\ell\), choosing an edge of length \(g\ell\) and then the opposite edge of the same length yields a closed degenerate segment of perimeter \(2g\ell\), not a genuine polygon. The code counts how many such objects exist via

$\sum_{\text{primitive }v}\left\lfloor\frac{N}{2\ell(v)}\right\rfloor,$

then divides by \(2\) because each direction and its opposite both appear in the vector list.

That is exactly why the final answer is computed as

$\text{answer}=\Bigl(\text{all closed states}\Bigr)-1-\text{diagonal}.$

6. Small checks

The implementation validates itself on

$P(4)=1,\qquad P(30)=3655,\qquad P(60)=891045.$

For \(N=4\), the only polygon is the unit square, so the first checkpoint is easy to visualize. The program then computes

$P(120)=3600060866.$

How the Code Works

The function init_vectors generates all primitive integer vectors with integer norm up to \((N-1)/2\), then sorts them by angle. The array arr[r] is a hash map of reachable displacements at remaining budget \(r\). It starts from the origin at budget \(N\). For each direction, the code tries every admissible multiplicity \(g\), applies the two pruning rules, and adds the resulting state into the hash map for the smaller remaining budget. Finally it sums all origin states and subtracts the empty path and the degenerate two-edge corrections.

Complexity Analysis

If \(V\) is the number of primitive directions and \(S_r\) is the number of reachable states at remaining budget \(r\), then the running time is roughly

$O\!\left(\sum_{v\in V}\sum_r S_r\,M_{v,r}\right),$

where \(M_{v,r}\) is the number of multiplicities \(g\) that still fit inside budget \(r\). Memory usage is the total size of the hash maps \(\texttt{arr}[0],\dots,\texttt{arr}[N]\). The essential gain comes from the geometric pruning, especially the distance-to-origin bound.

Further Reading

1. Problem page: https://projecteuler.net/problem=292
2. Pythagorean triples: https://en.wikipedia.org/wiki/Pythagorean_triple
3. Lattice polygons: https://en.wikipedia.org/wiki/Lattice_polygon