Project Euler Problem 276

Solution

Answer: 5777137137739632912

Let

$$T(N)=#{(a,b,c): a\le b\le c,\ a+b>c,\ a+b+c\le N}$$

be the number of all integer-sided triangles with perimeter at most $N$, and let

$$P(N)$$

be the number of primitive ones (i.e. $\gcd(a,b,c)=1$).

We want $P(10^7)$.

1. Mathematical analysis

Step 1: Count all integer triangles of perimeter $n$

Let $t(n)$ be the number of integer triangles with perimeter exactly $n$.

A classical result gives:

$$t(n)=\operatorname{round}!\left(\frac{n^2}{12}\right) -\left\lfloor \frac n4 \right\rfloor \left\lfloor \frac{n+2}{4}\right\rfloor.$$

We can verify on small examples:

$n=3$: only $(1,1,1)$, so $t(3)=1$
$n=5$: only $(1,2,2)$, so $t(5)=1$
$n=6$: $(1,2,3)$ fails triangle inequality, but $(2,2,2)$, $(1,2,3)$ invalid, $(1,1,4)$ invalid, so only $(2,2,2)$ and $(1,2,3)$ excluded ⇒ $t(6)=1$

The formula matches.

Define the cumulative count:

$$A(N)=\sum_{n\le N} t(n).$$

Since $t(n)$ is quadratic with a periodic correction (period 12), $A(N)$ becomes a cubic quasipolynomial. Writing

$$N=12q+r,\qquad 0\le r<12,$$

we obtain an exact $O(1)$ formula for $A(N)$. For example:

$$A(12q)=6q^2(2q+1),$$

and similarly for the other 11 residue classes.

Step 2: Primitive triangles via Möbius inversion

Every triangle $(a,b,c)$ has a unique gcd $d$:

$$(a,b,c)=d(a',b',c')$$

with $(a',b',c')$ primitive.

Thus:

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

This is a divisor convolution.

Applying Möbius inversion:

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

where $\mu$ is the Möbius function.

So the task reduces to:

Compute $\mu(d)$ up to $10^7$ using a linear sieve.
Compute the Mertens prefix sum

$$M(n)=\sum_{k\le n}\mu(k).$$

Group equal values of $\lfloor N/d\rfloor$:

$$P(N) = \sum A(v), \bigl(M(r)-M(l-1)\bigr),$$

where $v=\lfloor N/l\rfloor$ and $r=\lfloor N/v\rfloor$.

This reduces the summation to $O(\sqrt N)$.

2. Python implementation

from array import array

N = 10_000_000

def cumulative_triangles(n):
    """
    A(n) = number of integer-sided triangles
    with perimeter <= n.
    Exact O(1) quasipolynomial formula.
    """
    q, r = divmod(n, 12)

    if r == 0:
        return 6 * q * q * (2 * q + 1)
    elif r == 1:
        return q * (12 * q * q + 9 * q + 2)
    elif r == 2:
        return 3 * q * (2 * q + 1) ** 2
    elif r == 3:
        return 12 * q**3 + 15 * q**2 + 6 * q + 1
    elif r == 4:
        return (2 * q + 1) * (6 * q**2 + 6 * q + 1)
    elif r == 5:
        return 12 * q**3 + 21 * q**2 + 12 * q + 2
    elif r == 6:
        return 3 * (q + 1) * (2 * q + 1) ** 2
    elif r == 7:
        return (q + 1) * (12 * q**2 + 15 * q + 5)
    elif r == 8:
        return 6 * (q + 1) ** 2 * (2 * q + 1)
    elif r == 9:
        return 3 * (q + 1) ** 2 * (4 * q + 3)
    elif r == 10:
        return (q + 1) * (12 * q**2 + 24 * q + 11)
    else:  # r == 11
        return 3 * (q + 1) ** 2 * (4 * q + 5)

# ----- Linear sieve for Möbius function -----

mu = array('b', [0]) * (N + 1)
lp = array('I', [0]) * (N + 1)
primes = array('I')

mu[1] = 1

for i in range(2, N + 1):
    if lp[i] == 0:
        lp[i] = i
        primes.append(i)
        mu[i] = -1

    li = lp[i]

    for p in primes:
        v = i * p
        if v > N or p > li:
            break

        lp[v] = p

        if p == li:
            mu[v] = 0
            break
        else:
            mu[v] = -mu[i]

# ----- Prefix sums of Möbius -----

M = array('i', [0]) * (N + 1)

running = 0
for i in range(1, N + 1):
    running += mu[i]
    M[i] = running

# ----- Möbius inversion with floor-division grouping -----

answer = 0
l = 1

while l <= N:
    v = N // l
    r = N // v

    answer += cumulative_triangles(v) * (M[r] - M[l - 1])

    l = r + 1

print(answer)

3. Code walkthrough

`cumulative_triangles(n)`

Computes

$$A(n)=\sum_{k\le n} t(k)$$

in constant time using the exact residue-class formulas modulo 12.

This avoids storing all triangle counts up to $10^7$.

Linear sieve

We compute the Möbius function:

$$\mu(n)= \begin{cases} 1 & n=1\ (-1)^k & n \text{ squarefree with }k\text{ primes}\ 0 & \text{otherwise} \end{cases}$$

using an $O(N)$ linear sieve.

Prefix Mertens function

We store:

$$M(n)=\sum_{k\le n}\mu(k)$$

to allow fast range sums:

$$\sum_{d=l}^r \mu(d)=M(r)-M(l-1).$$

Harmonic grouping trick

Since

$$\left\lfloor \frac Nd\right\rfloor$$

takes only $O(\sqrt N)$ distinct values, we process intervals where it is constant.

This reduces the final summation from $10^7$ iterations to roughly $2\sqrt N$.

4. Small verification

Brute force checks:

$N=10$: result = 8
$N=20$: result = 58
$N=50$: result = 789
$N=100$: result = 6033

The optimized method exactly matches brute force.

For $N=10^7$, the count should scale cubically (roughly proportional to $N^3$), so a value around $10^{18}$ is reasonable.

The computation yields:

$$5777137137739632912$$

Answer: 5777137137739632912