Detailed mathematical approach

Problem Summary

We must count all integer-sided triangles with perimeter at most \(L\) that contain an angle of exactly \(60^\circ\), \(90^\circ\), or \(120^\circ\). The final Project Euler total is intentionally omitted; this page explains the parameterizations and counting logic used by the C++ solution.

Mathematical Approach

1) Three disjoint angle classes

Let

$N(L)=N_{60}(L)+N_{90}(L)+N_{120}(L).$

For integer-sided triangles these classes are disjoint:

\(90^\circ\) and \(120^\circ\) cannot both occur because their sum already exceeds \(180^\circ\).

\(60^\circ\) and \(120^\circ\) also cannot both occur because that would leave a third angle of \(0^\circ\).

\(60^\circ\) and \(90^\circ\) would force a \(30\)-\(60\)-\(90\) triangle, whose side ratio is \(1:\sqrt3:2\). Since \(\sqrt3\) is irrational, no positive integer scaling can make all three sides integers.

So every valid triangle belongs to exactly one of the three counters. Equilateral triangles belong only to the \(60^\circ\) family.

2) Law of cosines gives three Diophantine equations

If side \(c\) is opposite the special angle \(\theta\), then

$c^2=a^2+b^2-2ab\cos\theta.$

For the three angles in the problem:

$90^\circ:\ c^2=a^2+b^2,$

$60^\circ:\ c^2=a^2+b^2-ab,$

$120^\circ:\ c^2=a^2+b^2+ab.$

So Project Euler 279 is really three separate integer-parameterization problems plus a scaling count.

3) The \(90^\circ\) family: ordinary Euclid triples

Primitive right triangles are given by Euclid's formula:

$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$

with

$m>n,\qquad \gcd(m,n)=1,\qquad m-n\text{ odd}.$

The primitive perimeter is

$P_{0,90}=a+b+c=2m(m+n).$

Example: \((m,n)=(2,1)\) gives \((3,4,5)\) with perimeter \(12\). Every scaled copy \(k(3,4,5)\) is still a right triangle, so this primitive triple contributes

$\left\lfloor\frac{L}{12}\right\rfloor$

triangles.

For a fixed \(m\), the smallest possible perimeter occurs at \(n=1\):

$P_{0,90}\ge 2m(m+1).$

This is exactly the lower bound behind max_m_90() in the code.

4) A useful viewpoint for \(60^\circ\) and \(120^\circ\): Eisenstein norms

Let \(\omega\) be a primitive cube root of unity, so

$\omega^2+\omega+1=0.$

The Eisenstein norm is

$N(x+y\omega)=(x+y\omega)(x+y\omega^2)=x^2-xy+y^2.$

This is exactly the quadratic form that appears for \(60^\circ\):

$c^2=a^2-ab+b^2=N(a+b\omega).$

For \(120^\circ\), write

$a^2+ab+b^2=a^2-a(-b)+(-b)^2=N(a-b\omega).$

So the \(60^\circ\) and \(120^\circ\) families are the Eisenstein-integer analogues of Euclid's formula for right triangles.

5) The primitive \(120^\circ\) family

Square \(m-n\omega\):

$ (m-n\omega)^2 =m^2-n^2-(2mn+n^2)\omega. $

Its norm is

$N(m-n\omega)^2=(m^2+mn+n^2)^2.$

This yields the standard primitive parameterization

$a=m^2-n^2,\qquad b=2mn+n^2,\qquad c=m^2+mn+n^2,$

and a direct substitution confirms

$c^2=a^2+b^2+ab.$

Example: \((m,n)=(2,1)\) gives

$a=3,\qquad b=5,\qquad c=7,$

and indeed

$7^2=3^2+5^2+3\cdot5=49.$

The primitive perimeter is

$P_{0,120}=a+b+c=2m^2+3mn+n^2.$

For fixed \(m\), this is smallest at \(n=1\):

$P_{0,120}\ge 2m^2+3m+1.$

That is exactly the bound used by max_m_120().

There is one more subtlety: \(\gcd(m,n)=1\) does not automatically force \(\gcd(a,b,c)=1\). For example, \((m,n)=(4,1)\) gives

$ (15,9,21)=3\cdot(5,3,7). $

So the implementation simply tests

$\gcd(a,b,c)=1$

directly instead of encoding the extra mod-\(3\) restriction by hand.

6) The primitive \(60^\circ\) family, and why the code has two branches

First, equilateral triangles contribute immediately:

$ (k,k,k),\qquad 3k\le L,\qquad \text{count}=\left\lfloor\frac{L}{3}\right\rfloor. $

For non-equilateral primitive triangles, square \(m+n\omega\):

$ (m+n\omega)^2 =(m^2-n^2)+(2mn-n^2)\omega. $

