Problem 257: Angular Bisectors

Project Euler Problem 257 Solution

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

Problem Summary Let $a\le b\le c$ be the side lengths of a nondegenerate integer triangle $ABC$, so its perimeter is $$p=a+b+c.$$ As in the problem statement, the angle bisectors cut the sides at points $E,F,G$, and we are interested in the area ratio $$\frac{[ABC]}{[AEG]}.$$ We must count all integer-sided triangles with $$a+b+c\le P$$ for which that ratio is an integer. The final count for the full Euler limit is intentionally omitted here. Mathematical Approach 1. Converting the Geometry into an Arithmetic Ratio The code does not work directly with angles or areas. It first turns the geometry into a pure arithmetic condition. Let $E$ be the point where the bisector at $A$ meets $BC$, and let $G$ be the point where the bisector at $B$ meets $AC$. By the angle bisector theorem, $$\frac{BE}{EC}=\frac{AB}{AC}=\frac{c}{b},\qquad \frac{AG}{GC}=\frac{AB}{BC}=\frac{c}{a}.$$ Because $BC=a$ and $AC=b$, this gives $$EC=\frac{ab}{b+c},\qquad AG=\frac{bc}{a+c}.$$ Now compare areas in two stages....

Detailed mathematical approach

Problem Summary

An integer-sided triangle $ABC$ has the sides $a\le b\le c$, where $a=BC$, $b=CA$ and $c=AB$. The bisectors of its three angles meet the sides in the points $E$, $F$ and $G$, and the segments $EF$, $EG$ and $FG$ cut $ABC$ into the four triangles $AEG$, $BFE$, $CGF$ and $EFG$. The statement notes that the area of $ABC$ divided by the area of each of them is rational, and that for some triangles some or all of these ratios are integers. Writing $[XYZ]$ for the area of a triangle $XYZ$, we must count the triangles with perimeter $a+b+c\le100\,000\,000$ for which $[ABC]/[AEG]$ is an integer. ^[1] A triangle is a triple of whole numbers $a\le b\le c$ with $a+b\gt c$, so congruent triangles count once. We write $P$ for the bound on the perimeter and $N(P)$ for the number of such triangles. The statement gives no checkpoints; a direct search gives $N(40)=16$, $N(100)=46$ and $N(300)=160$.

The whole solution in one sentence: the ratio equals $(a+b)(a+c)/(bc)$, which lies between $1$ and $4$, so it can only be $2$, $3$ or $4$; the value $4$ means an equilateral triangle, and the values $2$ and $3$ lead to equations whose solutions are the multiples of explicit smallest triangles, built from two coprime integers $x$ and $y$, so we only have to count how many multiples of each smallest triangle fit within the perimeter limit.

Mathematical Approach

We first turn the geometry into a formula in the three sides, then show that the ratio can take only three integer values, and finally solve the two equations that remain with the help of prime factorisations.

1. Where the three points lie

Near the corner $A$, the triangle $ABC$ is covered by $AEG$ alone, the only small triangle with the vertex $A$, so the sides of $AEG$ at $A$ run along $AB$ and $AC$, and $E$ and $G$ lie one on each of these two sides. In the same way $E$ and $F$ lie one on each of the sides $BA$ and $BC$. A point of $AC$ that also lies on $BA$ or $BC$ is $A$ or $C$, and $E$ is neither, so $E$ lies on $AB$, $G$ on $AC$ and $F$ on $BC$: $E$, $F$ and $G$ are the points where the bisectors from $C$, $A$ and $B$ meet the opposite sides.

The angle bisector theorem says that the bisector from a vertex divides the opposite side in the ratio of the two sides that meet at that vertex. ^[2] For the bisector from $C$ this gives $AE:EB=CA:CB=b:a$, and for the bisector from $B$ it gives $AG:GC=BA:BC=c:a$. Since $AB=c$ and $AC=b$,

$$AE=\frac{bc}{a+b},\qquad AG=\frac{bc}{a+c}.$$

2. The area ratio

The area of a triangle is half the product of two sides times the sine of the angle between them. ^[3] The triangles $AEG$ and $ABC$ have the same angle at $A$, so the sine cancels in the quotient of their areas:

$$\begin{aligned}\frac{[AEG]}{[ABC]}&=\frac{AE}{AB}\cdot\frac{AG}{AC}\\&=\frac{b}{a+b}\cdot\frac{c}{a+c}.\end{aligned}$$

The quantity of the problem is therefore

$$R=\frac{[ABC]}{[AEG]}=\frac{(a+b)(a+c)}{bc}.$$

For the sides $4$, $5$, $6$ this gives $R=9\cdot10/(5\cdot6)=3$, an integer, and for $3$, $4$, $5$ it gives $R=7\cdot8/(4\cdot5)=14/5$. The same argument at $B$ and at $C$ gives $(a+b)(b+c)/(ac)$ for $BFE$ and $(a+c)(b+c)/(ab)$ for $CGF$, and the inner triangle $EFG$, the incentral triangle of $ABC$, has $2abc/\bigl((a+b)(b+c)(c+a)\bigr)$ times the area of $ABC$, ^[4] so all four ratios are rational, as the statement says.

3. Only the values 2, 3 and 4

Dividing each bracket of the numerator by one factor of the denominator gives

$$R=\Bigl(1+\frac ab\Bigr)\Bigl(1+\frac ac\Bigr).$$

