Detailed mathematical approach

Problem Summary

Let \(T(N)\) denote the number of integer-sided triangles that contain a \(60^\circ\) angle and whose incircle radius does not exceed \(N\). The specific task is to evaluate \(T(1{,}053{,}779)\).

A brute-force search over side triples would be far too large, because the geometric condition mixes a Diophantine constraint from the \(60^\circ\) angle with a second constraint on the inradius. The implementations therefore replace direct triangle enumeration by a parametrization of primitive objects and then count all admissible integer scalings.

Mathematical Approach

The key observation is that a \(60^\circ\) triangle can be converted into a \(120^\circ\) triangle with integer sides, and the latter has a classical coprime parametrization. Once that primitive parametrization is known, the inradius becomes a simple linear expression, so counting triangles reduces to summing the number of allowed scale factors.

From a \(60^\circ\) triangle to a \(120^\circ\) triple

Take a triangle whose \(60^\circ\) angle lies between the integer sides \(a\) and \(b\), and let \(c\) be the side opposite that angle. Without loss of generality order the adjacent sides so that \(a \le b\). The law of cosines gives

$c^2=a^2+b^2-ab.$

Now write \(x=a\) and \(y=b-a\), so \(b=x+y\). Substituting this into the cosine-law relation yields

$c^2=x^2+(x+y)^2-x(x+y)=x^2+xy+y^2.$

So every target triangle determines an integer triple \((x,y,z)\) with

$z^2=x^2+xy+y^2.$

This is exactly the side relation for a triangle with a \(120^\circ\) angle. Conversely, any positive integer solution of \(z^2=x^2+xy+y^2\) generates two \(60^\circ\) triangles:

$ (x,\ x+y,\ z)\qquad\text{and}\qquad (y,\ x+y,\ z). $

That is why the counting formula naturally splits into two families.

Primitive parametrization of the \(120^\circ\) triples

For primitive solutions of \(z^2=x^2+xy+y^2\), the implementations use the standard parametrization

$x=m^2-n^2,\qquad y=2mn+n^2,\qquad z=m^2+mn+n^2,$

where

$m>n\ge 1,\qquad \gcd(m,n)=1,\qquad m\not\equiv n \pmod{3}.$

The coprimality condition removes common factors, and the congruence restriction eliminates the redundant non-primitive cases. It is convenient to replace \(m\) by

$t=m-n,$

so that \(m=n+t\), \(\gcd(m,n)=\gcd(n,t)\), and the congruence condition becomes simply \(t\not\equiv 0\pmod 3\).

The two \(60^\circ\) families and their inradii

Family A uses the triangle \((x,\ x+y,\ z)\). Since \(x+y=m^2+2mn=m(m+2n)\), its area is

$\Delta_A=\frac{\sqrt{3}}{4}\,x(x+y),$

and its semiperimeter is

$s_A=\frac{x+(x+y)+z}{2}=\frac{2x+y+z}{2}=\frac{3m(m+n)}{2}.$

Therefore

$r_A=\frac{\Delta_A}{s_A}=\frac{\sqrt{3}}{6}(m-n)(m+2n)=\frac{\sqrt{3}}{6}\,t(3n+t).$

Family B uses the triangle \((y,\ x+y,\ z)\). Its area and semiperimeter are

$\Delta_B=\frac{\sqrt{3}}{4}\,y(x+y),\qquad s_B=\frac{y+(x+y)+z}{2}=\frac{x+2y+z}{2}=\frac{(m+2n)(2m+n)}{2},$

so its inradius becomes

$r_B=\frac{\Delta_B}{s_B}=\frac{\sqrt{3}}{2}mn=\frac{\sqrt{3}}{2}\,n(n+t).$

If a primitive triangle is scaled by an integer factor \(k\), all side lengths and the inradius scale by the same factor. Hence the two non-primitive families are counted through

$r_A(k)=\frac{k\sqrt{3}}{6}\,q_A,\qquad q_A=t(3n+t),$

$r_B(k)=\frac{k\sqrt{3}}{2}\,q_B,\qquad q_B=n(n+t).$

Counting all admissible scales

For a fixed primitive object, the only remaining question is how many positive integers \(k\) keep the inradius below \(N\). Family B requires

$\frac{k\sqrt{3}}{2}\,q_B\le N,$

so the number of valid scales is

$\left\lfloor \frac{2N}{q_B\sqrt{3}} \right\rfloor.$

Family A analogously contributes

$\left\lfloor \frac{6N}{q_A\sqrt{3}} \right\rfloor.$

This is the central invariant used by the code. If we define

