Problem 296: Angular Bisector and Tangent

Project Euler Problem 296 Solution

EulerSolve provides an optimized solution for Project Euler Problem 296, Angular Bisector and Tangent, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We are given an integer-sided triangle $ABC$ with $$BC \le AC \le AB.$$ The angle bisector of $\angle ACB$ meets the line through $B$ parallel to the tangent at $C$ to the circumcircle at a point $E$. We must count all triangles with perimeter at most $100000$ for which the segment $BE$ has integer length. Mathematical Approach 1. Side notation used by the code The program uses $$a=BC,\qquad b=CA,\qquad c=AB,$$ so the ordering condition becomes $$a\le b\le c.$$ The triangle inequalities and perimeter bound then force $$c < a+b,\qquad a+b+c\le N.$$ 2. A clean trigonometric derivation of $BE$ Let the angles of triangle $ABC$ be $A,B,C$ at the corresponding vertices. Because $CE$ is the angle bisector of $\angle C$, we have $$\angle ECB=\frac{C}{2}.$$ The line through $B$ is parallel to the tangent at $C$ to the circumcircle. By the tangent-chord theorem, the angle between that tangent and the chord $CB$ equals the angle at $A$....

Detailed mathematical approach

Problem Summary

We are given an integer-sided triangle $ABC$ with

$$BC \le AC \le AB.$$

The angle bisector of $\angle ACB$ meets the line through $B$ parallel to the tangent at $C$ to the circumcircle at a point $E$. We must count all triangles with perimeter at most $100000$ for which the segment $BE$ has integer length.

Mathematical Approach

1. Side notation used by the code

The program uses

$$a=BC,\qquad b=CA,\qquad c=AB,$$

so the ordering condition becomes

$$a\le b\le c.$$

The triangle inequalities and perimeter bound then force

$$c < a+b,\qquad a+b+c\le N.$$

2. A clean trigonometric derivation of $BE$

Let the angles of triangle $ABC$ be $A,B,C$ at the corresponding vertices. Because $CE$ is the angle bisector of $\angle C$, we have

$$\angle ECB=\frac{C}{2}.$$

The line through $B$ is parallel to the tangent at $C$ to the circumcircle. By the tangent-chord theorem, the angle between that tangent and the chord $CB$ equals the angle at $A$. Therefore, in triangle $CBE$,

$$\angle CBE = A.$$

Now apply the sine rule in triangle $CBE$:

$$\frac{BE}{\sin(C/2)}=\frac{BC}{\sin(A+C/2)}=\frac{a}{\sin(A+C/2)}.$$

$$BE=a\cdot\frac{\sin(C/2)}{\sin(A+C/2)}.$$

To simplify the denominator, use $A+B+C=\pi$:

$$A+\frac{C}{2}=\frac{\pi}{2}+\frac{A-B}{2},$$

hence

$$\sin\!\left(A+\frac C2\right)=\cos\!\left(\frac{A-B}{2}\right).$$

On the other hand, by the sine rule in triangle $ABC$,

$$a=2R\sin A,\qquad b=2R\sin B,\qquad c=2R\sin C,$$

$$a+b=2R(\sin A+\sin B)=4R\cos\!\left(\frac C2\right)\cos\!\left(\frac{A-B}{2}\right),$$

and

$$c=2R\sin C=4R\sin\!\left(\frac C2\right)\cos\!\left(\frac C2\right).$$

Dividing these gives

$$\frac{a+b}{c}=\frac{\cos((A-B)/2)}{\sin(C/2)}=\frac{\sin(A+C/2)}{\sin(C/2)}.$$

Substituting into the previous expression yields the key identity

$$BE=\frac{ac}{a+b}.$$

3. The integrality condition becomes pure divisibility

The problem asks when $BE$ is an integer. Because $a,b,c$ are integers, the identity above shows that this is equivalent to

$$a+b \mid ac.$$

This is the decisive reduction: the geometric condition disappears completely and the rest of the problem becomes arithmetic counting.

4. For fixed $a,b$, what values of $c$ are even possible?

Fix $a$ and $b$. Since $b\le c$ and the triangle inequality requires $c<a+b$, while the perimeter bound requires $c\le N-a-b$, the allowed interval is

$$b \le c \le c_{\max},\qquad c_{\max}=\min(a+b-1,\ N-a-b).$$

If $c_{\max}<b$, then no triangle exists for that pair $(a,b)$.

5. Turning divisibility into an arithmetic progression

Let

$$s=a+b,\qquad g=\gcd(a,b).$$

Because

$$\gcd(a,s)=\gcd(a,a+b)=\gcd(a,b)=g,$$

we may write

$$a=g a_1,\qquad s=g s_1,\qquad \gcd(a_1,s_1)=1.$$

The divisibility condition

$$s\mid ac$$

becomes

$$g s_1 \mid g a_1 c \quad\Longleftrightarrow\quad s_1 \mid a_1 c.$$

Since $a_1$ and $s_1$ are coprime, this is equivalent to

$$s_1 \mid c,$$

that is,

$$\frac{s}{g}\mid c.$$