Because $a\le b\le c$, the fractions $a/b$ and $a/c$ are positive and at most $1$, so each bracket is greater than $1$ and at most $2$, and $1\lt R\le4$. An integer ratio is therefore $2$, $3$ or $4$, and we write $k$ for it. The value $k=4$ needs both brackets equal to $2$, that is, $a=b=c$. So the triangles with $k=4$ are the equilateral triangles $(s,s,s)$, and $\lfloor P/3\rfloor$ of them have $3s\le P$. Multiplying all three sides by the same number $d$ does not change $R$, so the multiples $(da,db,dc)$ of a solution are solutions with the same $k$.

4. Small cases

A direct search through all triangles with perimeter at most $100$ finds the $33$ equilateral ones and $13$ others, so $N(100)=46$. Sorted by perimeter within each value of $k$, the others are:

$k=3$: $(4,5,6)$, $(8,10,12)$, $(12,15,18)$, $(15,20,21)$, $(16,20,24)$, $(20,25,30)$, $(20,22,35)$, $(21,24,35)$, $(24,30,36)$ and $(24,28,39)$;
$k=2$: $(6,14,15)$, $(12,28,30)$ and $(15,33,40)$.

Seven of them are not multiples of a smaller solution: $(4,5,6)$, $(6,14,15)$, $(15,20,21)$, $(20,22,35)$, $(21,24,35)$, $(15,33,40)$ and $(24,28,39)$, with the perimeters $15$, $35$, $56$, $77$, $80$, $88$ and $91$. All of them have $a\lt b\lt c$; the next sections find the formulas behind them. The same search gives $N(60)=26$, $N(150)=72$ and $N(200)=100$.

5. Two products

Let $k=2$ or $k=3$. Expanding $(a+b)(a+c)=k\,bc$ gives $(k-1)\,bc=a^2+a(b+c)$. We multiply both sides by $k-1$ and add $a^2-(k-1)\,a(b+c)$ to both sides; the right side becomes $k\,a^2$, and the left side factors:

$$\begin{aligned}&\bigl((k-1)\,b-a\bigr)\bigl((k-1)\,c-a\bigr)\\&\qquad=k\,a^2.\end{aligned}$$

So with $U=(k-1)\,b-a$ and $V=(k-1)\,c-a$ the condition reads

$$UV=k\,a^2.$$

For $k=2$ this reads $(b-a)(c-a)=2a^2$, and for $k=3$ it reads $(2b-a)(2c-a)=3a^2$. For $(6,14,15)$ we get $U=8$, $V=9$ and $UV=72=2\cdot6^2$; for $(4,5,6)$ we get $U=6$, $V=8$ and $UV=48=3\cdot4^2$. Since $b\ge a$, we have $U\ge(k-2)\,a\ge0$, and $UV\gt0$ makes $U$ positive; $b\le c$ gives $U\le V$. Every step can be reversed, so conversely positive integers $U\le V$ with $UV=k\,a^2$ give a solution with $b=(U+a)/(k-1)$ and $c=(V+a)/(k-1)$, provided these are whole numbers that form a triangle with $a\le b$.

6. Splitting the product into squares

Let $g=\gcd(U,V)$ be the greatest common divisor of $U$ and $V$, and write $U=gs$ and $V=gt$. Then $s$ and $t$ are coprime, that is, their only common positive divisor is $1$, because $g$ is the greatest common divisor; and $g^2st=k\,a^2$. Every integer greater than $1$ has a prime factorisation that is unique up to the order of the factors, ^[5] so we may compare how often a prime $p$ occurs on the two sides: if it occurs $e$ times in $g$ and $f$ times in $a$, then $2e\le2f+1$, because the prime $k$ adds at most one factor; hence $e\le f$, and $g$ divides $a$. With $a=gh$ the equation becomes

$$st=k\,h^2,\qquad\gcd(s,t)=1.$$

The prime $k$ divides the product $st$, so by Euclid's lemma it divides $s$ or $t$, ^[6] but not both, because they are coprime. Suppose that $k$ divides $t$, and write $t=kt'$. Then $st'=h^2$ with coprime $s$ and $t'$. A positive integer is a square exactly when every prime occurs in it an even number of times; ^[7] each prime of $h^2$ occurs in only one of $s$ and $t'$, and there an even number of times, so both are squares: $s=x^2$ and $t'=y^2$ with coprime $x$ and $y$, and $h=xy$. Moreover $k$ does not divide $x$, because it does not divide $s$. If $k$ divides $s$ instead, the same argument gives $s=kx^2$ and $t=y^2$, where $k$ does not divide $y$.

For $(6,14,15)$: $g=\gcd(8,9)=1$, and the factor $2$ lies in $s=8=2\cdot2^2$, while $t=9=3^2$, so $x=2$ and $y=3$. For $(4,5,6)$ with $k=3$: $g=\gcd(6,8)=2$, $s=3=3\cdot1^2$ and $t=4=2^2$, so $x=1$ and $y=2$. For $(15,20,21)$ with $k=3$: $U=25$, $V=27$, $g=1$, and the factor $3$ lies in $t=27=3\cdot3^2$, so $x=5$ and $y=3$.

7. The two families

Family A collects the solutions in which $k$ divides $t$: $U=gx^2$, $V=kgy^2$ and $a=gxy$. Then $b=(U+a)/(k-1)$ and $c=(V+a)/(k-1)$ give

$$\begin{aligned}a&=gxy,\\ b&=\frac{g\,x(x+y)}{k-1},\\ c&=\frac{g\,y(x+ky)}{k-1},\end{aligned}$$

