Detailed mathematical approach

Problem Summary

Start with an acute triangle whose angles are \((A,B,C)\). One telescoping step replaces it by the new triangle with angles

$\bigl(\pi-2A,\ \pi-2B,\ \pi-2C\bigr).$

The sum is still \(\pi\), so the transformation preserves the angle-sum identity, but it is only valid as long as all three new angles remain positive and acute. The telescoping depth of a triangle is the number of consecutive valid triangles in this chain, including the original one. Problem 985 asks for the smallest perimeter of an integer-sided triangle whose telescoping depth is exactly \(20\).

Mathematical Approach

The three implementations all revolve around the same fact: telescoping is easiest to study relative to the equilateral triangle.

Deviations from \(60^\circ\)

Write the angles as

$A=\frac{\pi}{3}+\alpha,\qquad B=\frac{\pi}{3}+\beta,\qquad C=\frac{\pi}{3}+\gamma,$

with

$\alpha+\beta+\gamma=0.$

After one telescoping step,

$\pi-2\left(\frac{\pi}{3}+\alpha\right)=\frac{\pi}{3}-2\alpha,$

and similarly for the other two angles. Therefore the deviation triple evolves by the simple recurrence

$ (\alpha,\beta,\gamma)\longmapsto (-2\alpha,\,-2\beta,\,-2\gamma). $

So every step flips the sign of each deviation and doubles its magnitude.

The admissible interval for depth \(t\)

An angle is acute exactly when it lies in \((0,\pi/2)\), which means a deviation \(d\) from \(\pi/3\) must satisfy

$-\frac{\pi}{3}<d<\frac{\pi}{6}.$

After \(j\) telescoping steps the deviation is \((-2)^j d\), so depth at least \(t\) is equivalent to

$-\frac{\pi}{3}<(-2)^j d<\frac{\pi}{6},\qquad 0\le j<t.$

Intersecting those intervals gives a closed form. If \(t=2m\) is even, then

$I_{2m}=\left(-\frac{\pi}{3\cdot 2^{2m}},\ \frac{\pi}{3\cdot 2^{2m-1}}\right),$

while for \(t=2m+1\) one gets

$I_{2m+1}=\left(-\frac{\pi}{3\cdot 2^{2m}},\ \frac{\pi}{3\cdot 2^{2m+1}}\right).$

For the target \(t=20\), every initial deviation must lie in

$I_{20}=\left(-\frac{\pi}{3\cdot 2^{20}},\ \frac{\pi}{3\cdot 2^{19}}\right).$

This interval is extremely narrow, so any depth-20 triangle must be very close to equilateral.

Converting the angular window into a side-ratio bound

Order the sides and opposite angles as \(a\le b\le c\) and \(A\le B\le C\). The law of sines gives

$\frac{c}{a}=\frac{\sin C}{\sin A}.$

Inside the depth-20 window, the largest angle can be at most \(\pi/3+\pi/(3\cdot 2^{19})\), while the smallest can be as low as \(\pi/3-\pi/(3\cdot 2^{20})\). Since \(\sin x\) is increasing on \((0,\pi/2)\),

$\frac{c}{a}\le \frac{\sin\!\left(\frac{\pi}{3}+\frac{\pi}{3\cdot 2^{19}}\right)}{\sin\!\left(\frac{\pi}{3}-\frac{\pi}{3\cdot 2^{20}}\right)}=:r_{\max}.$

Numerically, \(r_{\max}-1\approx 1.72977337\times 10^{-6}\). That is why the search space collapses to near-equilateral triangles.

Why the minimizer has the form \((a,a,a+1)\)

An equilateral integer triangle would stay equilateral forever, so it does not have finite depth \(20\). Among non-equilateral integer triangles with fixed smallest side \(a\), the smallest possible perimeter is achieved by choosing the remaining sides as small as the ordering allows:

$b=a,\qquad c=a+1,$

which gives perimeter \(3a+1\). Because near-equilateral triangles are the only candidates for depth \(20\), the global minimizer must be the first isosceles triangle \((a,a,a+1)\) that enters the admissible window.

Solving the threshold for \((a,a,a+1)\)

For \((a,a,a+1)\), let \(C\) be the angle opposite the side \(a+1\). The law of cosines yields