$M_C(q)=\left\lfloor \frac{C}{q\sqrt{3}} \right\rfloor,$

then the total count is

$T(N)=\sum_{\substack{n\ge 1,\ t\ge 1\\ \gcd(n,t)=1\\ t\not\equiv 0\!\!\!\pmod 3}} M_{2N}\!\bigl(n(n+t)\bigr)+\sum_{\substack{n\ge 1,\ t\ge 1\\ \gcd(n,t)=1\\ t\not\equiv 0\!\!\!\pmod 3}} M_{6N}\!\bigl(t(3n+t)\bigr),$

with the understanding that only pairs satisfying \(q_B\le 2N/\sqrt3\) or \(q_A\le 6N/\sqrt3\) contribute at all. The two sums are finite because once \(q\) exceeds its threshold, even the primitive scale \(k=1\) is already too large.

Worked example

Choose \(m=2\) and \(n=1\), so \(t=1\). The primitive \(120^\circ\) triple is

$x=2^2-1^2=3,\qquad y=2\cdot2\cdot1+1^2=5,\qquad z=2^2+2\cdot1+1^2=7.$

This generates the two primitive \(60^\circ\) triangles

$ (3,8,7)\qquad\text{and}\qquad (5,8,7). $

For Family A,

$q_A=t(3n+t)=1\cdot(3+1)=4,\qquad r_A=\frac{\sqrt3}{6}\cdot 4=\frac{2\sqrt3}{3}.$

For Family B,

$q_B=n(n+t)=1\cdot2=2,\qquad r_B=\frac{\sqrt3}{2}\cdot 2=\sqrt3.$

If, for illustration, \(N=10\), then the admissible scale counts would be

$\left\lfloor \frac{60}{4\sqrt3}\right\rfloor=8\qquad\text{and}\qquad \left\lfloor \frac{20}{2\sqrt3}\right\rfloor=5.$

The actual problem uses a much larger \(N\), but the counting mechanism is identical: each primitive parameter pair contributes exactly the number of legal integer scalings.

How the Code Works

The implementations organize the computation around the function \(M_C(q)=\lfloor C/(q\sqrt3)\rfloor\). They build one table for \(C=2N\) and another for \(C=6N\), because the two triangle families differ only in that constant and in the definition of \(q\).

Exact scale-count tables

Each table entry stores the largest \(k\) such that \(qk\sqrt3\le C\). Instead of trusting floating-point arithmetic at the boundary, the code converts this to the exact integer inequality

$3q^2k^2\le C^2.$

A square-root estimate is used only as a starting guess; it is then corrected upward or downward until the inequality is exact. This prevents off-by-one errors near values where \(C/(q\sqrt3)\) lies extremely close to an integer.

Enumerating the primitive families

After the tables are ready, the code loops over the primitive parameters \((n,t)\). For Family B it walks through \(n\) and then all \(t\) for which \(q_B=n(n+t)\) still fits under the table bound. For Family A it walks through \(t\) and then all \(n\) for which \(q_A=t(3n+t)\) fits. In both cases it enforces \(\gcd(n,t)=1\) and skips \(t\) divisible by 3.

Every valid pair contributes a single precomputed table lookup, so the total is just the sum of those entries across both families. The C++ implementation can distribute the outer parameter loop across several threads, while the Python and Java implementations perform the same arithmetic serially. The C++ version also checks the known values \(T(100)=1234\), \(T(1000)=22767\), and \(T(10000)=359912\) before evaluating the full target.

Complexity Analysis

Let

$Q_B=\left\lfloor\frac{2N}{\sqrt3}\right\rfloor,\qquad Q_A=\left\lfloor\frac{6N}{\sqrt3}\right\rfloor.$

Building the two lookup tables costs \(O(Q_A+Q_B)=O(N)\) time and memory. The primitive enumeration for Family B visits

$\sum_{n\le \sqrt{Q_B}} O\!\left(\frac{Q_B}{n}\right)=O(Q_B\log Q_B),$

candidate pairs before the gcd filter, and Family A behaves similarly:

$\sum_{t\le \sqrt{Q_A}} O\!\left(\frac{Q_A}{t}\right)=O(Q_A\log Q_A).$

Hence the overall running time is \(O(N\log N)\), with \(O(N)\) memory for the scale tables. This is dramatically smaller than any direct search over side triples, because the geometry has already been compressed into two structured Diophantine families.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=195
2. Law of cosines: Wikipedia - Law of cosines
3. Incircle and inradius: Wikipedia - Incircle and excircles of a triangle
4. Integer triangles: Wikipedia - Integer triangle
5. Greatest common divisor: Wikipedia - Greatest common divisor