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

A triangle with integer sides is written as $(a,b,c)$ with $a\le b\le c$, so that each triangle is counted once. Three positive lengths with $a\le b\le c$ form a triangle exactly when $a+b\gt c$; for $a+b=c$ the three sides would lie flat along one line. The triangle is primitive if $\gcd(a,b,c)=1$, that is, if no integer greater than $1$ divides all three sides. We must count the primitive integer triangles whose perimeter $a+b+c$ does not exceed $N=10^7$. ^[1] The statement gives no smaller example values, so we compute our own: up to perimeter $30$ there are $225$ integer triangles, and $179$ of them are primitive.

The whole solution in one sentence: count all integer triangles of each perimeter with a rounding formula, add these counts up, and then remove every triangle whose three sides share a factor with the help of the Möbius function, which works because every triangle is a whole-number multiple of exactly one primitive triangle.

Mathematical Approach

We write $T(p)$ for the number of integer triangles with perimeter exactly $p$, $A(n)$ for the number of those with perimeter at most $n$, and $P(n)$ for the number of primitive ones with perimeter at most $n$; the task asks for $P(N)$. Sections 1–6 find $T$ and $A$, Sections 7–10 turn $A$ into $P$, and Sections 11–12 prepare the computation.

1. Small perimeters

Listing by hand the triples $a\le b\le c$ with $a+b+c=p$ and $a+b\gt c$ gives:

$p=3$: $(1,1,1)$; $p=4$: none, because $(1,1,2)$ is flat; $p=5$: $(1,2,2)$; $p=6$: $(2,2,2)$.
$p=7$: $(1,3,3)$, $(2,2,3)$; $p=8$: $(2,3,3)$.
$p=9$: $(1,4,4)$, $(2,3,4)$, $(3,3,3)$; $p=10$: $(2,4,4)$, $(3,3,4)$.
$p=11$: $(1,5,5)$, $(2,4,5)$, $(3,3,5)$, $(3,4,4)$; $p=12$: $(2,5,5)$, $(3,4,5)$, $(4,4,4)$.

So $T(3),T(4),\dots,T(12)$ are $1,0,1,1,2,1,3,2,4,3$, and $A(12)=18$. Four of these triangles are not primitive, namely $(2,2,2)$, $(3,3,3)$, $(2,4,4)$ and $(4,4,4)$, so $P(12)=14$. Two patterns stand out. Every odd perimeter has as many triangles as the perimeter three larger: $T(7)=T(10)=2$ and $T(9)=T(12)=3$. And the even perimeters $6,8,10,12$ have $1,1,2,3$ triangles, which are the numbers of ways to split $3,4,5,6$ into three positive parts. The next three sections explain both patterns.

2. Odd perimeters: one more on every side

Call $e=a+b-c$ the excess of a triple; the triple is a triangle exactly when $e\ge1$. Since $e=p-2c$, the excess has the same parity as the perimeter $p$, so for an even perimeter a positive excess is in fact at least $2$.

Claim. For every odd $p$, $T(p)=T(p+3)$.

Proof. Add $1$ to every side: $(a,b,c)\mapsto(a+1,b+1,c+1)$. This keeps the order of the sides and raises the perimeter to $p+3$ and the excess to $e+1\ge2$, so a triangle of perimeter $p$ becomes a triangle of perimeter $p+3$. Conversely, a triangle $(a,b,c)$ of the even perimeter $p+3$ has $e\ge2$. Subtracting $1$ from every side leaves the excess $e-1\ge1$, and the smallest new side is positive because $a\ge c-b+2\ge2$. The two maps undo each other, so they pair off the triangles of the two perimeters one to one.

For example, $(1,3,3)\leftrightarrow(2,4,4)$ and $(2,2,3)\leftrightarrow(3,3,4)$.

3. Even perimeters: measuring from the semi-perimeter

Let $p=2m$, so that the semi-perimeter is $m$, and put

