Detailed mathematical approach

Problem Summary

Let \(H(n)\) denote the number of regular hexagons whose six vertices lie on lattice points inside the triangular lattice region of size \(n\). In axial coordinates this region is

$T_n=\{(x,y)\in \mathbb{Z}_{\ge 0}^2 : x+y\le n\}.$

The task is not just to evaluate one \(H(n)\), but to compute the cumulative total

$S(N)=\sum_{n=3}^{N} H(n).$

A direct geometric search would be far too slow, so the solution turns the geometry into a one-parameter summation.

Mathematical Approach

The key observation is that every lattice regular hexagon can be described by one side vector together with its \(60^\circ\) rotation, and that the boundary conditions depend only on one simple integer parameter.

Step 1: Model a Hexagon with Axial Coordinates

Choose a nonzero lattice side vector

$u=(a,b).$

In axial coordinates, rotation by \(60^\circ\) sends this vector to

$v=(-b,a+b).$

If \(P\) is one vertex of the hexagon, then the six vertices are

$P,\quad P+u,\quad P+u+v,\quad P+2v,\quad P+2v-u,\quad P+v-u.$

This already determines a regular hexagon on the triangular lattice: consecutive edges are obtained by repeated \(60^\circ\) turns, so all sides have the same length and all interior angles are \(120^\circ\).

Step 2: Choose One Canonical Representative

The same hexagon can be described from several sides, so we restrict to the canonical sector

$a>0,\qquad b\ge 0.$

Among the six side directions of a regular hexagon, exactly one lies in this sector, so this removes double counting.

Now define the parameter

$k=a+b.$

For a fixed \(k\), the admissible canonical pairs are

$ (1,k-1),\ (2,k-2),\ \dots,\ (k,0), $

so there are exactly \(k\) such pairs. Different pairs may correspond to different lattice shapes, but they all consume the same amount of room against the boundary, and that is the quantity that matters for counting placements.

Step 3: Count the Valid Placements for Fixed \(k\)

Write the base vertex as \(P=(x,y)\). We must force all six vertices to remain inside \(T_n\), meaning

$x\ge 0,\qquad y\ge 0,\qquad x+y\le n$

for every listed vertex.

The strongest lower bound on the \(x\)-coordinate comes from \(P+2v-u\), whose first coordinate is

$x-a-2b,$

so we need

$x\ge a+2b.$

The strongest upper bound on \(x+y\) comes from \(P+u+v\), whose coordinate sum is

$x+y+2a+b,$

so we also need

$x+y\le n-2a-b.$

The remaining inequalities are weaker once these are satisfied. Shift the base point by setting

$x'=x-(a+2b).$

Then the conditions become

$x'\ge 0,\qquad y\ge 0,\qquad x'+y\le n-3(a+b)=n-3k.$

This is again a triangular lattice region, now of size \(n-3k\). Therefore the number of valid placements for one fixed canonical pair with parameter \(k\) is

$\binom{n-3k+2}{2}=\frac{(n-3k+1)(n-3k+2)}{2},$

provided \(3k\le n\), and it is \(0\) otherwise.

Step 4: Sum Over All Canonical Pairs

Since there are exactly \(k\) canonical pairs with \(a+b=k\), we obtain

$H(n)=\sum_{k=1}^{\lfloor n/3\rfloor} k\cdot \frac{(n-3k+1)(n-3k+2)}{2}.$

This already gives a fast \(O(n)\) formula for a single \(H(n)\).

For the cumulative total, swap the order of summation:

$S(N)=\sum_{n=3}^{N}H(n)=\sum_{k=1}^{\lfloor N/3\rfloor} k \sum_{n=3k}^{N}\frac{(n-3k+1)(n-3k+2)}{2}.$

Let

$t=n-3k+1,\qquad M=N-3k+1.$

Then the inner sum becomes

$\sum_{t=1}^{M}\frac{t(t+1)}{2}=\frac{M(M+1)(M+2)}{6}=\binom{M+2}{3}.$

So the final closed form used by the implementation is

$\boxed{S(N)=\sum_{k=1}^{\lfloor N/3\rfloor} k\cdot \frac{(N-3k+1)(N-3k+2)(N-3k+3)}{6}.}$

Worked Example: \(n=6\)

Here \(\lfloor 6/3\rfloor=2\), so only \(k=1\) and \(k=2\) contribute.

For \(k=1\):

$1\cdot \frac{(6-3+1)(6-3+2)}{2}=1\cdot \frac{4\cdot 5}{2}=10.$

For \(k=2\):

$2\cdot \frac{(6-6+1)(6-6+2)}{2}=2\cdot \frac{1\cdot 2}{2}=2.$

Therefore

$H(6)=10+2=12,$

which matches the known checkpoint used by the C++ implementation.

How the Code Works

The C++, Python, and Java implementations use the final cumulative formula directly. They iterate over every admissible \(k\) with \(3k\le N\), compute the remaining translation budget \(N-3k+1\), and add

$k\cdot \frac{(N-3k+1)(N-3k+2)(N-3k+3)}{6}$

to the running total.

The C++ implementation also evaluates the single-\(n\) formula on small checkpoints such as \(H(3)=1\), \(H(6)=12\), and \(H(20)=966\) before printing the final cumulative answer. The arithmetic uses sufficiently wide integer types because the intermediate cubic products are larger than a signed 64-bit multiplication can safely handle in C++.

Complexity Analysis

The loop runs once for each integer \(k\) with \(1\le k\le \lfloor N/3\rfloor\). Hence the running time is \(O(N)\) and the extra memory usage is \(O(1)\). The method is efficient because all geometric complexity has been collapsed into a single summation parameter.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=577
2. Triangular lattice: Wikipedia - Triangular lattice
3. Hexagon: Wikipedia - Hexagon
4. Tetrahedral number: Wikipedia - Tetrahedral number
5. Binomial coefficient: Wikipedia - Binomial coefficient