Open Source · 7 Languages · 900+ Problems

Project Euler Solutions

Complete solutions in C++, Python & Java — with step-by-step mathematical explanations

All Problems

Problem 276: Primitive Triangles

Project Euler Problem 276 Solution

EulerSolve provides an optimized solution for Project Euler Problem 276, Primitive Triangles, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We want the number of primitive integer triangles with perimeter at most $N$, where “primitive” means $\gcd(a,b,c)=1.$ The code does not generate triangles one by one. Instead, it first counts all integer triangles by perimeter using a closed formula, then removes scaled copies with Möbius inversion. Mathematical Approach 1) Counting all integer triangles with a fixed perimeter Let $T(p)$ be the number of integer triangles with perimeter exactly $p$, written in sorted form $a\le b\le c$ and $a+b+c=p,\qquad a+b>c.$ A convenient way to count them is to start from all partitions of $p$ into three positive parts, then subtract the non-triangles. All partitions into three positive parts. The number of triples $a\le b\le c$ with $a+b+c=p$ is the classical partition formula $Q(p)=\left\lfloor\frac{p^2+3}{12}\right\rfloor.$ Invalid triples. A partition fails to be a triangle exactly when $c\ge a+b$. If we set $d=a+b$, then $d\le\lfloor p/2\rfloor$, and the number of ordered-by-size pairs $a\le b$ with $a+b=d$ is $\lfloor d/2\rfloor$....

Detailed mathematical approach

Problem Summary

We want the number of primitive integer triangles with perimeter at most $N$, where “primitive” means

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

The code does not generate triangles one by one. Instead, it first counts all integer triangles by perimeter using a closed formula, then removes scaled copies with Möbius inversion.

Mathematical Approach

1) Counting all integer triangles with a fixed perimeter

Let $T(p)$ be the number of integer triangles with perimeter exactly $p$, written in sorted form $a\le b\le c$ and

$a+b+c=p,\qquad a+b>c.$

A convenient way to count them is to start from all partitions of $p$ into three positive parts, then subtract the non-triangles.

All partitions into three positive parts. The number of triples $a\le b\le c$ with $a+b+c=p$ is the classical partition formula

$Q(p)=\left\lfloor\frac{p^2+3}{12}\right\rfloor.$

Invalid triples. A partition fails to be a triangle exactly when $c\ge a+b$. If we set $d=a+b$, then $d\le\lfloor p/2\rfloor$, and the number of ordered-by-size pairs $a\le b$ with $a+b=d$ is $\lfloor d/2\rfloor$. Hence the number of invalid triples is

$I(p)=\sum_{d=2}^{\lfloor p/2\rfloor}\left\lfloor\frac d2\right\rfloor =\left\lfloor\frac{\lfloor p/2\rfloor^2}{4}\right\rfloor.$

Therefore

$T(p)=Q(p)-I(p).$

After simplifying by parity, this becomes the compact formula used in code:

For even $p$:

$T(p)=\left\lfloor\frac{p^2+24}{48}\right\rfloor,$

For odd $p$:

$T(p)=\left\lfloor\frac{(p+3)^2+24}{48}\right\rfloor.$

2) Worked example: perimeter $p=12$

The partitions of $12$ into three positive nondecreasing parts are

$\begin{aligned} &(1,1,10),(1,2,9),(1,3,8),(1,4,7),(1,5,6),\\ &(2,2,8),(2,3,7),(2,4,6),(2,5,5),\\ &(3,3,6),(3,4,5),(4,4,4). \end{aligned}$

The first nine fail the triangle inequality. The last three are valid:

$T(12)=3,$

corresponding to

$ (2,5,5),\qquad (3,4,5),\qquad (4,4,4). $

The formula agrees:

$T(12)=\left\lfloor\frac{12^2+24}{48}\right\rfloor=\left\lfloor\frac{168}{48}\right\rfloor=3.$

3) From exact-perimeter counts to cumulative counts

Let

$A(n)=\sum_{p\le n} T(p).$

Then $A(n)$ counts all integer triangles with perimeter at most $n$, primitive or not. The code builds this array as a prefix sum of the closed formula above.

4) Why primitive triangles are extracted by Möbius inversion

Every integer triangle has a unique gcd $d$. Dividing all three sides by $d$ gives a unique primitive triangle. Conversely, multiplying a primitive triangle by $d$ produces a non-primitive one.

For exact perimeter this means “all triangles with perimeter $p$” are obtained by scaling primitive triangles whose primitive perimeter divides $p$. Summing over all perimeters up to $n$ gives the cumulative identity

$A(n)=\sum_{d\ge1} P\!\left(\left\lfloor\frac nd\right\rfloor\right),$

where $P(n)$ is the number of primitive triangles with perimeter at most $n$.

This is exactly a divisor-sum transform, so Möbius inversion yields

$P(n)=\sum_{d=1}^{n}\mu(d)\,A\!\left(\left\lfloor\frac nd\right\rfloor\right).$

That is the final formula implemented by the solver.

5) Intuition for the scaling relation

The triangle $(6,8,10)$ is not primitive because its gcd is $2$; dividing by $2$ gives the primitive triangle $(3,4,5)$. Likewise, $(2,4,4)$ comes from the primitive triangle $(1,2,2)$. The Möbius sum corrects exactly for the overcount caused by all such scaled copies.

How the Code Works

Closed formula. all_triangles_with_perimeter(p) evaluates the parity-based formula for $T(p)$.

Möbius sieve. mobius_up_to() computes $\mu(1),\dots,\mu(N)$ with a linear sieve.

Prefix of all triangles. prefix_all[n] stores $A(n)$.

Primitive answer. solve() evaluates

$P(N)=\sum_{d=1}^{N}\mu(d)\,A\!\left(\left\lfloor\frac Nd\right\rfloor\right).$

Validation. The source compares the fast method to a brute-force triangle generator for perimeter limits $30,50,100,150,250$. For example, the primitive cumulative count at $N=30$ is

$P(30)=179.$

Complexity Analysis

The linear sieve for $\mu$ costs $O(N)$ time and $O(N)$ memory. Building the prefix array $A(n)$ is another $O(N)$, and the Möbius inversion sum is a final $O(N)$ pass. So the total complexity is near-linear:

$O(N)\text{ time},\qquad O(N)\text{ memory}.$