Problem 279: Triangles with Integral Sides and an Integral Angle

Project Euler Problem 279 Solution

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

Problem Summary We must count all integer-sided triangles with perimeter at most $L$ that contain an angle of exactly $60^\circ$, $90^\circ$, or $120^\circ$. The final Project Euler total is intentionally omitted; this page explains the parameterizations and counting logic used by the C++ solution. Mathematical Approach 1) Three disjoint angle classes Let $$N(L)=N_{60}(L)+N_{90}(L)+N_{120}(L).$$ For integer-sided triangles these classes are disjoint: $90^\circ$ and $120^\circ$ cannot both occur because their sum already exceeds $180^\circ$. $60^\circ$ and $120^\circ$ also cannot both occur because that would leave a third angle of $0^\circ$. $60^\circ$ and $90^\circ$ would force a $30$-$60$-$90$ triangle, whose side ratio is $1:\sqrt3:2$. Since $\sqrt3$ is irrational, no positive integer scaling can make all three sides integers. So every valid triangle belongs to exactly one of the three counters. Equilateral triangles belong only to the $60^\circ$ family. 2) Law of cosines gives three Diophantine equations If side $c$ is opposite the special angle $\theta$, then $$c^2=a^2+b^2-2ab\cos\theta.$$ For the three angles in the problem: $$90^\circ:\ c^2=a^2+b^2,$$ $$60^\circ:\ c^2=a^2+b^2-ab,$$ $$120^\circ:\ c^2=a^2+b^2+ab.$$ So Project Euler 279 is really three separate integer-parameterization problems plus a scaling count....

Detailed mathematical approach

Problem Summary

We must count all integer-sided triangles with perimeter at most $L$ that contain an angle of exactly $60^\circ$, $90^\circ$, or $120^\circ$. The final Project Euler total is intentionally omitted; this page explains the parameterizations and counting logic used by the C++ solution.

Mathematical Approach

1) Three disjoint angle classes

Let

$$N(L)=N_{60}(L)+N_{90}(L)+N_{120}(L).$$

For integer-sided triangles these classes are disjoint:

$90^\circ$ and $120^\circ$ cannot both occur because their sum already exceeds $180^\circ$.

$60^\circ$ and $120^\circ$ also cannot both occur because that would leave a third angle of $0^\circ$.

$60^\circ$ and $90^\circ$ would force a $30$-$60$-$90$ triangle, whose side ratio is $1:\sqrt3:2$. Since $\sqrt3$ is irrational, no positive integer scaling can make all three sides integers.

So every valid triangle belongs to exactly one of the three counters. Equilateral triangles belong only to the $60^\circ$ family.

2) Law of cosines gives three Diophantine equations

If side $c$ is opposite the special angle $\theta$, then

$$c^2=a^2+b^2-2ab\cos\theta.$$

For the three angles in the problem:

$$90^\circ:\ c^2=a^2+b^2,$$

$$60^\circ:\ c^2=a^2+b^2-ab,$$

$$120^\circ:\ c^2=a^2+b^2+ab.$$

So Project Euler 279 is really three separate integer-parameterization problems plus a scaling count.

3) The $90^\circ$ family: ordinary Euclid triples

Primitive right triangles are given by Euclid's formula:

$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$

with

$$m>n,\qquad \gcd(m,n)=1,\qquad m-n\text{ odd}.$$

The primitive perimeter is

$$P_{0,90}=a+b+c=2m(m+n).$$

Example: $(m,n)=(2,1)$ gives $(3,4,5)$ with perimeter $12$. Every scaled copy $k(3,4,5)$ is still a right triangle, so this primitive triple contributes

$$\left\lfloor\frac{L}{12}\right\rfloor$$

triangles.

For a fixed $m$, the smallest possible perimeter occurs at $n=1$:

$$P_{0,90}\ge 2m(m+1).$$

This is exactly the lower bound behind max_m_90() in the code.

4) A useful viewpoint for $60^\circ$ and $120^\circ$: Eisenstein norms

Let $\omega$ be a primitive cube root of unity, so

