Detailed mathematical approach

Problem Summary

Start with an equilateral triangle of side length \(n\), subdivided in the cross-hatched way described in the problem, and count every triangle whose three sides lie on drawn segments. For the Project Euler instance, \(n=36\).

The important point is that the implementations do not classify triangles by shape or size. Instead, they turn the whole picture into a finite arrangement of supporting lines and then count which triples of those lines really bound a triangle inside the outer hull.

Mathematical Approach

The derivation is geometric rather than recursive. Once the cross-hatching is written as explicit families of lines, the problem becomes: among all triples of generated lines, how many have three pairwise intersections that are inside the big triangle and are not collapsed into a single point?

Coordinate Model of the Outer Triangle

Set

$h=\frac{\sqrt{3}}{2},\qquad A=(0,0),\qquad B=(n,0),\qquad C=\left(\frac{n}{2},nh\right).$

This places the outer figure as a standard equilateral triangle. A point \(P\) lies inside or on the boundary precisely when it is on the left side of each directed edge \(AB\), \(BC\), and \(CA\). Using the oriented-area determinant

$\det(P,Q,R)=(Q_x-P_x)(R_y-P_y)-(Q_y-P_y)(R_x-P_x),$

the inside test is

$\det(A,B,P)\ge 0,\qquad \det(B,C,P)\ge 0,\qquad \det(C,A,P)\ge 0.$

Equivalently, in this coordinate system the hull is described by

$y\ge 0,\qquad y\le \sqrt{3}\,x,\qquad y\le \sqrt{3}\,(n-x).$

The Six Direction Families in the Cross-hatching

The code reveals that every drawn segment belongs to one of only six directions: horizontal, vertical, \(\pm 60^\circ\), and \(\pm 30^\circ\). After extending each drawn segment to its full supporting line, the families become

$\begin{aligned} y &= kh, && 0\le k\le n-1,\\ x-\sqrt{3}\,y &= s, && -(n-1)\le s\le n-1,\\ x-\frac{y}{\sqrt{3}} &= k, && 0\le k\le n-1,\\ x+\frac{y}{\sqrt{3}} &= k+1, && 0\le k\le n-1,\\ x+\sqrt{3}\,y &= t, && 1\le t\le 2n-1,\\ x &= \frac{u}{2}, && 1\le u\le 2n-1. \end{aligned}$

The family sizes are

$n,\quad 2n-1,\quad n,\quad n,\quad 2n-1,\quad 2n-1,$

so the total number of supporting lines is

$M=n+(2n-1)+n+n+(2n-1)+(2n-1)=9n-3.$

For \(n=36\), this is only \(M=321\) lines. That is the key reduction: the original picture looks complicated, but the entire counting problem is compressed into a modest finite line arrangement.

Intersections Turn the Drawing into Algebra

Each line is stored in coefficient form

$ax+by=c,$

where a line through \(P=(p_x,p_y)\) and \(Q=(q_x,q_y)\) uses

$a=p_y-q_y,\qquad b=q_x-p_x,\qquad c=q_xp_y-p_xq_y.$

For two lines \((a_1,b_1,c_1)\) and \((a_2,b_2,c_2)\), let

$\Delta=a_1b_2-a_2b_1.$

If \(\Delta=0\), the lines are parallel and cannot give a triangle vertex. Otherwise their unique intersection is

$x=\frac{c_1b_2-c_2b_1}{\Delta},\qquad y=\frac{a_1c_2-a_2c_1}{\Delta}.$

Any intersection outside the outer hull is discarded immediately. After this preprocessing, every unordered pair of lines is either marked invalid or assigned one concrete vertex inside the big triangle.

Why Valid Line Triples Are Exactly the Triangles

Take three generated lines \(\ell_1,\ell_2,\ell_3\). There are only three possibilities:

If some pair is parallel, at least one vertex is missing, so there is no triangle.