$$x=m-a,\qquad y=m-b,\qquad z=m-c.$$

Then $x\ge y\ge z$ because $a\le b\le c$; the triangle condition becomes $z=(a+b-c)/2\ge1$; and $x+y+z=3m-2m=m$. Conversely, any integers $x\ge y\ge z\ge1$ with $x+y+z=m$ give back the sides $a=y+z$, $b=x+z$, $c=x+y$, which satisfy $a\le b\le c$, $a+b+c=2m$ and $a+b-c=2z\ge2$. Hence $T(2m)=Q(m)$, where $Q(m)$ is the number of ways to write $m$ as a sum of three positive integers when the order does not matter, the number of partitions of $m$ into three parts. For $m=6$, the partitions $4+1+1$, $3+2+1$ and $2+2+2$ give the three triangles $(2,5,5)$, $(3,4,5)$ and $(4,4,4)$ of perimeter $12$.

4. Three parts: the nearest integer to $m^2/12$

We first count ordered triples $(x,y,z)$ of positive integers with $x+y+z=m$. By the stars-and-bars argument, they correspond to the ways of cutting a row of $m$ stones at two of its $m-1$ gaps, so there are $\binom{m-1}{2}$ of them. ^[5] In this count a partition with three different parts appears $6$ times, a partition with exactly two equal parts $3$ times, and the partition $u+u+u$, which exists only when $3$ divides $m$, once. The ordered triples with $x=y$ are the solutions of $2x+z=m$, one for each $x$ from $1$ to $\lfloor(m-1)/2\rfloor$, and they contain each partition with two equal parts once and $u+u+u$ once. Adding them three times brings every partition with two equal parts up to $6$ copies and $u+u+u$ up to $4$; two more copies of $u+u+u$ make every partition appear exactly $6$ times:

$$6\,Q(m)=\binom{m-1}{2}+3\left\lfloor\frac{m-1}{2}\right\rfloor+2\,[3\mid m],$$

where $[3\mid m]$ is $1$ if $3$ divides $m$ and $0$ otherwise. For $m=6$ this gives $Q(6)=(10+6+2)/6=3$. For even $m$ the first two terms add up to $(m^2-4)/2$, and for odd $m$ to $(m^2-1)/2$. So the difference $Q(m)-m^2/12$ is $0$ when $m$ leaves the remainder $0$ after division by $6$, it is $-1/3$ for the remainders $2$ and $4$, $1/4$ for the remainder $3$, and $-1/12$ for the remainders $1$ and $5$. In every case it is smaller than $1/2$ in absolute value, and therefore $Q(m)$ is the integer nearest to $m^2/12$. ^[4]

5. The formula for $T(p)$

By Sections 3 and 4, $T(2m)=Q(m)$ is the integer nearest to $m^2/12=(2m)^2/48$, and Section 2 reduces an odd perimeter $p$ to the even perimeter $p+3$. Rounding $x/48$ to the nearest integer is the same as computing $\lfloor(x+24)/48\rfloor$, so for even $p$

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

and for odd $p$

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

The rounding never meets a tie: by Section 4 the fractional part of $m^2/12$ is $0$, $1/12$, $1/3$ or $3/4$, never $1/2$. As a check, $T(11)=T(14)=\lfloor220/48\rfloor=4$ and $T(12)=\lfloor168/48\rfloor=3$, as listed in Section 1, and for $p=1$ and $p=2$ the formulas give $0$, as they should. The numbers $T(p)$ form Alcuin's sequence, and both Wikipedia and the OEIS state exactly this rounding formula. ^[2] ^[3]

6. All triangles up to a perimeter

Adding the exact counts gives $A(n)=T(1)+T(2)+\dots+T(n)$, the number of all integer triangles, primitive or not, with perimeter at most $n$. From Section 1, $A(10)=11$ and $A(12)=18$; further values are $A(15)=34$, $A(30)=225$, $A(100)=7361$ and $A(250)=111111$. Because $T(p)$ is close to $p^2/48$ and $1^2+2^2+\dots+n^2$ is close to $n^3/3$, the count $A(n)$ grows like $n^3/144$.