with the perimeter $g(x+y)(x+ky)/(k-1)$, where $x$ and $y$ are coprime and $k$ does not divide $x$. Family B collects the solutions in which $k$ divides $s$: $U=kgx^2$, $V=gy^2$, and

$$\begin{aligned}a&=gxy,\\ b&=\frac{g\,x(kx+y)}{k-1},\\ c&=\frac{g\,y(x+y)}{k-1},\end{aligned}$$

with the perimeter $g(x+y)(kx+y)/(k-1)$, where $x$ and $y$ are coprime and $k$ does not divide $y$. For $k=2$ the denominators are $1$, and the conditions say that $x$ is odd in family A and $y$ is odd in family B; for $k=3$ they say that $x$, respectively $y$, is not a multiple of $3$. So the examples $(6,14,15)$ and $(4,5,6)$ of Section 6 belong to family B, and $(15,20,21)$ belongs to family A.

8. The inequalities

The conditions $a\le b\le c$ and $a+b\gt c$ become conditions on $x$ and $y$. From $(k-1)\,b=U+a$ and $(k-1)\,c=V+a$ we get: $b\le c$ exactly when $U\le V$; $a\le b$ exactly when $(k-2)\,a\le U$; and $a+b\gt c$ exactly when $(k-1)\,a+U-V\gt0$. In family A, $U\le V$ means $x^2\le ky^2$, and equality is impossible, because $ky^2$ contains the prime $k$ an odd number of times and so is not a square. ^[7] After division by $g$, the triangle inequality becomes

$$\begin{aligned}&(k-1)\,xy+x^2-ky^2\\&\qquad=(x-y)(x+ky)\gt0,\end{aligned}$$

that is, $x\gt y$, and then $(k-2)\,y\le x$ holds as well, because $k-2\le1$. So family A needs $y\lt x\lt\sqrt k\,y$. In family B the three conditions become $kx^2\lt y^2$, $(kx-y)(x+y)\gt0$ and $(k-2)\,y\le kx$, so family B needs $\sqrt k\,x\lt y\lt kx$. In both families $b\lt c$. Equality $a=b$ would mean $U=(k-2)\,a$, which is impossible for $k=2$ because $U\gt0$, and for $k=3$ needs $x=y$ in family A or $y=3x$ in family B, which the ranges exclude. So every solution with $k=2$ or $k=3$ has $a\lt b\lt c$, as observed in Section 4, and an isosceles triangle with an integer ratio is equilateral.

9. Whole side lengths for k = 3

For $k=2$ every $g\ge1$ gives whole numbers. For $k=3$ the sides $b$ and $c$ are halves, and $x$ and $y$ are not both even. If both are odd, then $x+y$, $x+3y$ and $3x+y$ are even, and every $g$ works. If one of them is even, the other one is odd. The numerators are $x(x+y)$ and $y(x+3y)$ in family A and $x(3x+y)$ and $y(x+y)$ in family B, and the one whose first factor is the odd variable is a product of two odd numbers. Then $g$ must be even. For example, $(x,y)=(1,2)$ in family B gives $b=5g/2$, so $g=2$ is the smallest choice, the triangle $(4,5,6)$, while $(5,3)$ in family A allows $g=1$.

10. Every triangle is counted exactly once

A triangle with $k=2$ or $k=3$ determines $U$, $V$ and $g$, and Section 6 tells whether the factor $k$ lies in $s$ or in $t$ and returns $x$ and $y$; so the triangle belongs to one family, with one pair $(x,y)$ and one $g$. Conversely, coprime $x$ and $y$ that satisfy the conditions of a family, with an allowed $g$, give through Section 7 a triangle with ratio $k$, since the algebra of Section 5 can be reversed. In family A its $U=gx^2$ and $V=kgy^2$ have the greatest common divisor $g\gcd(x^2,ky^2)=g$, because $x$ is coprime to $y$ and not divisible by $k$, so the triangle leads back to the same $g$, $x$ and $y$; family B works the same way. So the solutions with $k=2$ or $k=3$ correspond one to one to these choices, and as a triangle has only one ratio, nothing is counted twice.

11. The counting formula

Fix a family and a pair $(x,y)$. Multiplying a triangle by $d$ multiplies $U$, $V$ and $g$ by $d$ and keeps $s$, $t$, $x$ and $y$. So the triangles of the pair are exactly the multiples of the one with the smallest allowed $g$, which is $g=1$, or $g=2$ when $k=3$ and $x$ and $y$ are not both odd. We call it $T(x,y)$ and write $p_0$ for its perimeter:

$k=2$: $p_0=(x+y)(x+2y)$ in family A and $p_0=(x+y)(2x+y)$ in family B;
$k=3$: $p_0=(x+y)(x+3y)$ in family A and $p_0=(x+y)(3x+y)$ in family B, halved when $x$ and $y$ are both odd.

The same argument shows that $T(x,y)$ is primitive: if its sides had a common factor $d\ge2$, it would be $d$ times a solution of the same pair with a smaller allowed $g$. The multiples of $T(x,y)$ with perimeter at most $P$ are the triangles $d\,T(x,y)$ with $1\le d\le\lfloor P/p_0\rfloor$. Therefore

$$N(P)=\Bigl\lfloor\frac P3\Bigr\rfloor+\sum_{(x,y)}\Bigl\lfloor\frac{P}{p_0(x,y)}\Bigr\rfloor,$$