So for fixed $(a,b)$, the valid values of $c$ form an arithmetic progression with step

$$d=\frac{a+b}{\gcd(a,b)}.$$

6. Closed-form counting for each pair $(a,b)$

We now only need to count multiples of $d$ inside the interval $[b,c_{\max}]$. The answer is

$$\left\lfloor\frac{c_{\max}}{d}\right\rfloor-\left\lfloor\frac{b-1}{d}\right\rfloor.$$

This replaces a full inner scan over all $c$ values by a constant-time formula.

7. Checkpoints and why they matter

The code validates two different parts of the reasoning.

Geometric checkpoint. For sample triangles such as $(3,4,5)$, $(5,5,8)$, $(7,8,9)$, the function be_from_geometry computes $BE$ directly from coordinates and checks that it matches

$$\frac{ac}{a+b}.$$

Counting checkpoint. For small perimeter limits $150,300,600$, the fast arithmetic count is compared with a brute-force loop over every admissible $c$. This confirms that the divisibility reformulation is exact.

How the Code Works

count_range loops over ordered side pairs $(a,b)$, computes $c_{\max}$, the gcd $g$, the step $d=(a+b)/g$, and adds the floor-difference count of multiples of $d$ in the allowed interval. solve_fast parallelizes only over disjoint ranges of $a$; mathematically each $(a,b)$ contributes independently. solve_bruteforce is kept only for checkpoint verification.

Complexity Analysis

The outer loops run only over $a$ and $b$. Each pair contributes constant-time arithmetic, so the running time is roughly

$$O(N^2),$$

which is a major improvement over the cubic brute-force scan over all $(a,b,c)$. Memory usage is $O(1)$ apart from thread-local counters.

Problem 296 source code

C++

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

