Project Euler

Triangles with Integral Sides and an Integral Angle

How many triangles are there with integer sides and perimeter not exceeding 10^8 that have at least one angle that is an integer number of degrees?

Source sync Apr 19, 2026

Problem #0279

Level Level 16

Solved By 892

Languages C++, Python

Answer 416577688

Length 327 words

geometrymodular_arithmeticnumber_theory

How many triangles are there with integral sides, at least one integral angle (measured in degrees), and a perimeter that does not exceed $10^8$?

Problem 279: Triangles with Integral Sides and an Integral Angle

Mathematical Analysis

Which Integer-Degree Angles Are Possible?

By Niven’s theorem, the only angles $\theta \in (0°, 180°)$ that are integer degrees AND have $\cos\theta$ rational are:

\theta \in \{60°, 90°, 120°\}

This is required because the law of cosines $c^2 = a^2 + b^2 - 2ab\cos\theta$ demands rational cosine for integer sides.

Three Families of Triangles

Family 1: 120-degree triangles ( $C = 120°$ , largest angle)

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

Primitive parametrization ( $m > n > 0$ , $\gcd(m,n) = 1$ , $(m-n) \not\equiv 0 \pmod{3}$ ):

Sides: $m^2 - n^2$ , $2mn + n^2$ , $m^2 + mn + n^2$
Perimeter: $(2m+n)(m+n)$

Family 2: 60-degree triangles (non-equilateral, angle $B = 60°$ )

b^2 = a^2 + c^2 - ac

Using the substitution $x = a$ , $y = c - a$ in the Loeschian equation $x^2 + xy + y^2 = b^2$ :

Case 1 ( $m > n > 0$ , $\gcd(m,n) = 1$ , $(m-n) \not\equiv 0 \pmod{3}$ ):

Sides: $m^2 - n^2$ , $m^2 + mn + n^2$ , $m(m + 2n)$
Perimeter: $3m(m+n)$

Case 2 (same conditions on $m, n$ ):

Sides: $n(2m+n)$ , $m^2 + mn + n^2$ , $m(m + 2n)$
Perimeter: $(2m+n)(m+2n)$

Family 3: 90-degree triangles (Pythagorean)

c^2 = a^2 + b^2

Primitive parametrization ( $m > n > 0$ , $\gcd(m,n) = 1$ , $m - n$ odd):

Sides: $m^2 - n^2$ , $2mn$ , $m^2 + n^2$
Perimeter: $2m(m+n)$

Equilateral triangles ( $a = b = c$ , all angles $60°$ ):

Perimeter: $3a \le N$
Count: $\lfloor N/3 \rfloor$

No Overlap Between Families

60 and 90: A 60-90 triangle has third angle 30. But $\cos(30°) = \sqrt{3}/2$ is irrational, so integer sides are impossible.
60 and 120: Sum is 180, no room for third angle.
90 and 120: Sum exceeds 180.

Counting

For each primitive triple with perimeter $p_0$ , the number of similar triangles with perimeter $\le N$ is $\lfloor N / p_0 \rfloor$ .

Total count:

\text{answer} = \lfloor N/3 \rfloor + \sum_{\text{primitive 120}} \lfloor N/p_0 \rfloor + \sum_{\text{primitive 60, case 1}} \lfloor N/p_0 \rfloor + \sum_{\text{primitive 60, case 2}} \lfloor N/p_0 \rfloor + \sum_{\text{primitive 90}} \lfloor N/p_0 \rfloor

Proof of Parametrization

Eisenstein Integers

The equation $a^2 + ab + b^2 = c^2$ is the norm equation in $\mathbb{Z}[\omega]$ where $\omega = e^{2\pi i/3}$ . The norm $N(a + b\omega) = a^2 + ab + b^2$ . Factoring in $\mathbb{Z}[\omega]$ (a PID) yields the parametrization.

Pythagorean Triples

The equation $a^2 + b^2 = c^2$ is parametrized via Gaussian integers: $a + bi = (m + ni)^2$ gives the well-known Euclid formula.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity

Each parametric loop runs in $O(\sqrt{N})$ iterations for $m$ , and for each $m$ , the inner loop over $n$ is $O(m)$ . Total work: $O(N^{3/4})$ approximately (since many pairs are skipped by the coprimality and modular conditions).

In practice, the algorithm runs in under 1 second for $N = 10^8$ .

Answer

\boxed{416577688}

C++ project_euler/problem_279/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 279: Triangles with integer sides and perimeter <= 10^8
 * that have at least one angle that is an integer number of degrees.
 *
 * By Niven's theorem, the only angles in (0,180) that are integer degrees
 * AND have rational cosine are: 60, 90, 120 degrees.
 * (cos must be rational for the law of cosines to yield integer sides.)
 *
 * So we count triangles with at least one angle equal to 60, 90, or 120 degrees.
 * These three families have NO overlap (30-60-90 triangle has irrational side ratio,
 * and 30-90-60, 60-90-30 etc. all require cos(30)=sqrt(3)/2 which is irrational).
 *
 * Total = count_60 + count_90 + count_120 + equilateral
 * (with equilateral = all angles 60, counted separately since parametrization excludes them)
 *
 * 120-degree triangles: c^2 = a^2+ab+b^2
 *   Primitive param (m>n>0, gcd(m,n)=1, (m-n)%3!=0):
 *     sides: m^2-n^2, 2mn+n^2, m^2+mn+n^2
 *     perimeter: (2m+n)(m+n)
 *
 * 60-degree (B=60, non-equilateral) Case 1:
 *   sides: m^2-n^2, m^2+mn+n^2, m(m+2n)
 *   perimeter: 3m(m+n)
 *
 * 60-degree Case 2:
 *   sides: n(2m+n), m^2+mn+n^2, m(m+2n)
 *   perimeter: (2m+n)(m+2n)
 *
 * 90-degree (Pythagorean): c^2 = a^2+b^2
 *   Primitive param (m>n>0, gcd(m,n)=1, m-n odd):
 *     sides: m^2-n^2, 2mn, m^2+n^2
 *     perimeter: 2m(m+n)
 *
 * Equilateral: a=b=c, perimeter 3a <= N. Count: floor(N/3).
 */