where the sum runs over the pairs of all four families with $p_0\le P$. A pair may occur in two families, with different $p_0$: $(5,4)$ gives $(20,45,52)$ for $k=2$ and $(40,45,68)$ for $k=3$, both in family A.

12. Worked example: N(100) = 46

Equilateral triangles: $\lfloor100/3\rfloor=33$.
$k=2$, family B: $(2,3)$ gives $(6,14,15)$ with $p_0=5\cdot7=35$, so $2$ triangles; $(3,5)$ gives $(15,33,40)$ with $p_0=8\cdot11=88$, so $1$. Family A starts with $(5,4)$, the triangle $(20,45,52)$ with $p_0=9\cdot13=117\gt100$.
$k=3$, family B: $(1,2)$ gives $(4,5,6)$ with $p_0=3\cdot5=15$, so $6$ triangles; $(2,5)$ gives $(20,22,35)$ with $p_0=7\cdot11=77$; $(3,7)$, both odd, gives $(21,24,35)$ with $p_0=10\cdot16/2=80$.
$k=3$, family A: $(5,3)$, both odd, gives $(15,20,21)$ with $p_0=8\cdot14/2=56$; $(4,3)$ gives $(24,28,39)$ with $p_0=7\cdot13=91$.

Every other pair has $p_0\gt100$. So $N(100)=33+3+10=46$, with $2+1=3$ triangles for $k=2$ and $6+1+1+1+1=10$ for $k=3$, in agreement with Section 4, whose $13$ triangles are exactly the multiples $d\,T(x,y)$.

13. Two halves of one family

For a solution with ratio $k$, put $r=(k-1)\,b/a-1$. Family A gives $b/a=(x+y)/((k-1)y)$ and so $r=x/y$; family B gives $b/a=(kx+y)/((k-1)y)$ and $r=kx/y$. In both cases $1\lt r\lt\sqrt k$ by Section 8, and $r$ is in lowest terms, with a numerator divisible by $k$ exactly in family B. Conversely, for a fraction $X/Y$ in lowest terms with $1\lt X/Y\lt\sqrt k$, the pair $(x,y)=(X,Y)$ lies in family A if $k$ does not divide $X$, and otherwise $(x,y)=(X/k,Y)$ lies in family B, where $k$ cannot divide $Y$ because $X$ and $Y$ are coprime; in both cases the ranges of Section 8 hold. So the two families are the two halves of one: the primitive solutions with ratio $k$ correspond one to one to the fractions in lowest terms between $1$ and $\sqrt k$. For $(6,14,15)$, $r=14/6-1=4/3$, and for $(4,5,6)$, $r=2\cdot5/4-1=3/2$. This gives a second, independent way to list the solutions, used as a check below.

How the Code Works

The C++ program ^[8] accepts two optional arguments: --perimeter= followed by a number replaces the default limit $P=10^8$, and --skip-checkpoints turns the self-check off. Otherwise run_checkpoints first compares, for the perimeters $40$, $60$, $100$, $150$, $200$ and $300$, the fast count with brute_count, a triple loop over all triangles with perimeter at most $P$ that tests whether $bc$ divides $(a+b)(a+c)$, the formula of Section 2, and stops the program on a mismatch. Then the program prints the value of count_valid_triangles.

count_valid_triangles starts with $\lfloor P/3\rfloor$ for the equilateral triangles, sets max_var to $\lfloor\sqrt P\rfloor+2$, the upper end of every outer loop, and adds the results of four counters, one per family and value of $k$. count_case_k2_a lets $y$ run up to max_var and $x$ from $y+1$ to floor_sqrt(2*y*y), the largest $x$ with $x^2\le2y^2$; as $2y^2$ is never a square, this is the range $y\lt x\lt\sqrt2\,y$ of Section 8. It skips pairs with $\gcd(x,y)\ne1$ or even $x$, computes base, which is $p_0=(x+y)(x+2y)$, and adds perimeter_limit / base, that is $\lfloor P/p_0\rfloor$, if the base does not exceed $P$. count_case_k2_b lets $x$ run over the outer range and $y$ from ceil_sqrt(2*x*x) to $2x-1$, requires an odd $y$ and uses $p_0=(x+y)(2x+y)$.

count_case_k3_a and count_case_k3_b do the same for $k=3$, with the ranges $y\lt x\lt\sqrt3\,y$ and $\sqrt3\,x\lt y\lt3x$ and the test that $x$, respectively $y$, is not a multiple of $3$. They compute base_num, the number $B=(x+y)(x+3y)$ or $B=(x+y)(3x+y)$, and g_max, the largest $g$ with $gB/2\le P$, that is $\lfloor2P/B\rfloor$. The flag odd_g_valid is true when both numerators of Section 9 are even for $g=1$, that is, when $x$ and $y$ are both odd; then all g_max values of $g$ count, and otherwise only the even ones, g_max / 2 of them. By the rule for nested divisions, $\lfloor\lfloor2P/B\rfloor/2\rfloor=\lfloor P/B\rfloor$, ^[9] so in both cases the added number is the term $\lfloor P/p_0\rfloor$ of Section 11.

floor_sqrt corrects the floating-point square root in single steps until it is exact, and ceil_sqrt adds $1$ unless the argument is a perfect square. 64-bit integers are more than enough: the largest product formed, $(x+y)(3x+y)$ with $x\le10002$ and $y\lt3x$, stays below $2.5\cdot10^9$.