If all three pairwise intersections exist but two of them coincide, then the three lines are concurrent and the boundary degenerates at one point instead of forming three corners.

If the three pairwise intersections all exist and are three distinct points, then those points are the vertices of one and only one triangle whose sides lie on \(\ell_1,\ell_2,\ell_3\).

The converse is just as important: every triangle in the cross-hatched figure has three sides on three supporting lines from the list above, and those supporting lines are unique. So counting valid triples of lines counts every triangle exactly once.

Worked Example at \(n=1\)

When \(n=1\), the six families contribute exactly six lines:

$y=0,\quad x-\sqrt{3}\,y=0,\quad x-\frac{y}{\sqrt{3}}=0,\quad x+\frac{y}{\sqrt{3}}=1,\quad x+\sqrt{3}\,y=1,\quad x=\frac{1}{2}.$

Choose the three lines

$y=0,\qquad x=\frac{1}{2},\qquad x+\sqrt{3}\,y=1.$

Their pairwise intersections are

$\left(\frac{1}{2},0\right),\qquad (1,0),\qquad \left(\frac{1}{2},\frac{1}{2\sqrt{3}}\right),$

which are three distinct points inside the hull, so they contribute one triangle.

By contrast, the triple

$y=0,\qquad x-\frac{y}{\sqrt{3}}=0,\qquad x-\sqrt{3}\,y=0$

has all three pairwise intersections at \(A=(0,0)\), so it is rejected as degenerate. Running this criterion over all \(\binom{6}{3}=20\) triples leaves 16 triangles, matching the first checkpoint used by the implementations.

How the Code Works

Generate the Arrangement from a Unit Template

The C++, Python, and Java implementations start from a unit equilateral triangle with vertices \((0,0)\), \((1,0)\), and \((1/2,\sqrt{3}/2)\). Midpoints of the unit sides determine the \(\pm 30^\circ\) and vertical auxiliary families, and integer or half-integer translations generate every line needed for size \(n\).

This is why the line list is so regular: the same six prototype directions are simply shifted across the figure until all supporting lines of the cross-hatching have been emitted.

Cache All Usable Pairwise Intersections

For each pair of lines, the implementation solves one \(2\times 2\) linear system. Parallel pairs are rejected by the determinant test. Nonparallel pairs are then filtered by the three oriented-area inequalities of the outer triangle, so only vertices that actually lie in the figure survive.

The result is a lookup table indexed by line pairs. Later stages never recompute an intersection; they only query whether a pair has a valid vertex and, if so, what that vertex is.

Enumerate Triples and Remove Degeneracies

The final sweep considers every \(i<j<k\). A triple contributes exactly when the three stored pairwise intersections \((i,j)\), \((i,k)\), and \((j,k)\) are all valid and no two of those points are numerically equal.

A small floating-point tolerance is used in the equality test because all coordinates are built from rational numbers and \(\sqrt{3}\), so exact binary arithmetic is not available. The implementations also verify the geometric model on the small cases \(n=1\to 16\) and \(n=2\to 104\) before counting the full case.

Complexity Analysis

Let \(M=9n-3\) be the number of generated lines. Pair preprocessing needs \(O(M^2)\) intersections, and the main triangle count checks all \(\binom{M}{3}\) triples, so the overall time is

$O(M^3)=O(n^3).$

The pair table uses

$O(M^2)=O(n^2)$

memory.

For the actual input \(n=36\), we have \(M=321\), hence only \(\binom{321}{2}=51360\) line pairs and \(\binom{321}{3}=5461280\) line triples. Those numbers are small enough that exhaustive geometric enumeration is entirely practical.

Footnotes and References

1. Problem page: Project Euler 163
2. Equilateral triangle: Wikipedia - Equilateral triangle
3. Line-line intersection: Wikipedia - Line-line intersection
4. Determinant: Wikipedia - Determinant
5. Oriented area test: cp-algorithms - Oriented area of a triangle