Detailed mathematical approach

Problem Summary

Let a triangle with integer sides \(a,b,c\) have area \(A\) and perimeter \(P=a+b+c\). We want all triangles for which

$$\frac{A}{P}=k$$

is an integer. For each \(k\), let \(p(k)\) be the sum of the corresponding perimeters. The program computes

$$\sum_{k=1}^{1000} p(k),$$

but the final numeric answer is intentionally omitted here.

Mathematical Approach

1) Replace side lengths by semiperimeter gaps. Let

$$s=\frac{a+b+c}{2},\qquad x=s-a,\qquad y=s-b,\qquad z=s-c.$$

Then \(x,y,z\) are positive integers, and conversely

$$a=y+z,\qquad b=z+x,\qquad c=x+y,\qquad s=x+y+z.$$

So every integer triangle corresponds to one positive integer triple \((x,y,z)\). If we sort the sides as \(a \ge b \ge c\), then \(x \le y \le z\), which is exactly the ordering used in the code to avoid duplicates.

2) Heron's formula gives a Diophantine equation. Heron's formula is

$$A^2=s(s-a)(s-b)(s-c)=sxyz.$$

The condition \(A/P=k\) means

$$A=k(a+b+c)=2ks.$$

Squaring and cancelling one factor of \(s\) gives

$$xyz=4k^2s=4k^2(x+y+z).$$

If we define

$$n=(2k)^2=4k^2,$$

the triangle problem becomes the pure integer equation

$$xyz=n(x+y+z),\qquad x \le y \le z.$$

The perimeter of the recovered triangle is

$$P=2s=2(x+y+z),$$

which is why the program adds \(2(x+y+z)\) for each valid triple.

3) Why this is a bijection. Starting from a triangle, we get one positive triple \((x,y,z)\). Starting from a positive solution of \(xyz=n(x+y+z)\), the inverse map

$$a=y+z,\qquad b=z+x,\qquad c=x+y$$

automatically satisfies the triangle inequalities because \(x,y,z>0\). So no valid triangle is lost and no extra object is counted.

4) Solve one variable in terms of the other two. Rearranging the main equation gives

$$z=\frac{n(x+y)}{xy-n}.$$

Therefore \(xy>n\) is necessary, and once \(x\) and \(y\) are fixed there is at most one possible \(z\). The brute-force checkpoint routine in the code uses exactly this formula.

5) The key factorization for the fast algorithm. For the production algorithm, fixing \(k\) and \(x\) is enough. Starting from

$$xyz=n(x+y+z),$$

one checks that

$$(xy-n)(xz-n)=x^2yz-nx(y+z)+n^2=n(x^2+n).$$

Define

$$m=x^2+n,\qquad M=nm,\qquad u=xy-n,\qquad v=xz-n.$$

Then

$$uv=M,$$

and the original variables are recovered by

$$y=\frac{u+n}{x},\qquad z=\frac{v+n}{x}.$$

So for fixed \((k,x)\), every divisor pair \((u,v)\) of \(M\) gives a candidate, and the only remaining tests are:

$$x \mid (u+n),\qquad x \mid (v+n),\qquad y \ge x,\qquad z \ge y.$$

Because \(y \le z\) is equivalent to \(u \le v\), the code only needs divisor pairs with \(u^2 \le M\).

6) Why the bound \(x \le \sqrt{3n}\) is correct. For fixed \(x\), the function

$$f(y,z)=\frac{xyz}{x+y+z}$$

is increasing in both \(y\) and \(z\) on positive inputs. Since \(y,z \ge x\), the smallest possible value is at \(y=z=x\), so

$$n=f(y,z)\ge \frac{x^3}{3x}=\frac{x^2}{3}.$$

Hence

$$x \le \sqrt{3n}.$$

This is exactly the outer bound used by both the fast solver and the brute-force verifier.

7) The brute-force upper bound for \(y\). In the verifier, the extra condition \(z \ge y\) and the formula for \(z\) imply

$$\frac{n(x+y)}{xy-n}\ge y,$$

which rearranges to

$$xy^2-2ny-nx \le 0.$$

Solving this quadratic inequality yields

$$y \le \frac{n+\sqrt{n(n+x^2)}}{x},$$

which is the exact bound used in the checkpoint routine.

Worked Examples

Example 1: \(k=1\). Then \(n=4\). Take \(x=2\). We get

$$M=n(x^2+n)=4(4+4)=32.$$

Choose the divisor pair \((u,v)=(4,8)\). Then

$$y=\frac{4+4}{2}=4,\qquad z=\frac{8+4}{2}=6.$$

So \((x,y,z)=(2,4,6)\), which gives the triangle

$$a=y+z=10,\qquad b=z+x=8,\qquad c=x+y=6.$$

Its semiperimeter is \(s=12\), its area is \(\sqrt{12\cdot 2\cdot 4\cdot 6}=24\), and its perimeter is \(24\). Therefore \(A/P=1\), exactly as required.

Example 2: \(k=2\). Then \(n=16\). The triple \((x,y,z)=(6,7,8)\) satisfies

$$6\cdot 7\cdot 8 = 16(6+7+8)=336.$$

The corresponding sides are

$$a=15,\qquad b=14,\qquad c=13,$$

so we recover the classical \(13\)-\(14\)-\(15\) triangle. Its perimeter is \(42\), its area is \(84\), and \(84/42=2\).

Why the Code Is Correct

The code first chooses \(k\), hence \(n=(2k)^2\). It then loops over all admissible \(x\), factors

$$M=n(x^2+n),$$

generates all divisors of \(M\), keeps only \(u\) with \(u^2 \le M\), reconstructs \(y\) and \(z\), and accepts exactly the candidates that satisfy the divisibility and ordering constraints. By the derivation above, every accepted candidate is a valid triangle, and every valid triangle appears exactly once.

Checks and Complexity

The file contains two explicit checkpoints. The fast method and the brute-force method both give

$$\sum_{k \le 5} p(k)=140098,\qquad \sum_{k \le 10} p(k)=3781786.$$

For complexity, the expensive part is factoring \(m=x^2+n\) and enumerating divisors of \(M=n(x^2+n)\). The SPF sieve is built up to

$$4(2K)^2,$$

because \(x^2 \le 3n\) implies \(m=x^2+n \le 4n\). In practice this makes each factorization cheap, and divisor enumeration is far smaller than brute forcing all \((y,z)\).

Further Reading

1. Problem page: https://projecteuler.net/problem=283
2. Heron's formula: https://en.wikipedia.org/wiki/Heron%27s_formula
3. Diophantine equations: https://en.wikipedia.org/wiki/Diophantine_equation