Detailed mathematical approach

Problem Summary

Let \(H(n)\) denote the number of convex equiangular hexagons with integer side lengths and perimeter at most \(n\), where two hexagons are identified when they are congruent. The checkpoints \(H(6)=1\), \(H(12)=10\), and \(H(100)=31248\) show that the count grows quickly, so direct enumeration of all side sextuples is not practical.

The key observation is that an equiangular hexagon is determined by its six side lengths once the six edge directions are fixed. That turns the geometric problem into a counting problem on positive integer 6-tuples, followed by a quotient by the symmetries of a hexagon.

Mathematical Approach

Write the side lengths in cyclic order as \((a,b,c,d,e,f)\). Because each exterior turn is \(60^\circ\), the edge directions are \(0^\circ,60^\circ,120^\circ,180^\circ,240^\circ,300^\circ\). Summing the six edge vectors and forcing the polygon to close produces the arithmetic structure used by the solution.

Step 1: Convert Geometric Closure into Two Linear Equations

The \(y\)-components give

$b+c=e+f.$

The \(x\)-components give

$2a+b-c-2d-e+f=0.$

Eliminating \(b-e\) between these two relations yields the cleaner pair

$a-d=c-f,\qquad b-e=f-c.$

Every positive integer sextuple satisfying these two equations corresponds to an equiangular hexagon with those side lengths, and every such hexagon arises this way. So the problem becomes: count positive integer solutions with

$a+b+c+d+e+f\le n,$

then divide by congruence.

Step 2: Use Burnside's Lemma for Congruence Classes

Before quotienting by congruence, we count ordered sextuples. Congruence classes are orbits under the dihedral group \(D_6\), which has 12 symmetries: 6 rotations and 6 reflections. Burnside's lemma says

$H(n)=\frac{1}{12}\sum_{g\in D_6}\operatorname{Fix}(g),$

where \(\operatorname{Fix}(g)\) is the number of admissible sextuples left unchanged by the symmetry \(g\).

The 12 symmetries split into conjugacy classes, so only a few distinct counts are needed:

$H(n)=\frac{I(n)+2R_1(n)+2R_2(n)+R_3(n)+3F_{\mathrm{even}}(n)+3F_{\mathrm{odd}}(n)}{12}.$

Here \(I\) is the identity count, \(R_1,R_2,R_3\) come from rotations by \(60^\circ,120^\circ,180^\circ\), and \(F_{\mathrm{even}},F_{\mathrm{odd}}\) are the two reflection types.

Step 3: Rotation Counts Collapse to Compositions

A rotation by \(60^\circ\) or \(300^\circ\) forces all six sides to be equal, so the fixed tuples are

$ (x,x,x,x,x,x),\qquad 6x\le n.$

Hence

$R_1(n)=\left\lfloor\frac{n}{6}\right\rfloor.$

A rotation by \(120^\circ\) or \(240^\circ\) forces the pattern

$ (x,y,x,y,x,y),\qquad 3x+3y\le n.$

The number of positive pairs with \(x+y\le \lfloor n/3\rfloor\) is

$R_2(n)=\binom{\left\lfloor n/3\right\rfloor}{2}.$

A rotation by \(180^\circ\) forces

$ (x,y,z,x,y,z),\qquad 2(x+y+z)\le n,$

so

$R_3(n)=\binom{\left\lfloor n/2\right\rfloor}{3}.$

These are ordinary positive-composition counts.

Step 4: Parameterize the Identity Contribution

For the identity symmetry we must count every ordered sextuple satisfying the closure equations. Introduce the difference parameter

$\delta=a-d=c-f.$

Then we may write

$d=\alpha,\qquad f=\beta,\qquad e=\gamma,$

$a=\alpha+\delta,\qquad c=\beta+\delta,\qquad b=\gamma-\delta.$

This automatically enforces both closure equations. The perimeter becomes

$a+b+c+d+e+f=2(\alpha+\beta+\gamma)+\delta\le n.$

Positivity translates into

$\alpha\ge \max(1,1-\delta),\qquad \beta\ge \max(1,1-\delta),\qquad \gamma\ge \max(1,1+\delta).$

Let

$T_\delta=\left\lfloor\frac{n-\delta}{2}\right\rfloor,$

$\alpha_0=\beta_0=\max(1,1-\delta),\qquad \gamma_0=\max(1,1+\delta).$

After setting \(\alpha=\alpha_0+u\), \(\beta=\beta_0+v\), \(\gamma=\gamma_0+w\) with \(u,v,w\ge 0\), we get