Its norm is

$N(m+n\omega)^2=(m^2-mn+n^2)^2.$

So one valid branch is

$a=m^2-n^2,\qquad b_1=2mn-n^2,\qquad c=m^2-mn+n^2,$

with identity

$c^2=a^2+b_1^2-ab_1.$

Now fix

$a=m^2-n^2,\qquad c=m^2-mn+n^2$

and solve the \(60^\circ\) equation for the missing side \(b\):

$b^2-ab+(a^2-c^2)=0.$

This quadratic has one root \(b_1\), so by Vieta its second root is

$b_2=a-b_1=(m^2-n^2)-(2mn-n^2)=m^2-2mn.$

Therefore the code counts two non-equilateral branches:

$b_1=2mn-n^2,\qquad b_2=m^2-2mn.$

Example: \((m,n)=(3,1)\) gives

$ (a,c)=(8,7),\qquad b_1=5,\qquad b_2=3. $

So we get two valid triangles:

$ (5,7,8),\qquad (3,7,8), $

and in both cases

$7^2=5^2+8^2-5\cdot8=3^2+8^2-3\cdot8=49.$

Why restrict to \(n\le \lfloor(m-1)/2\rfloor\)? Because larger \(n\) only reproduces the same unordered triangle. If we replace \(n\) by \(m-n\), then

$a'=m^2-(m-n)^2=2mn-n^2=b_1,$

$b_1'=2m(m-n)-(m-n)^2=m^2-n^2=a,$

and

$c'=m^2-m(m-n)+(m-n)^2=c.$

So \((m,n)\) and \((m,m-n)\) generate the same triangle with \(a\) and \(b_1\) swapped. Example:

$ (m,n)=(4,1)\Rightarrow(15,7,13), $

$ (m,n)=(4,3)\Rightarrow(7,15,13). $

Scanning only

$1\le n\le \left\lfloor\frac{m-1}{2}\right\rfloor$

keeps exactly one representative of each unordered triangle. It also ensures the second root is positive:

$b_2=m(m-2n)>0.$

The primitive perimeters of the two branches are

$P_{0,60A}=a+b_1+c=2m^2+mn-n^2\ge 2m^2+m-1,$

$P_{0,60B}=a+b_2+c=3m(m-n)\ge 3m\left\lceil\frac m2\right\rceil.$

The code writes the second bound in integer arithmetic as

$3m\left(\frac{m+1}{2}\right)\qquad\text{with integer division},$

which is exactly what appears in max_m_60().

As in the \(120^\circ\) family, the code uses the direct test

$\gcd(a,b,c)=1$

to keep only primitive triangles.

7) Why counting primitive triangles is enough

If \((a,b,c)\) is primitive and has one of the target angles, then every multiple

$k(a,b,c)$

has the same angle pattern, and its perimeter is \(kP_0\). Therefore one primitive triangle contributes exactly

$\left\lfloor\frac{L}{P_0}\right\rfloor$

copies. This explains why every counting loop in the program adds a floor-division term.

8) How the code mirrors the mathematics

Separate counters. The program maintains with_60, with_90, and with_120 independently.

Immediate equilateral count. with_60 starts from

$\left\lfloor\frac{L}{3}\right\rfloor.$

Three parameter scans. count_90_range(), count_120_range(), and count_60_non_eq_range() scan the corresponding \((m,n)\)-lattices.

Primitive filters. The right-triangle family uses the classical coprime/opposite-parity conditions; the \(60^\circ\) and \(120^\circ\) families use \(\gcd(m,n)=1\) plus a direct \(\gcd(a,b,c)=1\) test.

Hard \(m\)-bounds. The helper functions max_m_90(), max_m_120(), and max_m_60() are derived exactly from the perimeter lower bounds above.

Parallel split. Threads only divide the \(m\)-values by residue class modulo the thread count; this changes wall-clock time, not the counted set.

Brute-force validation. The program checks

$N(100)=84,\qquad N_{60}(100)=53,\qquad N_{90}(100)=17,\qquad N_{120}(100)=14,$

and also compares the fast method against a direct brute-force triangle scan for \(L=120,200,300\).

Complexity Analysis

Each family is an \((m,n)\)-lattice scan with gcd filters, so the runtime is roughly quadratic in the relevant \(m_{\max}\). The perimeter bounds cut off large useless regions early. Memory usage is \(O(1)\) apart from a small amount of thread bookkeeping and the tiny brute-force table used by the checkpoints.

Further Reading

1. Problem page: https://projecteuler.net/problem=279
2. Pythagorean triples: https://en.wikipedia.org/wiki/Pythagorean_triple
3. Law of cosines: https://en.wikipedia.org/wiki/Law_of_cosines