Detailed mathematical approach

Problem Summary

A geometric triangle here means an integer-sided triangle whose side lengths are in geometric progression. If the sides are ordered as \(a \le b \le c\), then the condition is \(b^2 = ac\). For a perimeter limit \(L\), we must count all such triangles with \(a+b+c \le L\).

Mathematical Approach

The local solution files reduce the problem to a sum over primitive parameter pairs \((p,q)\). The full argument has three layers: an exact parameterization of all integer geometric triangles, a triangle-inequality bound on the ratio \(q/p\), and a scaling count for all multiples of each primitive triangle.

Step 1: Parameterize Every Integer Geometric Triangle

Let \((a,b,c)\) be an integer geometric triangle with \(a \le b \le c\). Since the sides are in geometric progression,

$b^2 = ac.$

Set \(m=\gcd(a,c)\), and write

$a=mu,\qquad c=mv,\qquad \gcd(u,v)=1.$

Then \(b^2 = m^2uv\), so \(uv\) is a square. Because \(u\) and \(v\) are coprime, each must itself be a square. Hence there exist coprime integers \(p,q\) such that

$u=p^2,\qquad v=q^2,\qquad \gcd(p,q)=1.$

Therefore every integer geometric triangle has the form

$a=mp^2,\qquad b=mpq,\qquad c=mq^2,$

with \(m \ge 1\), \(1 \le p \le q\), and \(\gcd(p,q)=1\). Conversely, every triple of this form satisfies \(b^2=ac\), so the parameterization is exact and unique once \(p \le q\) and \(\gcd(p,q)=1\) are imposed.

Step 2: Triangle Inequality Gives the Golden-Ratio Bound

The only nontrivial triangle inequality is \(c \lt a+b\). Substituting the parameterization gives

$mq^2 \lt mp^2 + mpq \iff q^2 \lt p^2 + pq.$

Divide by \(p^2\) and set \(x=q/p\). Then

$x^2 - x - 1 \lt 0.$

The positive root is the golden ratio

$\varphi = \frac{1+\sqrt{5}}{2},$

so admissible ratios satisfy

$1 \le \frac{q}{p} \lt \varphi,\qquad q \lt \varphi p.$

This is why the code computes an integer upper bound `q_max_triangle(p)` by starting from \(\varphi p\) and then correcting the boundary with exact arithmetic.

Step 3: Perimeter Bound and the Primitive Contribution

The perimeter of the triangle \((mp^2,mpq,mq^2)\) is

$P = m(p^2 + pq + q^2).$

For a fixed primitive pair \((p,q)\), the allowed scale factors \(m\) are exactly

$1 \le m \le \left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor.$

So the primitive pair \((p,q)\) contributes

$\left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor$

different triangles. Summing over all primitive ratios yields the counting formula used by the solver:

$\boxed{G(L)=\sum_{\substack{p\ge 1\\ q\ge p\\ \gcd(p,q)=1\\ q^2 \lt p^2+pq}} \left\lfloor\frac{L}{p^2+pq+q^2}\right\rfloor.}$

Step 4: Finite Search Bounds

Because \(q \ge p\), the smallest primitive perimeter for a fixed \(p\) occurs at \(q=p\), namely \(p^2+pq+q^2=3p^2\). Therefore no contribution is possible once

$3p^2 \gt L,$

so the outer loop only needs

$p \le p_{\max} = \left\lfloor\sqrt{\frac{L}{3}}\right\rfloor.$

For fixed \(p\), the perimeter inequality

$p^2+pq+q^2 \le L$

is quadratic in \(q\). Solving it gives

$q \le \left\lfloor\frac{\sqrt{4L-3p^2}-p}{2}\right\rfloor.$

The implementation names this second bound `q_max_for_norm(p, L)`, and finally uses

$q_{\max}(p)=\min\!\left(\left\lfloor \varphi p \right\rfloor,\left\lfloor\frac{\sqrt{4L-3p^2}-p}{2}\right\rfloor\right).$

Worked Example: \(L=100\)

The primitive pairs \((p,q)\) that survive both bounds are

