Project Euler Problem 223

Project Euler Problem 223

Solution

Answer: 61614848

Let

$$a^2+b^2=c^2+1, \qquad a\le b\le c$$

with perimeter

$$a+b+c\le 25{,}000{,}000.$$

We want to count all integer-sided “barely acute” triangles.

1. Mathematical analysis

Rearrange the defining equation:

$$a^2+b^2=c^2+1$$

as

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

Define

$$x=c-b,\qquad y=c+b.$$

Then

$$xy=a^2-1.$$

Since

$$b=\frac{y-x}{2},\qquad c=\frac{y+x}{2},$$

we require:

1. $x,y$ have the same parity (so $b,c$ are integers),
2. $x>0$,
3. $a\le b$, i.e.

$$a \le \frac{y-x}{2}$$

which becomes

$$y-x\ge 2a.$$

Also the perimeter condition becomes

$$a+b+c=a+y\le N,$$

where $N=25{,}000{,}000$.

So for each fixed $a$, we are counting divisors $x\mid(a^2-1)$ such that

$$x\le y=\frac{a^2-1}{x},$$

$$\frac{a^2-1}{x}-x\ge 2a,$$

and

$$a+\frac{a^2-1}{x}\le N.$$

Because $y=(a^2-1)/x$, the constraints become:

Upper bound on $x$

From $y-x\ge 2a$:

$$\frac{a^2-1}{x}-x\ge 2a.$$

Multiply by $x$:

$$a^2-1\ge x^2+2ax.$$

Rearrange:

$$(x+a)^2\le 2a^2-1.$$

Hence

$$x\le \sqrt{2a^2-1}-a.$$

Lower bound on $x$

From perimeter:

$$a+\frac{a^2-1}{x}\le N$$

so

$$x\ge \frac{a^2-1}{N-a}.$$

Thus, for each $a$, we count divisors $x$ of $a^2-1$ lying in the interval

$$\left\lceil \frac{a^2-1}{N-a} \right\rceil \le x\le \left\lfloor \sqrt{2a^2-1}-a \right\rfloor,$$

with parity condition $x+y$ even.

Special case $a=1$

If $a=1$,

$$1+b^2=c^2+1 \Rightarrow b=c.$$

So every triangle $(1,b,b)$ works provided

$$1+2b\le N.$$

That contributes

$$\left\lfloor\frac{N-1}{2}\right\rfloor$$

solutions.

---

2. Python implementation

from math import isqrt

N = 25_000_000
A_MAX = N // 3 + 1

def build_spf(limit):
    """Smallest prime factor sieve."""
    spf = list(range(limit + 1))

    for i in range(2, isqrt(limit) + 1):
        if spf[i] == i:  # i is prime
            for j in range(i * i, limit + 1, i):
                if spf[j] == j:
                    spf[j] = i

    return spf

spf = build_spf(A_MAX + 1)

# Special case a = 1
count = (N - 1) // 2

for a in range(2, A_MAX + 1):
    n = a * a - 1

    # Bounds on divisor x
    lower = (n + (N - a) - 1) // (N - a)
    upper = isqrt(2 * a * a - 1) - a

    # Factorise (a-1)(a+1)
    factors = {}

    for z in (a - 1, a + 1):
        while z > 1:
            p = spf[z]
            e = 0

            while z % p == 0:
                z //= p
                e += 1

            factors[p] = factors.get(p, 0) + e

    factor_items = list(factors.items())

    # Enumerate divisors <= upper
    stack = [(0, 1)]

    while stack:
        idx, cur = stack.pop()

        if idx == len(factor_items):
            if cur >= lower:
                y = n // cur

                # Same parity condition
                if ((cur + y) & 1) == 0:
                    count += 1
        else:
            p, e = factor_items[idx]
            value = 1

            for _ in range(e + 1):
                nxt = cur * value

                if nxt <= upper:
                    stack.append((idx + 1, nxt))
                else:
                    break

                value *= p

print(count)

---

3. Code walkthrough

SPF sieve

We precompute the smallest prime factor for every integer up to

$$\frac{N}{3}$$

since $a \le N/3$.

This allows very fast factorization of $a-1$ and $a+1$.

Loop over $a$

For each $a$:

• compute

$$n=a^2-1$$

• derive valid divisor interval $[L,U]$,
• factor

$$n=(a-1)(a+1),$$

• generate divisors $x$ of $n$ up to $U$,
• check parity and perimeter constraints.

Each valid divisor corresponds to exactly one triangle.

Small sanity check

For perimeter $\le 100$, the method finds 72 triangles, including:

$$(4,7,8), \quad (5,5,7), \quad (8,9,12), \quad (29,29,41),$$

and the infinite family

$$(1,b,b).$$

This matches brute force enumeration.

---

4. Final verification

The result is:

• positive and of plausible magnitude for perimeter $25$ million,
• larger than the count for smaller bounds by roughly linear growth,
• obtained via an exact divisor-counting algorithm (not probabilistic or approximate),
• verified against brute force for small limits.

Answer: 61614848