The Python and Java versions contain the same four counters, except that each counter receives a range of its outer variable and solve adds the results for consecutive ranges covering $1,\dots,$max_var. Both test the parity, or the divisibility by $3$, before the gcd, whereas the C++ version computes the gcd first. Python uses math.gcd and the exact integer square root math.isqrt, and its solve takes the limit as an argument with the default $10^8$; Java uses its own loop of Euclid's algorithm, the same corrected square roots as the C++ version and long arithmetic, with the limit fixed at $10^8$. Neither runs checkpoints.

Complexity and Verification

Let $m=\lfloor\sqrt P\rfloor+2=10002$ be the value of max_var. Because $ku^2$ is never a square, $\lceil\sqrt k\,u\rceil=\lfloor\sqrt k\,u\rfloor+1$ for every $u\ge1$, and the inner ranges of the two counters of each $k$ fit together: for the same value $u$ of the outer variable, the two counters for $k=2$ visit $u-1$ pairs together, and the two counters for $k=3$ visit $2u-1$. In total the program visits exactly

$$\frac{m(m-1)}{2}+m^2=150\,055\,005$$

pairs, about $1.5P$. The C++ version computes a gcd for every one of them, the Python and Java versions only for the $91\,706\,671$ pairs that pass the parity or divisibility test, and Euclid's algorithm never needs more division steps than five times the number of decimal digits of the smaller number. ^[10] Counting each operation on these small numbers as one step, the running time is therefore $O(P\log P)$, the memory is constant, and the C++ program finishes in about a second on a desktop computer.

Most of this work is wasted: only $6\,759\,015$ visited pairs have $p_0\le P$ and contribute. In family A, $x\gt y$ gives $p_0\gt6y^2$ for $k=2$ and $p_0\gt4y^2$ for $k=3$, and in family B, $y\gt x$ gives $p_0\gt6x^2$ and $p_0\gt4x^2$. So a contributing pair has $4u^2\lt P$ for its outer variable $u$, that is $u\lt\sqrt P/2=5000$, about half of $m$; the largest value that occurs is $4997$. Moreover, an inner loop goes on after its base has passed the limit, although the base only grows along the loop. Replacing the continue after the perimeter test by a break would cut the visits to $20\,313\,039$, about a seventh, with the same result.

Unless told to skip them, the C++ program checks itself against the brute force for six perimeters; the correct values are $N(40)=16$, $N(60)=26$, $N(100)=46$, $N(150)=72$, $N(200)=100$ and $N(300)=160$. For this article, a separate brute force over all triangles with perimeter at most $10\,000$ agrees with the formula of Section 11 for every $P\le10\,000$, and it confirms that the $676$ triangles $T(x,y)$ with $p_0\le10\,000$ are distinct primitive solutions with $a\lt b\lt c$. Two independent counts agree with the C++ program for $P=10^3,10^4,\dots,10^8$: one enumerates, for every $a$, the divisors $U$ of $2a^2$ and of $3a^2$ and tests the conditions of Section 5 directly, without the lemma of Section 6 or the parity rule of Section 9; the other lists the fractions of Section 13 and divides each triangle by the greatest common divisor of its sides. For example, $N(10^6)=1\,078\,857$, of which $333\,333$ triangles are equilateral, $249\,552$ have $k=2$ and $495\,972$ have $k=3$. The Python and Java programs print the same count as the C++ program for $P=10^8$. These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The formula for the area ratio, the reduction to $UV=k\,a^2$, the four families with their inequalities and parity rule, the correspondence with fractions and the operation counts are derived explicitly in this article.

Project Euler 257 — Angular Bisectors. The official statement defines the integer-sided triangle ABC with a ≤ b ≤ c (AB = c, BC = a, AC = b), the points E, F and G where the angle bisectors meet the sides and the four triangles AEG, BFE, CGF and EFG, and asks how many triangles with perimeter ≤ 100 000 000 have an integral ratio area(ABC)/area(AEG).
Wikipedia — Angle bisector theorem. If the bisector of the angle at A meets BC in D, then BD : DC = AB : AC.
Wikipedia — Area of a triangle. The section on two sides and the included angle gives T = ½ab sin γ.
MathWorld — Incentral Triangle. The incentral triangle is the cevian triangle with respect to the incenter, whose vertices are the feet of the angle bisectors; its area is 2abcΔ/((a + b)(b + c)(c + a)) for a reference triangle of area Δ.
Wikipedia — Fundamental theorem of arithmetic. Every integer greater than 1 is a product of primes, unique up to the order of the factors, so Section 6 can compare the exponents of a prime in two numbers.
Wikipedia — Coprime integers. The article defines coprime integers and states Euclid's lemma: a prime that divides a product bc divides b or c.
Wikipedia — Square number. A positive integer is a square exactly when all exponents in its prime factorisation are even, as used in Sections 6 and 8.
C++ — Euler257.cpp. The linked immutable C++ revision contains count_case_k2_a, count_case_k2_b, count_case_k3_a, count_case_k3_b, count_valid_triangles, brute_count and run_checkpoints. It is the implementation record for this article.
Wikipedia — Floor and ceiling functions. The section on nested divisions states ⌊⌊x/m⌋/n⌋ = ⌊x/(mn)⌋ for a positive integer n, used here with x = 2P, m = B and n = 2.
Wikipedia — Euclidean algorithm. The algorithm finds the greatest common divisor by repeated division with remainder, and by Lamé's theorem of 1844 it never needs more steps than five times the number of decimal digits of the smaller number.