$$\omega^2+\omega+1=0.$$

The Eisenstein norm is

$$N(x+y\omega)=(x+y\omega)(x+y\omega^2)=x^2-xy+y^2.$$

This is exactly the quadratic form that appears for $60^\circ$:

$$c^2=a^2-ab+b^2=N(a+b\omega).$$

For $120^\circ$, write

$$a^2+ab+b^2=a^2-a(-b)+(-b)^2=N(a-b\omega).$$

So the $60^\circ$ and $120^\circ$ families are the Eisenstein-integer analogues of Euclid's formula for right triangles.

5) The primitive $120^\circ$ family

Square $m-n\omega$:

$$ (m-n\omega)^2 =m^2-n^2-(2mn+n^2)\omega. $$

Its norm is

$$N(m-n\omega)^2=(m^2+mn+n^2)^2.$$

This yields the standard primitive parameterization

$$a=m^2-n^2,\qquad b=2mn+n^2,\qquad c=m^2+mn+n^2,$$

and a direct substitution confirms

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

Example: $(m,n)=(2,1)$ gives

$$a=3,\qquad b=5,\qquad c=7,$$

and indeed

$$7^2=3^2+5^2+3\cdot5=49.$$

The primitive perimeter is

$$P_{0,120}=a+b+c=2m^2+3mn+n^2.$$

For fixed $m$, this is smallest at $n=1$:

$$P_{0,120}\ge 2m^2+3m+1.$$

That is exactly the bound used by max_m_120().

There is one more subtlety: $\gcd(m,n)=1$ does not automatically force $\gcd(a,b,c)=1$. For example, $(m,n)=(4,1)$ gives

$$ (15,9,21)=3\cdot(5,3,7). $$

So the implementation simply tests

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

directly instead of encoding the extra mod-$3$ restriction by hand.

6) The primitive $60^\circ$ family, and why the code has two branches

First, equilateral triangles contribute immediately:

$$ (k,k,k),\qquad 3k\le L,\qquad \text{count}=\left\lfloor\frac{L}{3}\right\rfloor. $$

For non-equilateral primitive triangles, square $m+n\omega$:

$$ (m+n\omega)^2 =(m^2-n^2)+(2mn-n^2)\omega. $$

Its norm is

$$N(m+n\omega)^2=(m^2-mn+n^2)^2.$$

So one valid branch is

$$a=m^2-n^2,\qquad b_1=2mn-n^2,\qquad c=m^2-mn+n^2,$$

with identity

$$c^2=a^2+b_1^2-ab_1.$$

Now fix

$$a=m^2-n^2,\qquad c=m^2-mn+n^2$$

and solve the $60^\circ$ equation for the missing side $b$:

$$b^2-ab+(a^2-c^2)=0.$$

This quadratic has one root $b_1$, so by Vieta its second root is

$$b_2=a-b_1=(m^2-n^2)-(2mn-n^2)=m^2-2mn.$$

Therefore the code counts two non-equilateral branches:

$$b_1=2mn-n^2,\qquad b_2=m^2-2mn.$$

Example: $(m,n)=(3,1)$ gives

$$ (a,c)=(8,7),\qquad b_1=5,\qquad b_2=3. $$

So we get two valid triangles:

$$ (5,7,8),\qquad (3,7,8), $$

and in both cases

$$7^2=5^2+8^2-5\cdot8=3^2+8^2-3\cdot8=49.$$

Why restrict to $n\le \lfloor(m-1)/2\rfloor$? Because larger $n$ only reproduces the same unordered triangle. If we replace $n$ by $m-n$, then

$$a'=m^2-(m-n)^2=2mn-n^2=b_1,$$

$$b_1'=2m(m-n)-(m-n)^2=m^2-n^2=a,$$

and

$$c'=m^2-m(m-n)+(m-n)^2=c.$$

So $(m,n)$ and $(m,m-n)$ generate the same triangle with $a$ and $b_1$ swapped. Example:

$$ (m,n)=(4,1)\Rightarrow(15,7,13), $$

$$ (m,n)=(4,3)\Rightarrow(7,15,13). $$