$u+v+w\le R_\delta:=T_\delta-(\alpha_0+\beta_0+\gamma_0).$

The number of nonnegative triples with sum at most \(R_\delta\) is

$\binom{R_\delta+3}{3}.$

Therefore

$I(n)=\sum_{-n\le \delta\le n,\ R_\delta\ge 0}\binom{R_\delta+3}{3}.$

This is exactly the linear summation used by the implementations.

Step 5: Count the First Reflection Type

One reflection class fixes sextuples of the form

$ (u,v,w,u+v-w,w,v).$

Substituting this pattern into the closure equations shows that it is the general fixed form. Positivity requires

$u+v-w\ge 1\iff w\le u+v-1,$

and the perimeter condition is

$2u+3v+w\le n.$

So for each positive pair \((u,v)\), the third parameter \(w\) can range from \(1\) up to

$\min(u+v-1,\ n-2u-3v).$

The implementations do not iterate over \(w\). Instead, for each fixed \(v\), they split the \(u\)-range at the point where the minimum switches from \(u+v-1\) to \(n-2u-3v\). That turns the entire reflection class into a single linear-time arithmetic summation.

Step 6: Count the Second Reflection Type and Assemble Burnside

The other reflection class fixes sextuples of the simpler form

$ (u,u,v,u,u,v).$

Here the closure equations are automatic, and the perimeter condition is

$4u+2v\le n.$

If we set \(M=\lfloor n/2\rfloor\), this becomes

$2u+v\le M.$

For each \(u\ge 1\), the number of admissible positive \(v\) is \(M-2u\). Hence

$F_{\mathrm{odd}}(n)=\sum_{u=1}^{\lfloor (M-1)/2\rfloor}(M-2u).$

Combining both reflection counts with the rotation counts and the identity count gives the final formula

$\boxed{H(n)=\frac{I(n)+2R_1(n)+2R_2(n)+R_3(n)+3F_{\mathrm{even}}(n)+3F_{\mathrm{odd}}(n)}{12}.}$

Worked Example: Computing \(H(12)\)

This example matches one of the published checkpoints. First, the rotation terms are

$R_1(12)=\left\lfloor\frac{12}{6}\right\rfloor=2,\qquad R_2(12)=\binom{4}{2}=6,\qquad R_3(12)=\binom{6}{3}=20.$

For the identity term, only \(\delta=-2,-1,0,1,2\) contribute. Their values are

$1,\ 4,\ 20,\ 4,\ 1,$

so

$I(12)=30.$

For the two reflection classes, the corresponding sums give

$F_{\mathrm{even}}(12)=12,\qquad F_{\mathrm{odd}}(12)=6.$

Burnside then yields

$H(12)=\frac{30+2\cdot 2+2\cdot 6+20+3\cdot 12+3\cdot 6}{12}=\frac{120}{12}=10,$

which matches the stated checkpoint exactly.

How the Code Works

The C++, Python, and Java implementations follow the Burnside decomposition directly. They first evaluate the three rotation contributions from their closed forms, because those require only a few integer divisions and binomial formulas.

Next, the implementation computes the identity contribution by looping over every feasible integer value of the difference parameter \(\delta\). For each \(\delta\), it derives the minimal positive starting values forced by positivity, converts the remaining freedom into a nonnegative triple \((u,v,w)\), and adds the stars-and-bars count \(\binom{R_\delta+3}{3}\) whenever \(R_\delta\ge 0\).

For the first reflection class, the implementation loops over one side parameter and uses a split point to sum the second parameter range in two arithmetic pieces, avoiding an expensive inner enumeration. For the second reflection class, it uses the direct one-dimensional formula coming from \(2u+v\le \lfloor n/2\rfloor\).

Finally, it combines the six class counts with the Burnside weights \(1,2,2,1,3,3\) and divides by 12. The numeric types differ by language, but all three versions use exact integer arithmetic rather than floating point.

Complexity Analysis

The rotation terms and the second reflection class are \(O(1)\). The identity term is a single loop over \(2n+1\) possible values of \(\delta\), so it is \(O(n)\). The first reflection class is also evaluated by a single linear summation over the relevant side parameter range, again \(O(n)\). Therefore the overall running time is \(O(n)\).

The algorithm stores only a fixed number of counters and temporary arithmetic values, so the memory usage is \(O(1)\).

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=600
2. Burnside's lemma: Wikipedia — Burnside's lemma
3. Dihedral group: Wikipedia — Dihedral group
4. Stars and bars: Wikipedia — Stars and bars
5. Equiangular polygon: Wikipedia — Equiangular polygon