Detailed mathematical approach

Problem Summary

For every admissible triple of integer tooth counts \((s,p,q)\) with \(s\ge 5\), \(p\ge 5\), \(q>p\), and \(c=s+p+q\), let \(g(c,s,p,q)\) denote the number of valid planetary-gear arrangements for that triple. The target quantity is

$G(n)=\sum_{s\ge 5}\sum_{p\ge 5}\sum_{\substack{q>p\\s+p+q\le n}} g(s+p+q,s,p,q),$

and the problem asks for \(G(500)\). The implementations show that once one triple \((s,p,q)\) is fixed, the counting problem collapses to a closed geometric formula, so the remaining work is a careful enumeration of all admissible triples.

Mathematical Approach

The key point is that \(c\) is not an independent variable: once \((s,p,q)\) is chosen, we automatically have \(c=s+p+q\). So the problem is to evaluate one exact count \(g(c,s,p,q)\) and then sum it over all admissible triples.

Step 1: Reduce the Search Domain

Because \(q>p\), each unordered pair \(\{p,q\}\) is counted only once. For a fixed upper limit \(n\) and a fixed value of \(s\), write

$r=n-s.$

Then \(p\) can run only up to

$p\le \left\lfloor\frac{r-1}{2}\right\rfloor,$

since \(q\ge p+1\) and \(p+q\le r\). After choosing \(p\), the third gear satisfies

$q=p+1,p+2,\dots,r-p.$

This is exactly the loop structure used by the implementations.

Step 2: Package the Geometry into Three Quantities

For one fixed triple \((s,p,q)\), the implementations derive the count from three positive quantities

$u=s+p,\qquad v=s+q,\qquad w=p+q-2\pi.$

Here \(w>0\) automatically because \(p\ge 5\) and \(q>p\) imply \(p+q\ge 11>2\pi\). These three numbers act as the effective inputs of the geometric subproblem. Instead of working directly with the original gear picture, the solution converts everything into angle bounds determined by \(u\), \(v\), and \(w\).

Step 3: Extract the Two Critical Angles

The relevant angular limits are obtained from law-of-cosines expressions:

$\cos\theta=\frac{v^2+w^2-u^2}{2vw},\qquad \cos\varphi=\frac{u^2+w^2-v^2}{2uw}.$

Therefore

$\theta=\arccos\!\left(\frac{v^2+w^2-u^2}{2vw}\right),\qquad \varphi=\arccos\!\left(\frac{u^2+w^2-v^2}{2uw}\right).$

These angles describe the ends of the admissible phase window for the planetary arrangement. In exact mathematics the cosine inputs are intended to lie in \([-1,1]\); the implementations still clamp them to that interval to protect against floating-point drift near the boundary.

Step 4: Turn the Angle Window into a Discrete Count

Once the two angles are known, the continuous phase window becomes an integer-counting problem. The implementations encode its upper endpoint as

$M=\frac{v\theta-u\varphi}{\pi}.$

In the shifted coordinate system used by the solution, the number of admissible integer phase positions is

$g(c,s,p,q)=\max\!\left(0,\ u+\left\lfloor M\right\rfloor\right).$

The outer maximum is necessary because some triples leave no valid discrete positions at all. This single formula is the entire mathematical core of the computation.

Step 5: Worked Example with the Smallest Admissible Triple

The smallest possible admissible triple is \((s,p,q)=(5,5,6)\). Then

$u=10,\qquad v=11,\qquad w=11-2\pi\approx 4.7168146928.$

From the cosine formulas we get

$\theta\approx 1.1409056324,\qquad \varphi\approx 1.5575630607.$

Hence

$M=\frac{11\theta-10\varphi}{\pi}\approx -0.9631002437.$

So \(\lfloor M\rfloor=-1\), and therefore

$g(16,5,5,6)=\max(0,10-1)=9.$

This example is especially useful because \(16=5+5+6\) is the smallest possible total tooth count. Therefore there is only one admissible triple with \(s+p+q\le 16\), and the full sum is immediately

$G(16)=9.$

Step 6: Sum over All Admissible Triples

After computing \(g(c,s,p,q)\) for one triple, the global answer is obtained by direct summation:

$G(n)=\sum_{s=5}^{n}\ \sum_{p=5}^{\left\lfloor\frac{n-s-1}{2}\right\rfloor}\ \sum_{q=p+1}^{n-s-p} g(s+p+q,s,p,q).$

Each inner evaluation is \(O(1)\), so the mathematical difficulty lies in finding the exact closed form for \(g\), not in any advanced data structure.

How the Code Works

The C++, Python, and Java implementations all follow the same formula. They loop over \(s\), compute the remaining budget \(r=n-s\), derive the largest feasible \(p\), and then scan every \(q\) from \(p+1\) to \(r-p\). For each triple they evaluate the two cosine expressions, clamp the results into \([-1,1]\), take the two inverse cosines, form \(M=(v\theta-u\varphi)/\pi\), and convert that real bound into an integer count.

A small epsilon is added before taking the floor so that values numerically equal to an integer from above or below do not fall on the wrong side because of floating-point rounding. The per-triple contribution is then truncated at zero and added to a 64-bit total. The Python implementation performs the loops serially, while the C++ and Java implementations distribute the outer \(s\)-loop across worker threads and combine partial sums at the end.

Complexity Analysis

For each admissible triple \((s,p,q)\), the formula for \(g\) takes constant time. The total running time is therefore proportional to the number of admissible triples:

$\sum_{s=5}^{n}\sum_{p=5}^{\left\lfloor\frac{n-s-1}{2}\right\rfloor} (n-s-2p)=O(n^3).$

In practice the constant factor is small because each iteration performs only a few arithmetic operations and two calls to \(\arccos\). Memory usage is \(O(1)\) for the serial version and \(O(t)\) for the threaded versions, where \(t\) is the number of worker threads storing partial sums.

Footnotes and References

1. Project Euler, Problem 620: https://projecteuler.net/problem=620
2. Epicyclic gearing overview: Wikipedia — Epicyclic gearing
3. Law of cosines: Wikipedia — Law of cosines
4. Inverse trigonometric functions: Wikipedia — Inverse trigonometric functions
5. Floor and ceiling functions: Wikipedia — Floor and ceiling functions