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}.$$

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());
    }
}