$\cos C=\frac{a^2+a^2-(a+1)^2}{2a^2}=\frac12-\frac{2a+1}{2a^2}.$

Set

$K=\frac{\pi}{3\cdot 2^{19}}.$

Because the other two angles are equal to \((\pi-C)/2\), the full depth-20 condition for this isosceles family reduces to the single inequality

$C<\frac{\pi}{3}+K.$

Since \(\cos x\) decreases on \((0,\pi)\), this is equivalent to

$\frac12-\frac{2a+1}{2a^2}>\cos\!\left(\frac{\pi}{3}+K\right).$

If we define

$V=\frac12-\cos\!\left(\frac{\pi}{3}+K\right),$

then the inequality becomes

$2Va^2-2a-1>0,$

so the first valid integer is

$a=\left\lfloor \frac{1+\sqrt{1+2V}}{2V}\right\rfloor+1.$

This gives \(a=578111\), hence the minimal perimeter is

$3a+1=1734334.$

For this triangle, the excess angle \(C-\pi/3\) is about \(1.99736879\times 10^{-6}\), which is below the depth-20 ceiling \(K\approx 1.99737082\times 10^{-6}\) but above the much smaller depth-21 ceiling \(\pi/(3\cdot 2^{21})\). Therefore the depth is exactly \(20\), not \(21\) or more.

Worked example: the depth-2 triangle \((3,3,4)\)

The same mechanism is already visible at very small depth. For \((3,3,4)\), the largest angle satisfies

$\cos C=\frac{9+9-16}{18}=\frac19,$

so \(C\approx 83.62^\circ\), and the other two angles are about \(48.19^\circ\). After one telescoping step the new angles are approximately

$83.62^\circ,\ 83.62^\circ,\ 12.76^\circ,$

which are still acute. After the next step they become approximately

$12.76^\circ,\ 12.76^\circ,\ 154.48^\circ,$

so the chain stops. That is why \((3,3,4)\) has exact depth \(2\), matching the general recurrence.

How the Code Works

The general search implementation

The C++ implementation keeps the problem in its full form. It computes triangle angles from side lengths with the law of cosines, simulates the telescoping map directly, and counts how many acute triangles appear before the process fails. Separately, it derives the admissible deviation interval for the requested target depth, converts it into the side-ratio cap \(r_{\max}\), and uses that cap to restrict the enumeration to a very thin strip near the line \(a=b=c\).

The search loops through ordered integer triples \(a\le b\le c\), enforces the triangle inequality, and breaks early whenever the current perimeter can no longer beat the best perimeter already found. That version is useful because it verifies the mathematics without assuming the final closed form in advance.

The closed-form specialization for \(t=20\)

The Python and Java implementations go one step further. They use the proof that the minimizer must be \((a,a,a+1)\), substitute that family into the law of cosines, and solve a single quadratic inequality for \(a\). Because \(K=\pi/(3\cdot 2^{19})\) is tiny, they evaluate \(\sin K\) and \(\cos K\) with short Taylor expansions, reconstruct \(\cos(\pi/3+K)\) from angle-addition formulas, and then compute the first integer \(a\) above the threshold. The printed answer is simply \(3a+1\).

Complexity Analysis

For the general search, checking one candidate triangle costs \(O(t)\) time because the telescoping chain is followed for at most a small capped number of steps. The candidate region itself is controlled by \(r_{\max}\): for a given \(a\), only \(O(a(r_{\max}-1)+1)\) values of \(c\) are possible, and the admissible range for \(b\) has the same order of magnitude. Since \(r_{\max}-1\) is tiny for \(t=20\), the practical search is far smaller than a naive cubic sweep over all triangles of comparable perimeter.

The Python and Java implementations eliminate enumeration entirely. At the fixed Project Euler target they perform a constant amount of high-precision arithmetic, so both time and memory usage are effectively \(O(1)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=985
2. Law of cosines: Wikipedia - Law of cosines
3. Law of sines: Wikipedia - Law of sines
4. Acute triangle: Wikipedia - Acute and obtuse triangles
5. Isosceles triangle: Wikipedia - Isosceles triangle
6. Taylor series: Wikipedia - Taylor series