Project Euler Problem 496

Solution

Answer: 2042473533769142717

Let

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

with $a,b,c\in \mathbb Z_{>0}$.

We seek all integer triangles satisfying

$$b = DI,$$

where $I$ is the incenter and $D$ is the second intersection of the angle bisector $AI$ with the circumcircle.

1. Mathematical analysis

Step 1: Express $DI$ geometrically

Since $A,I,D$ are collinear and $D$ lies on the circumcircle, use the power of a point at $I$.

The power of the incenter with respect to the circumcircle is

$$IA\cdot ID = 2Rr,$$

where $R$ is the circumradius and $r$ is the inradius.

Also,

$$IA = \frac{r}{\sin(A/2)}.$$

Hence

$$ID = \frac{2Rr}{IA} = 2R\sin(A/2).$$

The condition $AC = DI$ becomes

$$b = 2R\sin(A/2).$$

But from the sine law,

$$b = 2R\sin B.$$

Thus

$$\sin B = \sin(A/2).$$

Since the triangle angles are in $(0,\pi)$, the only valid possibility is

$$B = \frac A2.$$

So the condition is equivalent to:

$$A = 2B.$$

Step 2: Convert angle condition into a Diophantine equation

By the sine law,

$$\frac{a}{\sin A} = \frac{b}{\sin B}.$$

Since $A=2B$,

$$a = b\frac{\sin(2B)}{\sin B} = 2b\cos B.$$

Therefore

$$\cos B = \frac{a}{2b}.$$

Now

$$c = b\frac{\sin(3B)}{\sin B} = b(4\cos^2B-1).$$

Substitute $\cos B = a/(2b)$:

$$c = b\left(\frac{a^2}{b^2}-1\right) = \frac{a^2-b^2}{b}.$$

Rearranging gives the key equation:

$$a^2 = b(b+c).$$

This is the exact characterization.

Step 3: Parameterization

Let

$$g = \gcd(b,b+c).$$

Write

$$b = g u,\qquad b+c = gv,$$

with $\gcd(u,v)=1$.

Then

$$a^2 = g^2 uv.$$

Since $u$ and $v$ are coprime and their product is a square, both must be squares:

$$u=m^2,\qquad v=n^2,$$

with $\gcd(m,n)=1$.

Hence every solution is

$$\boxed{ a = gmn,\quad b = gm^2,\quad c = g(n^2-m^2) }$$

with

$$m<n<2m, \qquad \gcd(m,n)=1.$$

(The inequality $n<2m$ comes from triangle inequality / angle positivity.)

Example:

$m=2,n=3,g=1$

gives

$$(a,b,c)=(6,4,5),$$

matching the example.

Step 4: Summation formula

For fixed coprime $(m,n)$,

$$a = gmn.$$

All multiples with

$$gmn \le L$$

are allowed.

Let

$$K=\left\lfloor \frac{L}{mn}\right\rfloor.$$

Contribution of this primitive pair:

$$\sum_{g=1}^{K} gmn = mn\cdot \frac{K(K+1)}2.$$

Thus

$$F(L) = \sum_{\substack{m<n<2m\ \gcd(m,n)=1}} mn\cdot \frac{K(K+1)}2, \quad K=\left\lfloor\frac{L}{mn}\right\rfloor.$$

To evaluate efficiently for $L=10^9$, we avoid iterating over all $n$ directly and use Möbius inversion to sum coprime integers in ranges:

$$\sum_{\substack{x\le n\le y\(n,m)=1}} n.$$

This reduces runtime to a few seconds.

2. Python implementation

from math import isqrt

def F(L):
    M = isqrt(L)

    # Möbius function up to sqrt(L)
    mu = [0] * (M + 1)
    mu[1] = 1
    primes = []
    composite = [False] * (M + 1)

    for i in range(2, M + 1):
        if not composite[i]:
            primes.append(i)
            mu[i] = -1

        for p in primes:
            v = i * p
            if v > M:
                break

            composite[v] = True

            if i % p == 0:
                mu[v] = 0
                break

            mu[v] = -mu[i]

    # divisors with nonzero Möbius values
    divisors = [[] for _ in range(M + 1)]

    for d in range(1, M + 1):
        if mu[d] == 0:
            continue

        coeff = mu[d] * d

        for m in range(d, M + 1, d):
            divisors[m].append((d, coeff))

    def triangular(k):
        return k * (k + 1) // 2

    total = 0

    for m in range(1, M + 1):

        limit = min(2 * m - 1, L // m)
        if limit <= m:
            continue

        divs = divisors[m]

        # Sum of integers <= N coprime to m
        def coprime_sum(N):
            s = 0
            for d, coeff in divs:
                t = N // d
                s += coeff * (t * (t + 1) // 2)
            return s

        n = m + 1

        # Group intervals where floor(L/(m*n)) is constant
        while n <= limit:
            k = L // (m * n)
            r = min(limit, L // (m * k))

            sum_n = coprime_sum(r) - coprime_sum(n - 1)

            total += m * triangular(k) * sum_n

            n = r + 1

    return total

print(F(15))      # 45
print(F(10**9))

3. Code walkthrough

Möbius precomputation

We sieve the Möbius function up to $\sqrt L$.

This allows us to evaluate:

$$\sum_{\gcd(n,m)=1} n$$

using inclusion–exclusion:

$$\sum_{d\mid m} \mu(d)d \cdot \frac{\lfloor N/d\rfloor(\lfloor N/d\rfloor+1)}2.$$

Enumerating primitive triangles

We iterate over $m$, and for each:

$$m<n<2m.$$

Since

$$mn\le L,$$

we cap $n$ at

$$\min(2m-1,\lfloor L/m\rfloor).$$

Instead of checking every $n$, we group intervals where

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

is constant, making the algorithm fast.

Example verification

For $L=15$, the program finds exactly:

$$(6,4,5), (12,8,10), (12,9,7), (15,9,16),$$

whose sum of $BC$ values is:

$$6+12+12+15=45.$$

Correct.

4. Final verification

Geometry condition reduced cleanly to $A=2B$.
Diophantine condition parameterizes all integer solutions.
Verified against brute force for small $L$.
Reproduces the given example $F(15)=45$.

For $L=10^9$, the computation yields:

Answer: 2042473533769142717