Problem 257 source code

C++

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

namespace {

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

struct Options {
    i64 perimeter_limit = 100'000'000;
    bool run_checkpoints = true;
};

bool parse_int_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_int_after_prefix(arg, "--perimeter=", options.perimeter_limit)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.perimeter_limit >= 3;
}

i64 floor_sqrt(i64 x) {
    i64 r = static_cast<i64>(std::sqrt(static_cast<long double>(x)));
    while ((r + 1) * (r + 1) <= x) {
        ++r;
    }
    while (r * r > x) {
        --r;
    }
    return r;
}

i64 ceil_sqrt(i64 x) {
    const i64 r = floor_sqrt(x);
    return (r * r == x) ? r : (r + 1);
}

u64 count_case_k2_a(const i64 perimeter_limit, const i64 max_var) {
    u64 count = 0;
    // k = 2, decomposition (b-a)(c-a) = 2a^2
    // canonical case A: d1 = g*x^2, d2 = 2g*y^2, gcd(x,y)=1, x odd
    for (i64 y = 1; y <= max_var; ++y) {
        const i64 x_max = floor_sqrt(2 * y * y);
        for (i64 x = y + 1; x <= x_max; ++x) {
            if (std::gcd(x, y) != 1 || (x & 1LL) == 0) {
                continue;
            }
            const i64 base = (x + y) * (x + 2 * y);
            if (base > perimeter_limit) {
                continue;
            }
            count += static_cast<u64>(perimeter_limit / base);
        }
    }
    return count;
}

u64 count_case_k2_b(const i64 perimeter_limit, const i64 max_var) {
    u64 count = 0;
    // canonical case B: d1 = 2g*x^2, d2 = g*y^2, gcd(x,y)=1, y odd
    for (i64 x = 1; x <= max_var; ++x) {
        const i64 y_min = ceil_sqrt(2 * x * x);
        const i64 y_max = 2 * x - 1;
        for (i64 y = y_min; y <= y_max; ++y) {
            if (std::gcd(x, y) != 1 || (y & 1LL) == 0) {
                continue;
            }
            const i64 base = (x + y) * (2 * x + y);
            if (base > perimeter_limit) {
                continue;
            }
            count += static_cast<u64>(perimeter_limit / base);
        }
    }
    return count;
}

u64 count_case_k3_a(const i64 perimeter_limit, const i64 max_var) {
    u64 count = 0;
    // k = 3, decomposition (2b-a)(2c-a) = 3a^2
    // canonical case A: u = g*x^2, v = 3g*y^2, gcd(x,y)=1, x % 3 != 0
    for (i64 y = 1; y <= max_var; ++y) {
        const i64 x_max = floor_sqrt(3 * y * y);
        for (i64 x = y + 1; x <= x_max; ++x) {
            if (std::gcd(x, y) != 1 || x % 3 == 0) {
                continue;
            }

            const i64 base_num = (x + y) * (x + 3 * y);  // perimeter = g * base_num / 2
            if (base_num > 2 * perimeter_limit) {
                continue;
            }

            const i64 g_max = (2 * perimeter_limit) / base_num;
            const bool odd_g_valid = ((x * (x + y)) % 2 == 0) && ((y * (x + 3 * y)) % 2 == 0);
            count += odd_g_valid ? static_cast<u64>(g_max) : static_cast<u64>(g_max / 2);
        }
    }
    return count;
}

u64 count_case_k3_b(const i64 perimeter_limit, const i64 max_var) {
    u64 count = 0;
    // canonical case B: u = 3g*x^2, v = g*y^2, gcd(x,y)=1, y % 3 != 0
    for (i64 x = 1; x <= max_var; ++x) {
        const i64 y_min = ceil_sqrt(3 * x * x);
        const i64 y_max = 3 * x - 1;
        for (i64 y = y_min; y <= y_max; ++y) {
            if (std::gcd(x, y) != 1 || y % 3 == 0) {
                continue;
            }

            const i64 base_num = (x + y) * (3 * x + y);  // perimeter = g * base_num / 2
            if (base_num > 2 * perimeter_limit) {
                continue;
            }

            const i64 g_max = (2 * perimeter_limit) / base_num;
            const bool odd_g_valid = ((x * (y + 3 * x)) % 2 == 0) && ((y * (x + y)) % 2 == 0);
            count += odd_g_valid ? static_cast<u64>(g_max) : static_cast<u64>(g_max / 2);
        }
    }
    return count;
}

struct WorkerCtx {
    i64 perimeter_limit;
    i64 max_var;
    unsigned thread_id;
    unsigned thread_count;
    u64 local_count;
};

void* worker_main(void* ptr) {
    auto* ctx = static_cast<WorkerCtx*>(ptr);
    u64 total = 0;
    for (unsigned case_id = ctx->thread_id; case_id < 4U; case_id += ctx->thread_count) {
        if (case_id == 0U) {
            total += count_case_k2_a(ctx->perimeter_limit, ctx->max_var);
        } else if (case_id == 1U) {
            total += count_case_k2_b(ctx->perimeter_limit, ctx->max_var);
        } else if (case_id == 2U) {
            total += count_case_k3_a(ctx->perimeter_limit, ctx->max_var);
        } else {
            total += count_case_k3_b(ctx->perimeter_limit, ctx->max_var);
        }
    }
    ctx->local_count = total;
    return nullptr;
}

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