Scanning only

$$1\le n\le \left\lfloor\frac{m-1}{2}\right\rfloor$$

keeps exactly one representative of each unordered triangle. It also ensures the second root is positive:

$$b_2=m(m-2n)>0.$$

The primitive perimeters of the two branches are

$$P_{0,60A}=a+b_1+c=2m^2+mn-n^2\ge 2m^2+m-1,$$

$$P_{0,60B}=a+b_2+c=3m(m-n)\ge 3m\left\lceil\frac m2\right\rceil.$$

The code writes the second bound in integer arithmetic as

$$3m\left(\frac{m+1}{2}\right)\qquad\text{with integer division},$$

which is exactly what appears in max_m_60().

As in the $120^\circ$ family, the code uses the direct test

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

to keep only primitive triangles.

7) Why counting primitive triangles is enough

If $(a,b,c)$ is primitive and has one of the target angles, then every multiple

$$k(a,b,c)$$

has the same angle pattern, and its perimeter is $kP_0$. Therefore one primitive triangle contributes exactly

$$\left\lfloor\frac{L}{P_0}\right\rfloor$$

copies. This explains why every counting loop in the program adds a floor-division term.

8) How the code mirrors the mathematics

Separate counters. The program maintains with_60, with_90, and with_120 independently.

Immediate equilateral count. with_60 starts from

$$\left\lfloor\frac{L}{3}\right\rfloor.$$

Three parameter scans. count_90_range(), count_120_range(), and count_60_non_eq_range() scan the corresponding $(m,n)$-lattices.

Primitive filters. The right-triangle family uses the classical coprime/opposite-parity conditions; the $60^\circ$ and $120^\circ$ families use $\gcd(m,n)=1$ plus a direct $\gcd(a,b,c)=1$ test.

Hard $m$-bounds. The helper functions max_m_90(), max_m_120(), and max_m_60() are derived exactly from the perimeter lower bounds above.

Parallel split. Threads only divide the $m$-values by residue class modulo the thread count; this changes wall-clock time, not the counted set.

Brute-force validation. The program checks

$$N(100)=84,\qquad N_{60}(100)=53,\qquad N_{90}(100)=17,\qquad N_{120}(100)=14,$$

and also compares the fast method against a direct brute-force triangle scan for $L=120,200,300$.

Complexity Analysis

Each family is an $(m,n)$-lattice scan with gcd filters, so the runtime is roughly quadratic in the relevant $m_{\max}$. The perimeter bounds cut off large useless regions early. Memory usage is $O(1)$ apart from a small amount of thread bookkeeping and the tiny brute-force table used by the checkpoints.

Problem 279 source code

C++

#include <algorithm>
#include <array>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <pthread.h>
#include <string>
#include <unistd.h>
#include <vector>