7. Every triangle is a multiple of one primitive triangle

Let $g=\gcd(a,b,c)$. Dividing all three sides by $g$ keeps their order and the inequality $a+b\gt c$, and the new sides have greatest common divisor $1$; so $(a/g,b/g,c/g)$ is a primitive triangle and $(a,b,c)$ is $g$ times it. Conversely, $d$ times a primitive triangle is a triangle whose sides have greatest common divisor exactly $d$. For example, $(6,8,10)=2\cdot(3,4,5)$, while $(6,10,15)$ is primitive although any two of its sides share a factor: only a factor common to all three sides matters.

The fact used below follows at once: the triangles with perimeter at most $n$ whose three sides are all divisible by $d$ are the $d$-fold copies of the triangles with perimeter at most $n/d$, so there are exactly $A(\lfloor n/d\rfloor)$ of them. Grouping all triangles by their $g$ also gives

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

For instance, $A(12)=P(12)+P(6)+P(4)+P(3)$${}=14+2+1+1=18$: the four terms count the primitive triangles, then $(2,2,2)$ and $(2,4,4)$, then $(3,3,3)$, then $(4,4,4)$.

8. The Möbius function

To solve this relation for $P$ we use the Möbius function $\mu$. It is defined by $\mu(1)=1$, by $\mu(d)=(-1)^k$ if $d$ is a product of $k$ different primes, and by $\mu(d)=0$ if $d$ is divisible by the square of a prime; for $d=1,2,\dots,12$ its values are $1,-1,-1,0,-1,1,-1,0,0,1,-1,0$. ^[6] Its key property is

$$\sum_{d\mid g}\mu(d)=\begin{cases}1,&g=1,\\0,&g\gt1.\end{cases}$$

For $g=1$ the only divisor is $1$. If $g\gt1$ has $k\ge1$ different prime factors, the divisors with $\mu(d)\ne0$ are the products of some of these primes. Exactly $\binom kj$ of them use $j$ primes, and each of those has $\mu(d)=(-1)^j$, so by the binomial theorem the sum is $\sum_j\binom kj(-1)^j=(1-1)^k=0$. For $g=12$, the divisors $1,2,3,4,6,12$ contribute $1-1-1+0+1+0=0$.

9. Counting only the primitive triangles

Let $t=(a,b,c)$ run over all triangles with perimeter at most $n$. By Section 8 the inner sum below is $1$ for a primitive triangle and $0$ for any other one. We exchange the two finite sums and group the pairs $(t,d)$ by $d$; by Section 7, each $d$ is paired with exactly $A(\lfloor n/d\rfloor)$ triangles:

$$\begin{aligned}P(n)&=\sum_{t}\ \sum_{d\mid\gcd(a,b,c)}\mu(d)\\&=\sum_{d=1}^{n}\mu(d)\,A\left(\left\lfloor\frac nd\right\rfloor\right).\end{aligned}$$

This is the formula that the programs evaluate. It is the Möbius inversion of the relation of Section 7, in the form for functions of a real variable, ^[7] and it can be read as inclusion–exclusion: start with all triangles, subtract those whose sides are all even, all multiples of $3$, all multiples of $5$ and so on, then add back those subtracted twice, such as the multiples of $6$, and continue alternately. The terms with $d\gt n/3$ vanish, because then $\lfloor n/d\rfloor\le2$ and $A(2)=0$.

10. Worked example: $n=30$

Only $d\le10$ give nonzero terms, and $\mu(4)=\mu(8)=\mu(9)=0$, so

$$\begin{aligned}P(30)&=A(30)-A(15)-A(10)-A(6)\\&\quad+A(5)-A(4)+A(3)\\&=225-34-11-3+2-1+1=179.\end{aligned}$$