u64 count_valid_triangles(const i64 perimeter_limit) {
    u64 count = static_cast<u64>(perimeter_limit / 3);  // k = 4 (equilateral)
    const i64 max_var = floor_sqrt(perimeter_limit) + 2;

    const unsigned thread_count = choose_thread_count();
    if (thread_count <= 1U) {
        count += count_case_k2_a(perimeter_limit, max_var);
        count += count_case_k2_b(perimeter_limit, max_var);
        count += count_case_k3_a(perimeter_limit, max_var);
        count += count_case_k3_b(perimeter_limit, max_var);
        return count;
    }

    std::vector<pthread_t> threads(thread_count);
    std::vector<WorkerCtx> ctx(thread_count);
    unsigned created = 0U;
    bool failed = false;
    for (unsigned t = 0U; t < thread_count; ++t) {
        ctx[t] = WorkerCtx{perimeter_limit, max_var, t, thread_count, 0ULL};
        if (pthread_create(&threads[t], nullptr, worker_main, &ctx[t]) != 0) {
            failed = true;
            break;
        }
        ++created;
    }

    for (unsigned t = 0U; t < created; ++t) {
        pthread_join(threads[t], nullptr);
    }

    if (failed) {
        count += count_case_k2_a(perimeter_limit, max_var);
        count += count_case_k2_b(perimeter_limit, max_var);
        count += count_case_k3_a(perimeter_limit, max_var);
        count += count_case_k3_b(perimeter_limit, max_var);
        return count;
    }

    for (const WorkerCtx& w : ctx) {
        count += w.local_count;
    }

    return count;
}

u64 brute_count(const int perimeter_limit) {
    u64 count = 0;
    for (int a = 1; a <= perimeter_limit / 3; ++a) {
        for (int b = a; b <= (perimeter_limit - a) / 2; ++b) {
            for (int c = b; a + b + c <= perimeter_limit; ++c) {
                if (a + b <= c) {
                    continue;
                }
                const i64 num = static_cast<i64>(a + b) * static_cast<i64>(a + c);
                const i64 den = static_cast<i64>(b) * static_cast<i64>(c);
                if (num % den == 0) {
                    ++count;
                }
            }
        }
    }
    return count;
}

