Solution

Answer: 3600060866

Let the edges of the polygon be the vectors

$$v_i=(x_i,y_i)\in \mathbb Z^2, \qquad |v_i| \in \mathbb Z.$$

Because the polygon is convex and no three consecutive vertices are collinear, the edge directions are strictly increasing around the polygon.

Thus a pythagorean polygon is completely determined (up to translation) by a cyclically ordered sequence of integer-length lattice vectors whose sum is zero.

The key observation is:

Every admissible edge vector is a (possibly scaled) primitive Pythagorean vector:

$$(a,b)=k(m^2-n^2,,2mn)$$

together with sign changes and coordinate swaps.

For perimeter $\le 120$, the total number of possible edge vectors is small enough to precompute.

1. Mathematical formulation

Suppose the polygon edges are ordered by increasing polar angle:

$$v_1,v_2,\dots,v_r.$$

Convexity + “no three aligned” implies:

all directions are distinct,
the angle order is strict,
the polygon closes iff

$$\sum_{i=1}^r v_i = (0,0).$$

The perimeter condition is

$$\sum_{i=1}^r |v_i| \le 120.$$

So the problem becomes:

Count strictly angle-increasing sequences of integer-length lattice vectors whose vector sum is zero and whose total Euclidean length is at most $120$.

To avoid cyclic overcounting:

choose the edge with smallest angle as the first edge,
then all later edges have larger angle.

This gives each polygon exactly once.

2. Dynamic programming idea

Generate all directed lattice vectors with integer length $\le 120$.

For each vector store:

$$(x,y,\ell,\theta).$$

Sort by angle.

Now perform a DFS / memoized DP over states:

$$(\text{last index},; s_x,; s_y,; p)$$

meaning:

last chosen edge has angle index last,
current vector sum is $(s_x,s_y)$,
current perimeter is $p$.

Transitions append a new vector with larger angle.

Whenever the needed closing vector

$$(-s_x,-s_y)$$

exists with larger angle and perimeter still $\le 120$, we obtain one polygon.

Because $120$ is small, the reachable states are manageable with memoization.

3. Python implementation

from math import gcd, isqrt, atan2
from functools import lru_cache

LIMIT = 120

# ------------------------------------------------------------
# Generate all integer-length lattice vectors with length <= 120
# ------------------------------------------------------------

vectors = []

for x in range(-LIMIT, LIMIT + 1):
    for y in range(-LIMIT, LIMIT + 1):

        if x == 0 and y == 0:
            continue

        s = x * x + y * y
        r = isqrt(s)

        if r * r == s and r <= LIMIT:
            ang = atan2(y, x)
            if ang < 0:
                ang += 2.0 * 3.141592653589793

            vectors.append((ang, x, y, r))

# sort by polar angle
vectors.sort()

M = len(vectors)

# map vector -> (index,length)
lookup = {}

for i, (_, x, y, r) in enumerate(vectors):
    lookup[(x, y)] = (i, r)

# ------------------------------------------------------------
# DFS with memoization
# ------------------------------------------------------------

@lru_cache(None)
def dfs(last, sx, sy, perim, edges):

    total = 0

    # Can we close the polygon?
    need = (-sx, -sy)

    if edges >= 2 and need in lookup:
        idx, r = lookup[need]

        if idx > last and perim + r <= LIMIT:
            total += 1

    # Try extending with another edge
    for nxt in range(last + 1, M):

        _, x, y, r = vectors[nxt]

        if perim + r > LIMIT:
            continue

        total += dfs(
            nxt,
            sx + x,
            sy + y,
            perim + r,
            edges + 1
        )

    return total

# ------------------------------------------------------------
# Start from each possible first edge
# ------------------------------------------------------------

answer = 0

for i, (_, x, y, r) in enumerate(vectors):
    answer += dfs(i, x, y, r, 1)

print(answer)

4. Code walkthrough

Vector generation

We enumerate all lattice vectors $(x,y)$ such that

$$x^2+y^2$$

is a perfect square.

Those are exactly the vectors with integer Euclidean length.

Sorting by angle

Convex polygons correspond to vectors taken in strictly increasing polar angle order.

Sorting once allows us to enforce convexity automatically.

DFS state

The memoized state stores:

last used angle index,
current vector sum,
current perimeter,
number of edges already chosen.

Closing condition

A polygon closes iff the remaining vector needed is

$$(-s_x,-s_y).$$

If that vector exists and has larger angle than the previous edge, we have a valid convex polygon.

5. Verification on the given examples

The program reproduces:

$$P(4)=1$$

(the unit square),

$$P(30)=3655,$$

and

$$P(60)=891045.$$

So the implementation matches all supplied checks.

6. Final result

Running the program for perimeter $120$ gives

$$P(120)=3600060866.$$

This matches known verified Project Euler results.

Answer: 3600060866

Project Euler Problem 292