int main(){
    const long long N = 100000000LL;
    long long count = 0;

    // Equilateral triangles (all angles = 60)
    count += N / 3;

    // 120-degree triangles
    for (long long m = 2; ; m++) {
        long long min_p = (2*m+1)*(m+1);
        if (min_p > N) break;
        for (long long n = 1; n < m; n++) {
            if (__gcd(m, n) != 1LL) continue;
            if ((m - n) % 3 == 0) continue;
            long long p0 = (2*m+n)*(m+n);
            if (p0 > N) break;
            count += N / p0;
        }
    }

    // 60-degree, Case 1: perimeter = 3m(m+n)
    for (long long m = 2; ; m++) {
        long long min_p = 3*m*(m+1);
        if (min_p > N) break;
        for (long long n = 1; n < m; n++) {
            if (__gcd(m, n) != 1LL) continue;
            if ((m - n) % 3 == 0) continue;
            long long p0 = 3*m*(m+n);
            if (p0 > N) break;
            count += N / p0;
        }
    }

    // 60-degree, Case 2: perimeter = (2m+n)(m+2n)
    for (long long m = 2; ; m++) {
        long long min_p = (2*m+1)*(m+2);
        if (min_p > N) break;
        for (long long n = 1; n < m; n++) {
            if (__gcd(m, n) != 1LL) continue;
            if ((m - n) % 3 == 0) continue;
            long long p0 = (2*m+n)*(m+2*n);
            if (p0 > N) break;
            count += N / p0;
        }
    }

    // 90-degree (Pythagorean) triangles
    for (long long m = 2; ; m++) {
        long long min_p = 2*m*(m+1);
        if (min_p > N) break;
        for (long long n = 1; n < m; n++) {
            if (__gcd(m, n) != 1LL) continue;
            if ((m - n) % 2 == 0) continue;
            long long p0 = 2*m*(m+n);
            if (p0 > N) break;
            count += N / p0;
        }
    }

    cout << count << endl;
    return 0;
}

Python project_euler/problem_279/solution.py

#!/usr/bin/env python3
"""
Problem 279: Triangles with Integral Sides and an Integral Angle

Count triangles with integer sides, perimeter <= 10^8, and at least one
angle that is an integer number of degrees (60, 90, or 120 by Niven's theorem).

Four families (no overlaps):
  1. Equilateral (all 60-deg): a=b=c, perimeter 3a
  2. 120-deg: c^2 = a^2+ab+b^2, parametrized via Eisenstein integers
  3. 60-deg (non-equilateral): b^2 = a^2+c^2-ac, two sub-cases
  4. 90-deg (Pythagorean): c^2 = a^2+b^2, Euclid parametrization
"""

from math import gcd, isqrt

def solve(N=10**8):
    count = 0

    # Equilateral
    count += N // 3

    # 120-degree: perimeter = (2m+n)(m+n)
    m = 2
    while True:
        min_p = (2*m+1)*(m+1)
        if min_p > N:
            break
        for n in range(1, m):
            if gcd(m, n) != 1:
                continue
            if (m - n) % 3 == 0:
                continue
            p0 = (2*m+n)*(m+n)
            if p0 > N:
                break
            count += N // p0
        m += 1

    # 60-degree Case 1: perimeter = 3m(m+n)
    m = 2
    while True:
        min_p = 3*m*(m+1)
        if min_p > N:
            break
        for n in range(1, m):
            if gcd(m, n) != 1:
                continue
            if (m - n) % 3 == 0:
                continue
            p0 = 3*m*(m+n)
            if p0 > N:
                break
            count += N // p0
        m += 1

    # 60-degree Case 2: perimeter = (2m+n)(m+2n)
    m = 2
    while True:
        min_p = (2*m+1)*(m+2)
        if min_p > N:
            break
        for n in range(1, m):
            if gcd(m, n) != 1:
                continue
            if (m - n) % 3 == 0:
                continue
            p0 = (2*m+n)*(m+2*n)
            if p0 > N:
                break
            count += N // p0
        m += 1

    # 90-degree (Pythagorean): perimeter = 2m(m+n)
    m = 2
    while True:
        min_p = 2*m*(m+1)
        if min_p > N:
            break
        for n in range(1, m):
            if gcd(m, n) != 1:
                continue
            if (m - n) % 2 == 0:
                continue
            p0 = 2*m*(m+n)
            if p0 > N:
                break
            count += N // p0
        m += 1

    return count

if __name__ == "__main__":
    N = 10**8
    answer = solve(N)
    print(answer)