bool run_checkpoints() {
    for (int perimeter : {40, 60, 100, 150, 200, 300}) {
        const u64 slow = brute_count(perimeter);
        const u64 fast = count_valid_triangles(perimeter);
        if (slow != fast) {
            std::cerr << "Checkpoint failed at perimeter=" << perimeter
                      << ": brute=" << slow << ", fast=" << fast << '\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;
    }
    std::cout << count_valid_triangles(options.perimeter_limit) << '\n';
    return 0;
}

Python

import math
import multiprocessing

def count_case_k2_a(args):
    y_start, y_end, perimeter_limit = args
    count = 0
    for y in range(y_start, y_end):
        x_max = math.isqrt(2 * y * y)
        for x in range(y + 1, x_max + 1):
            if x % 2 == 0 or math.gcd(x, y) != 1:
                continue
            base = (x + y) * (x + 2 * y)
            if base > perimeter_limit:
                continue
            count += perimeter_limit // base
    return count

def count_case_k2_b(args):
    x_start, x_end, perimeter_limit = args
    count = 0
    for x in range(x_start, x_end):
        r = math.isqrt(2 * x * x)
        y_min = r if r * r == 2 * x * x else r + 1
        y_max = 2 * x - 1
        for y in range(y_min, y_max + 1):
            if y % 2 == 0 or math.gcd(x, y) != 1:
                continue
            base = (x + y) * (2 * x + y)
            if base > perimeter_limit:
                continue
            count += perimeter_limit // base
    return count

def count_case_k3_a(args):
    y_start, y_end, perimeter_limit = args
    count = 0
    for y in range(y_start, y_end):
        x_max = math.isqrt(3 * y * y)
        for x in range(y + 1, x_max + 1):
            if x % 3 == 0 or math.gcd(x, y) != 1:
                continue
            base_num = (x + y) * (x + 3 * y)
            if base_num > 2 * perimeter_limit:
                continue
                
            g_max = (2 * perimeter_limit) // base_num
            odd_g_valid = ((x * (x + y)) % 2 == 0) and ((y * (x + 3 * y)) % 2 == 0)
            count += g_max if odd_g_valid else (g_max // 2)
    return count

def count_case_k3_b(args):
    x_start, x_end, perimeter_limit = args
    count = 0
    for x in range(x_start, x_end):
        r = math.isqrt(3 * x * x)
        y_min = r if r * r == 3 * x * x else r + 1
        y_max = 3 * x - 1
        for y in range(y_min, y_max + 1):
            if y % 3 == 0 or math.gcd(x, y) != 1:
                continue
            base_num = (x + y) * (3 * x + y)
            if base_num > 2 * perimeter_limit:
                continue
                
            g_max = (2 * perimeter_limit) // base_num
            odd_g_valid = ((x * (y + 3 * x)) % 2 == 0) and ((y * (x + y)) % 2 == 0)
            count += g_max if odd_g_valid else (g_max // 2)
    return count

def solve(perimeter_limit=100000000):
    max_var = math.isqrt(perimeter_limit) + 2
    count = perimeter_limit // 3
    
    threads = max(1, multiprocessing.cpu_count())
    
    y_chunk = (max_var + threads - 1) // threads
    tasks_k2_a = [(1 + t * y_chunk, min(max_var + 1, 1 + (t + 1) * y_chunk), perimeter_limit) for t in range(threads)]
    tasks_k2_b = [(1 + t * y_chunk, min(max_var + 1, 1 + (t + 1) * y_chunk), perimeter_limit) for t in range(threads)]
    tasks_k3_a = [(1 + t * y_chunk, min(max_var + 1, 1 + (t + 1) * y_chunk), perimeter_limit) for t in range(threads)]
    tasks_k3_b = [(1 + t * y_chunk, min(max_var + 1, 1 + (t + 1) * y_chunk), perimeter_limit) for t in range(threads)]
    
    if threads > 1:
        with multiprocessing.Pool(threads) as pool:
            count += sum(pool.map(count_case_k2_a, [t for t in tasks_k2_a if t[0] < t[1]]))
            count += sum(pool.map(count_case_k2_b, [t for t in tasks_k2_b if t[0] < t[1]]))
            count += sum(pool.map(count_case_k3_a, [t for t in tasks_k3_a if t[0] < t[1]]))
            count += sum(pool.map(count_case_k3_b, [t for t in tasks_k3_b if t[0] < t[1]]))
    else:
        count += sum(count_case_k2_a(t) for t in tasks_k2_a if t[0] < t[1])
        count += sum(count_case_k2_b(t) for t in tasks_k2_b if t[0] < t[1])
        count += sum(count_case_k3_a(t) for t in tasks_k3_a if t[0] < t[1])
        count += sum(count_case_k3_b(t) for t in tasks_k3_b if t[0] < t[1])
        
    return str(count)

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

Java

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.*;

public class Euler257 {
    static long floorSqrt(long x) {
        long r = (long) Math.sqrt(x);
        while ((r + 1) * (r + 1) <= x)
            r++;
        while (r * r > x)
            r--;
        return r;
    }

    static long ceilSqrt(long x) {
        long r = floorSqrt(x);
        return (r * r == x) ? r : (r + 1);
    }

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

    static long countCaseK2A(long yStart, long yEnd, long limit) {
        long count = 0;
        for (long y = yStart; y < yEnd; ++y) {
            long xMax = floorSqrt(2 * y * y);
            for (long x = y + 1; x <= xMax; ++x) {
                if ((x & 1) == 0 || gcd(x, y) != 1)
                    continue;
                long base = (x + y) * (x + 2 * y);
                if (base > limit)
                    continue;
                count += limit / base;
            }
        }
        return count;
    }

    static long countCaseK2B(long xStart, long xEnd, long limit) {
        long count = 0;
        for (long x = xStart; x < xEnd; ++x) {
            long yMin = ceilSqrt(2 * x * x);
            long yMax = 2 * x - 1;
            for (long y = yMin; y <= yMax; ++y) {
                if ((y & 1) == 0 || gcd(x, y) != 1)
                    continue;
                long base = (x + y) * (2 * x + y);
                if (base > limit)
                    continue;
                count += limit / base;
            }
        }
        return count;
    }

    static long countCaseK3A(long yStart, long yEnd, long limit) {
        long count = 0;
        for (long y = yStart; y < yEnd; ++y) {
            long xMax = floorSqrt(3 * y * y);
            for (long x = y + 1; x <= xMax; ++x) {
                if (x % 3 == 0 || gcd(x, y) != 1)
                    continue;
                long baseNum = (x + y) * (x + 3 * y);
                if (baseNum > 2 * limit)
                    continue;

                long gMax = (2 * limit) / baseNum;
                boolean oddGValid = ((x * (x + y)) % 2 == 0) && ((y * (x + 3 * y)) % 2 == 0);
                count += oddGValid ? gMax : (gMax / 2);
            }
        }
        return count;
    }

    static long countCaseK3B(long xStart, long xEnd, long limit) {
        long count = 0;
        for (long x = xStart; x < xEnd; ++x) {
            long yMin = ceilSqrt(3 * x * x);
            long yMax = 3 * x - 1;
            for (long y = yMin; y <= yMax; ++y) {
                if (y % 3 == 0 || gcd(x, y) != 1)
                    continue;
                long baseNum = (x + y) * (3 * x + y);
                if (baseNum > 2 * limit)
                    continue;

                long gMax = (2 * limit) / baseNum;
                boolean oddGValid = ((x * (y + 3 * x)) % 2 == 0) && ((y * (x + y)) % 2 == 0);
                count += oddGValid ? gMax : (gMax / 2);
            }
        }
        return count;
    }

    public static String solve() {
        long limit = 100000000L;
        long maxVar = floorSqrt(limit) + 2;
        long count = limit / 3;

        int threads = Math.max(1, Runtime.getRuntime().availableProcessors());
        ExecutorService executor = Executors.newFixedThreadPool(threads);
        List<Future<Long>> futures = new ArrayList<>();

        long chunk = (maxVar + threads - 1) / threads;

        for (int t = 0; t < threads; ++t) {
            long start = 1 + t * chunk;
            long end = Math.min(maxVar + 1, 1 + (t + 1) * chunk);
            if (start < end) {
                futures.add(executor.submit(() -> countCaseK2A(start, end, limit)));
                futures.add(executor.submit(() -> countCaseK2B(start, end, limit)));
                futures.add(executor.submit(() -> countCaseK3A(start, end, limit)));
                futures.add(executor.submit(() -> countCaseK3B(start, end, limit)));
            }
        }

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

        return String.valueOf(count);
    }

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