The $34$ triangles with even sides are the doubles of the triangles with perimeter at most $15$, and the $11$ multiples of $3$ are the triples of those with perimeter at most $10$. The multiples of $5$ are $(5,5,5)$, $(5,10,10)$ and $(10,10,10)$, and the only multiple of $7$ is $(7,7,7)$. The multiples of $6$, $(6,6,6)$ and $(6,12,12)$, were subtracted twice, as even triangles and as multiples of $3$, and are added back once; likewise $(10,10,10)$ is subtracted for $d=2$ and $d=5$ and added back for $d=10$. In total each of the $225-179=46$ triangles that are not primitive is removed exactly once, and a brute-force count confirms $P(30)=179$.

The formula also shows what share of all triangles is primitive. Since $T(p)$ differs from $p^2/48$ by at most a constant times $p$, $A(x)$ differs from $x^3/144$ by at most a constant times $x^2$. Replacing each $A(\lfloor n/d\rfloor)$ by $(n/d)^3/144$ thus changes each term by at most a constant times $(n/d)^2$, so the sum by at most a constant times $n^2$, as $\sum_d1/d^2$ converges, and leaves $n^3/144$ times $\sum_{d\le n}\mu(d)/d^3$, which differs by less than $1/n^2$ from $\sum_{d\ge1}\mu(d)/d^3=1/\zeta(3)$, where $\zeta(3)=1+1/2^3+1/3^3+\dots$. ^[6] So $P(n)/A(n)$ tends to $1/\zeta(3)\approx0.8319$, the limit, as $M$ grows, of the probability that three integers chosen at random from $1,\dots,M$ have no common factor; ^[9] the ratio is $0.8196$ for $n=100$ and $0.8307$ for $n=1000$.

11. All Möbius values at once: a linear sieve

The formula needs $\mu(d)$ for every $d\le N$. A linear sieve finds these values, together with the least prime factor $\operatorname{lp}(i)$ of every $i\le N$, in time proportional to $N$. ^[8] It runs through $i=2,3,\dots,N$. If no smaller number has marked $i$, then $i$ is prime, and the sieve records $\operatorname{lp}(i)=i$ and $\mu(i)=-1$. Then it multiplies $i$ by the primes $p$ found so far, in increasing order, as long as $p\le\operatorname{lp}(i)$ and $ip\le N$, and marks $\operatorname{lp}(ip)=p$. If $p\lt\operatorname{lp}(i)$, the prime $p$ does not divide $i$, so $ip$ has one prime factor more than $i$ and $\mu(ip)=-\mu(i)$. If $p=\operatorname{lp}(i)$, then $p^2$ divides $ip$, so $\mu(ip)=0$, and the loop for this $i$ stops. For $i=15$ the sieve sets $\mu(30)=-\mu(15)=-1$ and $\mu(45)=0$; for $i=6$ it sets only $\mu(12)=0$.

Every composite $v\le N$ is marked exactly once. Write $v=p\,i$ with $p=\operatorname{lp}(v)$; every prime factor of $i$ also divides $v$, so $p\le\operatorname{lp}(i)$, and $v$ is marked when the outer loop reaches $i$. Any marking $v=p'i'$ has $p'\le\operatorname{lp}(i')$, so $p'$ is the least prime factor of $v$, which forces $p'=p$ and $i'=i$. For $N=10^7$ the sieve finds the $664\,579$ primes and marks each of the $9\,335\,420$ composites once.

12. How large the numbers get

Rounding adds at most $1/2$, so $T(p)\le(p+3)^2/48+1/2$, and summing over $p\le n$ gives $A(n)\lt(n+4)^3/144+n/2$, that is,

$$A(n)\lt\frac{n^3}{144}+\frac{n^2}{12}+\frac{5n}{6}+\frac49.$$