$ (1,1),\ (2,3),\ (3,4),\ (4,5),\ (5,6). $

Their primitive perimeters are

$3,\ 19,\ 37,\ 61,\ 91.$

Hence

$G(100)=\left\lfloor\frac{100}{3}\right\rfloor+\left\lfloor\frac{100}{19}\right\rfloor+\left\lfloor\frac{100}{37}\right\rfloor+\left\lfloor\frac{100}{61}\right\rfloor+\left\lfloor\frac{100}{91}\right\rfloor=33+5+2+1+1=42.$

This matches the statement checkpoint \(G(100)=42\) that the C++ file verifies automatically.

Step 5: Counting Coprime \(q\) by Möbius Inversion

A naive implementation would inspect every \(q\) individually. The optimized solver instead counts coprime values in an interval \([A,B]\) by inclusion-exclusion over the prime divisors of \(p\):

$C_p(A,B)=\left|\{q\in[A,B]:\gcd(p,q)=1\}\right|=\sum_{d\mid p}\mu(d)\left(\left\lfloor\frac{B}{d}\right\rfloor-\left\lfloor\frac{A-1}{d}\right\rfloor\right).$

To evaluate this quickly, the code factors \(p\) with a smallest-prime-factor sieve, extracts the distinct primes of \(p\), and enumerates the squarefree divisors together with their Möbius signs \(\mu(d)\in\{-1,1\}\). For very short intervals, both the C++ and Java implementations switch to direct \(\gcd\) tests because that is cheaper than running the divisor sum.

Step 6: Quotient Blocking

For fixed \(p\), define the primitive perimeter form

$N(p,q)=p^2+pq+q^2,\qquad t(q)=\left\lfloor\frac{L}{N(p,q)}\right\rfloor.$

Since \(N(p,q)\) is increasing in \(q\), the quotient \(t(q)\) stays constant on contiguous ranges of \(q\). If a block starts at \(q=\ell\), the code sets

$t=\left\lfloor\frac{L}{N(p,\ell)}\right\rfloor,\qquad M=\left\lfloor\frac{L}{t}\right\rfloor.$

Then the same quotient holds precisely while \(N(p,q)\le M\). So the block ends at the largest \(r\) satisfying that inequality, which is found by another call to `q_max_for_norm(p, M)`. The whole block contributes

$t\cdot C_p(\ell,r).$

This quotient-blocking step is the main reason the optimized solution avoids a full scan over all \(q\).

How the Code Works

The C++ file is the main optimized implementation. It precomputes smallest prime factors up to \(p_{\max}=\lfloor\sqrt{L/3}\rfloor\), processes each \(p\), and optionally parallelizes independent \(p\)-values across threads. It also validates the mathematics by checking the statement values \(G(100)=42\), \(G(1000)=532\), \(G(10^4)=6427\), \(G(10^5)=75243\), \(G(10^6)=861805\), and by comparing fast and brute-force counts on several small limits. The Java file implements the same mathematics in a simpler single-threaded form with `long`. The Python file is intentionally a bridge: it compiles and runs the C++ solver so that Python returns exactly the same validated result.

Complexity Analysis

The sieve up to \(p_{\max}\) costs \(O(p_{\max}\log\log p_{\max})\) time and \(O(p_{\max})\) memory. A naive double loop over all admissible \((p,q)\) pairs is essentially linear in \(L\), because \(p\) ranges up to \(O(\sqrt L)\) and each \(p\) has \(O(p)\) possible \(q\)-values. The implemented solver replaces that raw scan by quotient blocks and Möbius-weighted interval counts. The exact number of blocks depends on the floor-division structure, so the sharp asymptotic is subtle, but in practice it is dramatically smaller than the naive scan, and each block touches only the squarefree divisors of one \(p\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=370
2. Geometric progression: Wikipedia — Geometric progression
3. Golden ratio: Wikipedia — Golden ratio
4. Möbius inversion formula: Wikipedia — Möbius inversion formula
5. Inclusion-exclusion principle: Wikipedia — Inclusion-exclusion principle
6. Smallest-prime-factor sieve: Wikipedia — Sieve of Eratosthenes