namespace {

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

struct Options {
    i64 limit = 100000000LL;
    bool run_checkpoints = true;
};

bool parse_i64_after_prefix(const std::string& arg, const std::string& prefix, i64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    i64 parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<i64>(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_i64_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 3;
}

u64 gcd3(const u64 a, const u64 b, const u64 c) {
    return std::gcd(a, std::gcd(b, c));
}

struct Counts {
    u64 with_60 = 0;
    u64 with_90 = 0;
    u64 with_120 = 0;

    u64 total() const {
        return with_60 + with_90 + with_120;
    }
};

u64 count_90_range(const i64 limit, const i64 m_start, const i64 m_end, const i64 m_step) {
    u64 out = 0;
    for (i64 m = m_start; m <= m_end; m += m_step) {
        for (i64 n = 1; n < m; ++n) {
            if (((m - n) & 1LL) == 0 || std::gcd(m, n) != 1) {
                continue;
            }
            const i64 primitive_perimeter = 2 * m * (m + n);
            out += static_cast<u64>(limit / primitive_perimeter);
        }
    }
    return out;
}

u64 count_120_range(const i64 limit, const i64 m_start, const i64 m_end, const i64 m_step) {
    u64 out = 0;
    for (i64 m = m_start; m <= m_end; m += m_step) {
        for (i64 n = 1; n < m; ++n) {
            if (std::gcd(m, n) != 1) {
                continue;
            }
            const i64 mm = m * m;
            const i64 nn = n * n;
            const i64 a = mm - nn;
            const i64 b = 2 * m * n + nn;
            const i64 c = mm + m * n + nn;
            if (gcd3(static_cast<u64>(a), static_cast<u64>(b), static_cast<u64>(c)) != 1) {
                continue;
            }
            const i64 primitive_perimeter = a + b + c;
            out += static_cast<u64>(limit / primitive_perimeter);
        }
    }
    return out;
}

u64 count_60_non_eq_range(const i64 limit, const i64 m_start, const i64 m_end, const i64 m_step) {
    u64 out = 0;
    for (i64 m = m_start; m <= m_end; m += m_step) {
        const i64 mm = m * m;
        const i64 n_max = (m - 1) / 2;
        for (i64 n = 1; n <= n_max; ++n) {
            if (std::gcd(m, n) != 1) {
                continue;
            }
            const i64 nn = n * n;
            const i64 a = mm - nn;
            const i64 c = mm - m * n + nn;

            const i64 b_a = 2 * m * n - nn;
            if (gcd3(static_cast<u64>(a), static_cast<u64>(b_a), static_cast<u64>(c)) == 1) {
                const i64 primitive_perimeter = a + b_a + c;
                out += static_cast<u64>(limit / primitive_perimeter);
            }

            const i64 b_b = mm - 2 * m * n;
            if (b_b > 0 && gcd3(static_cast<u64>(a), static_cast<u64>(b_b), static_cast<u64>(c)) == 1) {
                const i64 primitive_perimeter = a + b_b + c;
                out += static_cast<u64>(limit / primitive_perimeter);
            }
        }
    }
    return out;
}

i64 max_m_90(const i64 limit) {
    i64 m = 2;
    while (2 * m * (m + 1) <= limit) {
        ++m;
    }
    return m - 1;
}

i64 max_m_120(const i64 limit) {
    i64 m = 2;
    while (2 * m * m + 3 * m + 1 <= limit) {
        ++m;
    }
    return m - 1;
}

i64 max_m_60(const i64 limit) {
    i64 m = 2;
    while (true) {
        const __int128 mm = static_cast<__int128>(m) * static_cast<__int128>(m);
        const __int128 min_perimeter_a = 2 * mm + m - 1;
        const __int128 min_perimeter_b = static_cast<__int128>(3) * m * ((m + 1) / 2);
        if (min_perimeter_a > limit && min_perimeter_b > limit) {
            break;
        }
        ++m;
    }
    return m - 1;
}

struct WorkerCtx {
    i64 limit = 0;
    i64 m_max_90 = 0;
    i64 m_max_120 = 0;
    i64 m_max_60 = 0;
    i64 m_start = 0;
    i64 m_step = 0;
    u64 c90 = 0;
    u64 c120 = 0;
    u64 c60 = 0;
};

void* worker_main(void* ptr) {
    auto* ctx = static_cast<WorkerCtx*>(ptr);
    ctx->c90 = count_90_range(ctx->limit, ctx->m_start, ctx->m_max_90, ctx->m_step);
    ctx->c120 = count_120_range(ctx->limit, ctx->m_start, ctx->m_max_120, ctx->m_step);
    ctx->c60 = count_60_non_eq_range(ctx->limit, ctx->m_start, ctx->m_max_60, ctx->m_step);
    return nullptr;
}

unsigned choose_thread_count() {
    long cpu = sysconf(_SC_NPROCESSORS_ONLN);
    unsigned threads = (cpu > 0) ? static_cast<unsigned>(cpu) : 1U;
    if (threads > 8U) {
        threads = 8U;
    }
    if (threads == 0U) {
        threads = 1U;
    }
    return threads;
}

Counts count_by_parameterization(const i64 limit) {
    Counts counts;
    const i64 m_max_90 = max_m_90(limit);
    const i64 m_max_120 = max_m_120(limit);
    const i64 m_max_60 = max_m_60(limit);

    counts.with_60 = static_cast<u64>(limit / 3);
    const unsigned thread_count = choose_thread_count();
    if (thread_count <= 1U) {
        counts.with_90 = count_90_range(limit, 2, m_max_90, 1);
        counts.with_120 = count_120_range(limit, 2, m_max_120, 1);
        counts.with_60 += count_60_non_eq_range(limit, 2, m_max_60, 1);
        return counts;
    }

    std::vector<pthread_t> threads(thread_count);
    std::vector<WorkerCtx> ctx(thread_count);
    unsigned created = 0U;
    bool failed = false;
    for (unsigned t = 0; t < thread_count; ++t) {
        ctx[t] = WorkerCtx{limit,
                           m_max_90,
                           m_max_120,
                           m_max_60,
                           static_cast<i64>(2 + t),
                           static_cast<i64>(thread_count),
                           0ULL,
                           0ULL,
                           0ULL};
        if (pthread_create(&threads[t], nullptr, worker_main, &ctx[t]) != 0) {
            failed = true;
            break;
        }
        ++created;
    }
    for (unsigned t = 0; t < created; ++t) {
        pthread_join(threads[t], nullptr);
    }

    if (failed) {
        counts.with_90 = count_90_range(limit, 2, m_max_90, 1);
        counts.with_120 = count_120_range(limit, 2, m_max_120, 1);
        counts.with_60 += count_60_non_eq_range(limit, 2, m_max_60, 1);
        return counts;
    }

    for (const WorkerCtx& w : ctx) {
        counts.with_90 += w.c90;
        counts.with_120 += w.c120;
        counts.with_60 += w.c60;
    }

    return counts;
}

Counts count_by_bruteforce(const int limit) {
    Counts counts;

    for (int a = 1; a <= limit / 3; ++a) {
        for (int b = a; b <= (limit - a) / 2; ++b) {
            const int c_max = limit - a - b;
            for (int c = b; c <= c_max; ++c) {
                if (a + b <= c) {
                    continue;
                }

                const std::array<i64, 3> sides = {a, b, c};
                bool has_60 = false;
                bool has_90 = false;
                bool has_120 = false;

                for (int i = 0; i < 3; ++i) {
                    const i64 z = sides[static_cast<std::size_t>(i)];
                    const i64 x = sides[static_cast<std::size_t>((i + 1) % 3)];
                    const i64 y = sides[static_cast<std::size_t>((i + 2) % 3)];
                    const i64 zz = z * z;
                    const i64 xx_yy = x * x + y * y;

                    if (zz == xx_yy) {
                        has_90 = true;
                    }
                    if (zz == xx_yy - x * y) {
                        has_60 = true;
                    }
                    if (zz == xx_yy + x * y) {
                        has_120 = true;
                    }
                }

                counts.with_60 += static_cast<u64>(has_60);
                counts.with_90 += static_cast<u64>(has_90);
                counts.with_120 += static_cast<u64>(has_120);
            }
        }
    }

    return counts;
}

bool run_checkpoints() {
    {
        const Counts fast = count_by_parameterization(100);
        if (fast.total() != 84 || fast.with_60 != 53 || fast.with_90 != 17 || fast.with_120 != 14) {
            std::cerr << "Checkpoint failed at limit=100" << '\n';
            return false;
        }
    }

    for (const int limit : {120, 200, 300}) {
        const Counts brute = count_by_bruteforce(limit);
        const Counts fast = count_by_parameterization(limit);
        if (brute.with_60 != fast.with_60 || brute.with_90 != fast.with_90 ||
            brute.with_120 != fast.with_120 || brute.total() != fast.total()) {
            std::cerr << "Mismatch at limit=" << limit << ": brute(total=" << brute.total()
                      << ", 60=" << brute.with_60 << ", 90=" << brute.with_90
                      << ", 120=" << brute.with_120 << ") fast(total=" << fast.total()
                      << ", 60=" << fast.with_60 << ", 90=" << fast.with_90
                      << ", 120=" << fast.with_120 << ")" << '\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;
    }

    const Counts result = count_by_parameterization(options.limit);
    std::cout << result.total() << '\n';
    return 0;
}

Python

import math
import multiprocessing

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def gcd3(a, b, c):
    return gcd(a, gcd(b, c))

def count_90_range(limit, m_start, m_end, m_step):
    out = 0
    for m in range(m_start, m_end + 1, m_step):
        for n in range(1, m):
            if ((m - n) & 1) == 0 or gcd(m, n) != 1:
                continue
            primitive_perimeter = 2 * m * (m + n)
            out += limit // primitive_perimeter
    return out

def count_120_range(limit, m_start, m_end, m_step):
    out = 0
    for m in range(m_start, m_end + 1, m_step):
        for n in range(1, m):
            if gcd(m, n) != 1:
                continue
            mm = m * m
            nn = n * n
            a = mm - nn
            b = 2 * m * n + nn
            c = mm + m * n + nn
            if gcd3(a, b, c) != 1:
                continue
            primitive_perimeter = a + b + c
            out += limit // primitive_perimeter
    return out

def count_60_non_eq_range(limit, m_start, m_end, m_step):
    out = 0
    for m in range(m_start, m_end + 1, m_step):
        mm = m * m
        n_max = (m - 1) // 2
        for n in range(1, n_max + 1):
            if gcd(m, n) != 1:
                continue
            nn = n * n
            a = mm - nn
            c = mm - m * n + nn

            b_a = 2 * m * n - nn
            if gcd3(a, b_a, c) == 1:
                primitive_perimeter = a + b_a + c
                out += limit // primitive_perimeter

            b_b = mm - 2 * m * n
            if b_b > 0 and gcd3(a, b_b, c) == 1:
                primitive_perimeter = a + b_b + c
                out += limit // primitive_perimeter
    return out

def max_m_90(limit):
    m = 2
    while 2 * m * (m + 1) <= limit:
        m += 1
    return m - 1

def max_m_120(limit):
    m = 2
    while 2 * m * m + 3 * m + 1 <= limit:
        m += 1
    return m - 1

def max_m_60(limit):
    m = 2
    while True:
        mm = m * m
        min_perimeter_a = 2 * mm + m - 1
        min_perimeter_b = 3 * m * ((m + 1) // 2)
        if min_perimeter_a > limit and min_perimeter_b > limit:
            break
        m += 1
    return m - 1

def worker_main(args):
    limit, m_max_90, m_max_120, m_max_60, m_start, m_step = args
    c90 = count_90_range(limit, m_start, m_max_90, m_step)
    c120 = count_120_range(limit, m_start, m_max_120, m_step)
    c60 = count_60_non_eq_range(limit, m_start, m_max_60, m_step)
    return c90, c120, c60

def solve(limit=100000000):
    m_max_90 = max_m_90(limit)
    m_max_120 = max_m_120(limit)
    m_max_60 = max_m_60(limit)
    
    total_60 = limit // 3
    total_90 = 0
    total_120 = 0
    
    threads = max(1, multiprocessing.cpu_count())
    
    if threads <= 1:
        total_90 += count_90_range(limit, 2, m_max_90, 1)
        total_120 += count_120_range(limit, 2, m_max_120, 1)
        total_60 += count_60_non_eq_range(limit, 2, m_max_60, 1)
    else:
        args = []
        for t in range(threads):
            args.append((limit, m_max_90, m_max_120, m_max_60, 2 + t, threads))
            
        with multiprocessing.Pool(threads) as pool:
            results = pool.map(worker_main, args)
            
        for c90, c120, c60 in results:
            total_90 += c90
            total_120 += c120
            total_60 += c60
            
    return str(total_60 + total_90 + total_120)

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

Java

import java.util.*;
import java.util.concurrent.*;

public class Euler279 {
    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    static long gcd3(long a, long b, long c) {
        return gcd(a, gcd(b, c));
    }

    static long count90Range(long limit, long mStart, long mEnd, long mStep) {
        long out = 0;
        for (long m = mStart; m <= mEnd; m += mStep) {
            for (long n = 1; n < m; ++n) {
                if (((m - n) & 1L) == 0 || gcd(m, n) != 1L) {
                    continue;
                }
                long primitivePerimeter = 2L * m * (m + n);
                out += limit / primitivePerimeter;
            }
        }
        return out;
    }

    static long count120Range(long limit, long mStart, long mEnd, long mStep) {
        long out = 0;
        for (long m = mStart; m <= mEnd; m += mStep) {
            for (long n = 1; n < m; ++n) {
                if (gcd(m, n) != 1L) {
                    continue;
                }
                long mm = m * m;
                long nn = n * n;
                long a = mm - nn;
                long b = 2L * m * n + nn;
                long c = mm + m * n + nn;
                if (gcd3(a, b, c) != 1L) {
                    continue;
                }
                long primitivePerimeter = a + b + c;
                out += limit / primitivePerimeter;
            }
        }
        return out;
    }

    static long count60NonEqRange(long limit, long mStart, long mEnd, long mStep) {
        long out = 0;
        for (long m = mStart; m <= mEnd; m += mStep) {
            long mm = m * m;
            long nMax = (m - 1) / 2;
            for (long n = 1; n <= nMax; ++n) {
                if (gcd(m, n) != 1L) {
                    continue;
                }
                long nn = n * n;
                long a = mm - nn;
                long c = mm - m * n + nn;

                long ba = 2L * m * n - nn;
                if (gcd3(a, ba, c) == 1L) {
                    long primitivePerimeter = a + ba + c;
                    out += limit / primitivePerimeter;
                }

                long bb = mm - 2L * m * n;
                if (bb > 0 && gcd3(a, bb, c) == 1L) {
                    long primitivePerimeter = a + bb + c;
                    out += limit / primitivePerimeter;
                }
            }
        }
        return out;
    }

    static long maxM90(long limit) {
        long m = 2;
        while (2L * m * (m + 1) <= limit) {
            ++m;
        }
        return m - 1;
    }

    static long maxM120(long limit) {
        long m = 2;
        while (2L * m * m + 3L * m + 1 <= limit) {
            ++m;
        }
        return m - 1;
    }

    static long maxM60(long limit) {
        long m = 2;
        while (true) {
            // Need BigInteger or __int128 equivalent to avoid overflow, but m is around
            // 10000 for limit=1e8
            // which fits fine in 64-bit int. Let's do it safely.
            long mm = m * m;
            long minPerimeterA = 2L * mm + m - 1;
            long minPerimeterB = 3L * m * ((m + 1) / 2);
            if (minPerimeterA > limit && minPerimeterB > limit) {
                break;
            }
            ++m;
        }
        return m - 1;
    }

    public static String solve() {
        long limit = 100_000_000L;
        long mMax90 = maxM90(limit);
        long mMax120 = maxM120(limit);
        long mMax60 = maxM60(limit);

        long with60 = limit / 3;
        long with90 = 0;
        long with120 = 0;

        int threads = Math.max(1, Runtime.getRuntime().availableProcessors());

        if (threads <= 1) {
            with90 += count90Range(limit, 2, mMax90, 1);
            with120 += count120Range(limit, 2, mMax120, 1);
            with60 += count60NonEqRange(limit, 2, mMax60, 1);
        } else {
            ExecutorService executor = Executors.newFixedThreadPool(threads);
            List<Future<long[]>> futures = new ArrayList<>();

            for (int t = 0; t < threads; ++t) {
                final long mStart = 2 + t;
                final long mStep = threads;

                futures.add(executor.submit(() -> {
                    long c90 = count90Range(limit, mStart, mMax90, mStep);
                    long c120 = count120Range(limit, mStart, mMax120, mStep);
                    long c60 = count60NonEqRange(limit, mStart, mMax60, mStep);
                    return new long[] { c90, c120, c60 };
                }));
            }

            for (Future<long[]> f : futures) {
                try {
                    long[] res = f.get();
                    with90 += res[0];
                    with120 += res[1];
                    with60 += res[2];
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            executor.shutdown();
        }

        long total = with60 + with90 + with120;
        return String.valueOf(total);
    }

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