For $n=10^7$ this is below $7\cdot10^{18}$, while the largest signed 64-bit integer is $2^{63}-1\approx9.22\cdot10^{18}$; so every entry of the table fits into 64 bits, even with a sign. Since $|\mu(d)|\le1$, no partial sum of Section 9 exceeds $\sum_{d\le N}A(\lfloor N/d\rfloor)$ in absolute value. Applying the bound to $n=\lfloor N/d\rfloor\le N/d$ and using $\sum_d d^{-3}\lt1+\tfrac18+\tfrac18=\tfrac54$, $\sum_d d^{-2}\lt2$ (compare the tails with $\int_2^\infty x^{-3}\,dx$ and $\int_1^\infty x^{-2}\,dx$) and $\sum_{d\le N}d^{-1}\le1+\ln N$ gives

$$\begin{aligned}\sum_{d=1}^{N}A\left(\left\lfloor\frac Nd\right\rfloor\right)&\lt\frac{5N^3}{576}+\frac{N^2}{6}\\&\quad+\frac{5N}{6}(1+\ln N)+\frac{4N}{9},\end{aligned}$$

which is below $8.69\cdot10^{18}$ for $N=10^7$. So a signed 64-bit accumulator cannot overflow either. The margin is modest: the table entry $A(n)$ reaches $2^{63}$ already at $n=10\,992\,185$.

How the Code Works

The C++ program ^[10] starts in main, where parse_arguments reads two optional arguments: --perimeter= with digits replaces the default limit $10^7$, which must be at least $3$, and --skip-checkpoints switches off the self-check run_checkpoints, which otherwise runs first. Then the program prints the value of solve for the limit.

solve(perimeter_limit) first calls mobius_up_to, the sieve of Section 11. It keeps the vectors mu and lp of length $N+1$ and the list primes, for which it reserves $N/10$ places, more than enough; a prime is recognised by lp[i] == 0, and the product $ip$ is formed in 64 bits.

Next, solve fills the table prefix_all of unsigned 64-bit numbers, in which entry $n$ is $A(n)$ of Section 6, by one running sum of all_triangles_with_perimeter(p) over $p=1,\dots,N$. That function is the formula of Section 5, with the rounding down done by unsigned integer division. Finally, $d$ runs from $1$ to $N$; the values with $\mu(d)=0$ are skipped, so only the $6\,079\,291$ squarefree $d\le10^7$ do any work, and $\mu(d)$ times prefix_all[perimeter_limit / d] is added to a signed 128-bit accumulator, a compiler extension of GCC and Clang; ^[11] the index is $\lfloor N/d\rfloor$, since integer division rounds down. The total is returned as an unsigned 64-bit number.

run_checkpoints compares solve with brute_count for the limits $30$, $50$, $100$, $150$ and $250$, where both must give $179$, $789$, $6033$, $20071$ and $91888$; a mismatch ends the program with exit code $2$. brute_count uses none of the mathematics above: it tries every $a\le L/3$, every $b$ from $a$ to $(L-a)/2$ and every $c$ from $b$ to $L-a-b$, where $L$ is the limit, and counts the triples with $a+b\gt c$ and $\gcd(a,\gcd(b,c))=1$, computed with std::gcd.

The Python and Java versions contain the same functions, all_triangles_with_perimeter and mobius_up_to in Python, allTrianglesWithPerimeter and mobiusUpTo in Java, and a solve with the final sum, but the limit is fixed at $10^7$ and there are no options and no checkpoints. Python's integers have arbitrary precision, so no 64-bit limit applies. Java keeps the table and the sum in long and its primes in an ArrayList<Integer>; Java's integer operations do not report an overflow, ^[11] so the bounds of Section 12 are what make its result trustworthy. The C++ option --perimeter= has no range check: the unsigned table wraps around modulo $2^{64}$ from $n=13\,849\,285$ on, and as the final conversion works modulo $2^{64}$ too, the output is exact only up to $n=14\,725\,465$ and wrong above that, without a warning; parse_int_after_prefix also misreads limits beyond the int range.