namespace {

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

struct Options {
    int limit = 100000;
    unsigned threads = std::thread::hardware_concurrency();
    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_unsigned_after_prefix(const std::string& arg, const std::string& prefix, unsigned& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    unsigned parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10U + static_cast<unsigned>(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, "--limit=", options.limit)) {
            continue;
        }
        if (parse_unsigned_after_prefix(arg, "--threads=", options.threads)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    if (options.limit < 3) {
        return false;
    }
    if (options.threads == 0) {
        options.threads = 1;
    }
    return true;
}

long double be_from_geometry(const int a, const int b, const int c) {
    // C=(0,0), A=(b,0), B determined by side lengths.
    const long double bx = (static_cast<long double>(a) * a + static_cast<long double>(b) * b -
                            static_cast<long double>(c) * c) /
                           (2.0L * b);
    const long double by2 = static_cast<long double>(a) * a - bx * bx;
    const long double by = -std::sqrt(std::max(0.0L, by2));

    // Angle bisector at C points along unit(CA)+unit(CB).
    const long double ux = 1.0L + bx / a;
    const long double uy = by / a;

    // Tangent at C to circumcircle is perpendicular to OC.
    // Circumcenter O satisfies OA=OC and OB=OC.
    // With C at origin and A on x-axis: O=(b/2, oy).
    const long double oy =
        (bx * bx + by * by - b * bx) / (2.0L * by);  // from OB^2 = OC^2.
    const long double ox = b / 2.0L;

    // Tangent direction is perpendicular to O vector.
    const long double tx = -oy;
    const long double ty = ox;

    // Solve C + s*u = B + t*tangent, then BE = |t|*|tangent|.
    const long double det = ux * (-ty) - uy * (-tx);
    const long double rhsx = bx;
    const long double rhsy = by;

    const long double t = (ux * rhsy - uy * rhsx) / det;
    const long double tangent_len = std::sqrt(tx * tx + ty * ty);
    return std::fabsl(t) * tangent_len;
}

u64 count_range(const int limit, const int a_start, const int a_end) {
    u64 total = 0;

    for (int a = a_start; a <= a_end; ++a) {
        const int b_max = (limit - a) / 2;
        for (int b = a; b <= b_max; ++b) {
            const int s = a + b;
            const int c_max = std::min(s - 1, limit - s);
            if (c_max < b) {
                continue;
            }

            const int g = std::gcd(a, b);
            const int step = s / g;
            total += static_cast<u64>(c_max / step - (b - 1) / step);
        }
    }

    return total;
}

u64 solve_fast(const int limit, unsigned threads) {
    const int a_max = limit / 3;
    if (threads <= 1 || a_max < 5000) {
        return count_range(limit, 1, a_max);
    }

    const unsigned use_threads = std::min<unsigned>(threads, static_cast<unsigned>(a_max));
    const int chunk = (a_max + static_cast<int>(use_threads) - 1) / static_cast<int>(use_threads);

    std::vector<std::thread> pool;
    std::vector<u64> partial(use_threads, 0);
    pool.reserve(use_threads);

    for (unsigned t = 0; t < use_threads; ++t) {
        const int start = static_cast<int>(t) * chunk + 1;
        const int end = std::min(a_max, start + chunk - 1);
        if (start > end) {
            continue;
        }
        pool.emplace_back([&, start, end, t]() {
            partial[t] = count_range(limit, start, end);
        });
    }

    for (auto& th : pool) {
        th.join();
    }

    u64 total = 0;
    for (u64 part : partial) {
        total += part;
    }
    return total;
}

u64 solve_bruteforce(const int limit) {
    u64 total = 0;
    for (int a = 1; a <= limit / 3; ++a) {
        for (int b = a; b <= (limit - a) / 2; ++b) {
            const int c_max = std::min(a + b - 1, limit - a - b);
            for (int c = b; c <= c_max; ++c) {
                if ((static_cast<i64>(a) * c) % (a + b) == 0) {
                    ++total;
                }
            }
        }
    }
    return total;
}

bool run_checkpoints() {
    {
        // Geometry validation for the BE formula on a few integer triangles.
        struct Tri {
            int a;
            int b;
            int c;
        };
        const std::vector<Tri> tests = {
            {3, 4, 5},
            {5, 5, 8},
            {7, 8, 9},
            {9, 12, 14},
            {11, 13, 15},
        };

        for (const auto& tri : tests) {
            const long double be_geom = be_from_geometry(tri.a, tri.b, tri.c);
            const long double be_formula =
                static_cast<long double>(tri.a) * tri.c / static_cast<long double>(tri.a + tri.b);
            if (std::fabsl(be_geom - be_formula) > 1e-9L) {
                std::cerr << "Geometry checkpoint failed for (" << tri.a << ',' << tri.b << ','
                          << tri.c << ")" << '\n';
                return false;
            }
        }
    }

    for (int limit : {150, 300, 600}) {
        const u64 fast = solve_fast(limit, 1);
        const u64 brute = solve_bruteforce(limit);
        if (fast != brute) {
            std::cerr << "Counting checkpoint failed for limit=" << limit << ": fast=" << fast
                      << ", brute=" << brute << '\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 u64 answer = solve_fast(options.limit, options.threads);
    std::cout << answer << '\n';
    return 0;
}

Python

from __future__ import annotations

import re
import shutil
import subprocess
from pathlib import Path

ANSWER_RE = re.compile(r"answer\s*:\s*(.+)$", re.IGNORECASE)
EQUAL_RE = re.compile(r"=\s*(.+)$")


def parse_output(stdout: str) -> str:
    lines = [line.strip() for line in stdout.splitlines() if line.strip()]
    if not lines:
        return ""

    answer_candidates = []
    equal_candidates = []
    for line in lines:
        m1 = ANSWER_RE.search(line)
        if m1:
            answer_candidates.append(m1.group(1).strip())
        m2 = EQUAL_RE.search(line)
        if m2:
            equal_candidates.append(m2.group(1).strip())

    if answer_candidates:
        return answer_candidates[-1]
    if equal_candidates:
        return equal_candidates[-1]
    return lines[-1]


def solve() -> str:
    problem_id = __file__.split("Euler")[-1].split(".")[0]
    root = Path(__file__).resolve().parent.parent
    src = root / "solutionsCpp" / f"Euler{problem_id}.cpp"
    binary = root / "solutionsCpp" / f".euler{problem_id}_py_bridge"

    if not binary.exists() or src.stat().st_mtime > binary.stat().st_mtime:
        compiler = shutil.which("clang++") or shutil.which("g++")
        if not compiler:
            raise RuntimeError("No C++ compiler found (clang++/g++).")
        subprocess.check_call([compiler, "-std=c++17", "-O2", str(src), "-o", str(binary)])

    output = subprocess.check_output([str(binary)], text=True)
    parsed = parse_output(output)
    if not parsed:
        raise RuntimeError(f"Euler{problem_id} bridge produced empty output.")
    return parsed


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

Java

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

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

    static long countRange(int limit, int aStart, int aEnd) {
        long total = 0;
        for (int a = aStart; a <= aEnd; ++a) {
            int bMax = (limit - a) / 2;
            for (int b = a; b <= bMax; ++b) {
                int s = a + b;
                int cMax = Math.min(s - 1, limit - s);
                if (cMax < b)
                    continue;

                int g = gcd(a, b);
                int step = s / g;
                total += (cMax / step) - ((b - 1) / step);
            }
        }
        return total;
    }

    public static String solve() {
        int limit = 100000;
        int aMax = limit / 3;
        int threads = Runtime.getRuntime().availableProcessors();
        if (threads <= 1) {
            return String.valueOf(countRange(limit, 1, aMax));
        }

        int useThreads = Math.min(threads, aMax);
        int chunk = (aMax + useThreads - 1) / useThreads;

        ExecutorService executor = Executors.newFixedThreadPool(useThreads);
        List<Future<Long>> futures = new ArrayList<>();

        for (int t = 0; t < useThreads; ++t) {
            final int start = t * chunk + 1;
            final int end = Math.min(aMax, start + chunk - 1);
            if (start > end)
                continue;

            futures.add(executor.submit(() -> countRange(limit, start, end)));
        }

        long total = 0;
        for (Future<Long> f : futures) {
            try {
                total += f.get();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        executor.shutdown();

        return String.valueOf(total);
    }

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