Complexity and Verification

All three steps take time proportional to $N$: the sieve marks each composite once and tests each number once, and the running sum and the final loop make $N$ steps each. The memory is proportional to $N$ as well: in C++, mu and lp take $40$ MB each for $N=10^7$; lp is released when the sieve returns, and then prefix_all takes $80$ MB, so at most about $120$ MB of arrays are alive at the same time. On an Apple-silicon Mac the C++ program, compiled by Clang with -O2, takes about $0.05$ s, checkpoints included, with a peak resident memory of about 157 MiB; the Java version takes $0.14$ s, and the Python version $2.3$ s and about 630 MiB for its lists of integer objects.

A faster route exists, although the published programs do not need it. The quotient $\lfloor N/d\rfloor$ takes only $6323$ different values for $N=10^7$, and $A(n)$ can be computed with a few operations, because by Sections 2 to 4 it is a sum of values $Q(m)=m^2/12+\delta_m$ whose corrections $\delta_m$, the differences found there, repeat with period $6$. Solving the relation of Section 7 for $P$ at those values alone, as

$$P(n)=A(n)-\sum_{d=2}^{n}P\left(\left\lfloor\frac nd\right\rfloor\right),$$

with the $d$ of equal quotient grouped together and every value of $P$ computed once and remembered, takes no sieve and on the order of $N^{3/4}$ operations, because the value for $q$ needs about $2\sqrt q$ groups and the sum of $\sqrt q$ over all values $q$ of $\lfloor N/k\rfloor$ is of that order.

Unless --skip-checkpoints is given, the C++ program checks itself against the brute force for the five limits above before it prints anything. For this article we also checked the formula of Section 5 against a direct count of the triangles for every $p\le1500$, the four cases of Section 4 for every $m\lt200$, the sieve against trial division for every $d\le10^5$, and the formula of Section 9 against a brute-force count for every $n\le300$ and for $n=1000$, where $A(1000)=6\,986\,111$ and $P(1000)=5\,803\,431$. A separately written program that uses no Möbius values and no table of length $N$, only the closed form of $A$ and the recursion above with its $6321$ remembered values, gives the same result as all three published programs at $N=10^7$. These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The pairing of odd and even perimeters, the formula for $Q(m)$, the inclusion–exclusion with $\mu$, the worked examples and the size bounds are derived explicitly in this article.

Project Euler 276 — Primitive Triangles. The official statement considers the triangles with integer sides a ≤ b ≤ c, calls such a triangle primitive if gcd(a, b, c) = 1, and asks how many primitive integer-sided triangles have a perimeter not exceeding 10 000 000. It gives no example values.
Wikipedia — Integer triangle. Positive integers are the sides of a triangle when they satisfy the triangle inequality: the longest side is shorter than the sum of the other two. The number of integer triangles with perimeter p, up to congruence, is the integer nearest to p²/48 for even p and to (p + 3)²/48 for odd p; these numbers form Alcuin's sequence.
OEIS A005044 — Alcuin's sequence. The entry counts the triangles with integer sides and perimeter n and gives the formula round(n²/48) for even n and round((n + 3)²/48) for odd n, and the relation a(n + 3) = a(n) for odd n that Section 2 proves.
OEIS A069905 — Number of partitions of n into 3 positive parts. The entry gives a(n) = round(n²/12), which Section 4 proves, and a(n) = A005044(2n) = A005044(2n − 3), the link between partitions and triangles of Sections 2 and 3.
Wikipedia — Stars and bars (combinatorics). The number of k-tuples of positive integers with sum n is the binomial coefficient C(n − 1, k − 1); Section 4 uses it with k = 3.
Wikipedia — Möbius function. μ(n) is 1 for n = 1, (−1)ᵏ for a product of k distinct primes and 0 when n is divisible by a square greater than 1; the sum of μ(d) over the divisors d of n is 1 for n = 1 and 0 for n > 1; and the sum of μ(n)/nˢ over all n is 1/ζ(s) for Re s > 1.
Wikipedia — Möbius inversion formula. The article states a version for functions on [1, ∞): if G(x) is the sum of F(x/n) over the integers 1 ≤ n ≤ x, for all x ≥ 1, then F(x) is the sum of μ(n) G(x/n) over the same n. With F(x) = P(⌊x⌋) and G(x) = A(⌊x⌋) this is the formula of Section 9.
cp-algorithms — Linear Sieve. The sieve stores the least prime factor lp[i] of every i, multiplies i only by the primes up to lp[i], goes through every composite number exactly once and therefore runs in O(n) time.
Wikipedia — Coprime integers. The probability that k randomly chosen integers are setwise coprime is 1/ζ(k); for k = 3 this is the limit of P(n)/A(n) in Section 10.
C++ — Euler276.cpp. The linked immutable C++ revision contains all_triangles_with_perimeter, mobius_up_to, solve, brute_count and run_checkpoints. It is the implementation record for this article.
GCC manual — 128-bit Integers describes the __int128 extension used for the C++ accumulator. The Java Language Specification, §4.2.1 and §4.2.2, gives the range of long, from −2⁶³ to 2⁶³ − 1, and states that the integer operators do not indicate overflow in any way.

Problem 276 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

namespace {

using i64 = long long;
using u64 = std::uint64_t;

struct Options {
    int perimeter_limit = 10'000'000;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--perimeter=", options.perimeter_limit)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.perimeter_limit >= 3;
}

u64 all_triangles_with_perimeter(const int p) {
    if ((p & 1) == 0) {
        // round(p^2 / 48)
        return static_cast<u64>((static_cast<u64>(p) * static_cast<u64>(p) + 24ULL) / 48ULL);
    }

    // round((p + 3)^2 / 48)
    const u64 t = static_cast<u64>(p + 3);
    return (t * t + 24ULL) / 48ULL;
}

std::vector<int> mobius_up_to(const int n) {
    std::vector<int> mu(static_cast<std::size_t>(n + 1), 0);
    std::vector<int> lp(static_cast<std::size_t>(n + 1), 0);
    std::vector<int> primes;
    primes.reserve(n / 10);

    mu[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (lp[static_cast<std::size_t>(i)] == 0) {
            lp[static_cast<std::size_t>(i)] = i;
            primes.push_back(i);
            mu[static_cast<std::size_t>(i)] = -1;
        }
        for (int p : primes) {
            const i64 v = static_cast<i64>(i) * static_cast<i64>(p);
            if (v > n || p > lp[static_cast<std::size_t>(i)]) {
                break;
            }
            lp[static_cast<std::size_t>(v)] = p;
            if (p == lp[static_cast<std::size_t>(i)]) {
                mu[static_cast<std::size_t>(v)] = 0;
                break;
            }
            mu[static_cast<std::size_t>(v)] = -mu[static_cast<std::size_t>(i)];
        }
    }

    return mu;
}

u64 solve(const int perimeter_limit) {
    const std::vector<int> mu = mobius_up_to(perimeter_limit);

    std::vector<u64> prefix_all(static_cast<std::size_t>(perimeter_limit + 1), 0);
    for (int p = 1; p <= perimeter_limit; ++p) {
        prefix_all[static_cast<std::size_t>(p)] = prefix_all[static_cast<std::size_t>(p - 1)] +
                                                  all_triangles_with_perimeter(p);
    }

    __int128 sum = 0;
    for (int d = 1; d <= perimeter_limit; ++d) {
        const int mu_d = mu[static_cast<std::size_t>(d)];
        if (mu_d == 0) {
            continue;
        }
        const u64 add = prefix_all[static_cast<std::size_t>(perimeter_limit / d)];
        sum += static_cast<__int128>(mu_d) * static_cast<__int128>(add);
    }

    return static_cast<u64>(sum);
}

u64 brute_count(const int perimeter_limit) {
    u64 count = 0;
    for (int a = 1; a <= perimeter_limit / 3; ++a) {
        for (int b = a; b <= (perimeter_limit - a) / 2; ++b) {
            const int max_c = perimeter_limit - a - b;
            for (int c = b; c <= max_c; ++c) {
                if (a + b <= c) {
                    continue;
                }
                if (std::gcd(a, std::gcd(b, c)) != 1) {
                    continue;
                }
                ++count;
            }
        }
    }
    return count;
}

bool run_checkpoints() {
    for (int perimeter : {30, 50, 100, 150, 250}) {
        const u64 slow = brute_count(perimeter);
        const u64 fast = solve(perimeter);
        if (slow != fast) {
            std::cerr << "Checkpoint failed at perimeter=" << perimeter
                      << ": brute=" << slow << ", fast=" << fast << '\n';
            return false;
        }
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }
    std::cout << solve(options.perimeter_limit) << '\n';
    return 0;
}

Python

def solve():
    perimeter_limit = 10_000_000

    def all_triangles_with_perimeter(p):
        if p % 2 == 0:
            return (p * p + 24) // 48
        else:
            t = p + 3
            return (t * t + 24) // 48

    def mobius_up_to(n):
        mu = [0] * (n + 1)
        lp = [0] * (n + 1)
        primes = []
        mu[1] = 1
        for i in range(2, n + 1):
            if lp[i] == 0:
                lp[i] = i
                primes.append(i)
                mu[i] = -1
            for p in primes:
                v = i * p
                if v > n or p > lp[i]:
                    break
                lp[v] = p
                if p == lp[i]:
                    mu[v] = 0
                    break
                mu[v] = -mu[i]
        return mu

    mu = mobius_up_to(perimeter_limit)

    prefix_all = [0] * (perimeter_limit + 1)
    for p in range(1, perimeter_limit + 1):
        prefix_all[p] = prefix_all[p - 1] + all_triangles_with_perimeter(p)

    total = 0
    for d in range(1, perimeter_limit + 1):
        if mu[d] == 0:
            continue
        total += mu[d] * prefix_all[perimeter_limit // d]

    return str(total)

if __name__ == '__main__':
    print(solve())

Java

import java.util.*;

public class Euler276 {
    static long allTrianglesWithPerimeter(int p) {
        if ((p & 1) == 0) {
            long lp = p;
            return (lp * lp + 24L) / 48L;
        }
        long t = p + 3L;
        return (t * t + 24L) / 48L;
    }

    static int[] mobiusUpTo(int n) {
        int[] mu = new int[n + 1];
        int[] lp = new int[n + 1];
        List<Integer> primes = new ArrayList<>(n / 10);

        mu[1] = 1;
        for (int i = 2; i <= n; ++i) {
            if (lp[i] == 0) {
                lp[i] = i;
                primes.add(i);
                mu[i] = -1;
            }
            for (int p : primes) {
                long v = (long) i * p;
                if (v > n || p > lp[i]) {
                    break;
                }
                lp[(int) v] = p;
                if (p == lp[i]) {
                    mu[(int) v] = 0;
                    break;
                }
                mu[(int) v] = -mu[i];
            }
        }
        return mu;
    }

    public static String solve() {
        int perimeterLimit = 10_000_000;
        int[] mu = mobiusUpTo(perimeterLimit);

        long[] prefixAll = new long[perimeterLimit + 1];
        for (int p = 1; p <= perimeterLimit; ++p) {
            prefixAll[p] = prefixAll[p - 1] + allTrianglesWithPerimeter(p);
        }

        long sum = 0;
        for (int d = 1; d <= perimeterLimit; ++d) {
            int muD = mu[d];
            if (muD == 0) {
                continue;
            }
            long add = prefixAll[perimeterLimit / d];
            sum += muD * add;
        }

        return String.valueOf(sum);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}