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.
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.
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.
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\).
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.
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.
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.$$
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.
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.
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.
Für jedes zulässige Tripel ganzzahliger Zahnzahlen \((s,p,q)\) mit \(s\ge 5\), \(p\ge 5\), \(q>p\) und \(c=s+p+q\) bezeichne \(g(c,s,p,q)\) die Anzahl gültiger Planetentrieb-Anordnungen für genau dieses Tripel. Gesucht ist
$$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),$$
und die Aufgabe verlangt \(G(500)\). Die Implementierungen zeigen, dass sich das Zählproblem für ein festes \((s,p,q)\) auf eine geschlossene geometrische Formel reduziert; danach bleibt nur noch die saubere Enumeration aller zulässigen Tripel.
Wichtig ist zunächst: \(c\) ist keine unabhängige Variable. Sobald \((s,p,q)\) feststeht, ist auch \(c=s+p+q\) festgelegt. Die Aufgabe besteht also darin, zunächst den exakten Wert \(g(c,s,p,q)\) für ein einzelnes Tripel zu berechnen und anschließend über alle zulässigen Tripel zu summieren.
Wegen \(q>p\) wird jedes ungeordnete Paar \(\{p,q\}\) nur einmal gezählt. Für eine feste Schranke \(n\) und ein festes \(s\) setzen wir
$$r=n-s.$$
Dann kann \(p\) höchstens
$$p\le \left\lfloor\frac{r-1}{2}\right\rfloor$$
sein, denn aus \(q\ge p+1\) und \(p+q\le r\) folgt genau diese Obergrenze. Ist \(p\) gewählt, dann läuft das dritte Zahnrad durch
$$q=p+1,p+2,\dots,r-p.$$
Genau diese Schleifenstruktur verwenden die Implementierungen.
Für ein festes Tripel \((s,p,q)\) wird die Zählung in den Implementierungen aus drei positiven Größen gewonnen:
$$u=s+p,\qquad v=s+q,\qquad w=p+q-2\pi.$$
Dabei ist \(w>0\) automatisch, denn aus \(p\ge 5\) und \(q>p\) folgt \(p+q\ge 11>2\pi\). Diese drei Zahlen sind die effektiven Eingaben des geometrischen Teilproblems. Statt mit der ursprünglichen Zahnradskizze direkt zu arbeiten, übersetzt die Lösung alles in Winkelgrenzen, die nur von \(u\), \(v\) und \(w\) abhängen.
Die relevanten Winkelgrenzen erhält man aus Kosinussatz-Ausdrücken:
$$\cos\theta=\frac{v^2+w^2-u^2}{2vw},\qquad \cos\varphi=\frac{u^2+w^2-v^2}{2uw}.$$
Also
$$\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).$$
Diese beiden Winkel beschreiben die Endpunkte des zulässigen Phasenfensters der planetaren Anordnung. In exakter Mathematik sollen die Kosinusargumente in \([-1,1]\) liegen; die Implementierungen klemmen sie trotzdem auf dieses Intervall, um numerische Randfehler durch Gleitkommaarithmetik abzufangen.
Sobald die beiden Winkel bekannt sind, wird aus dem kontinuierlichen Phasenfenster ein ganzzahliges Zählproblem. Die Implementierungen kodieren den oberen Rand als
$$M=\frac{v\theta-u\varphi}{\pi}.$$
Im verschobenen Koordinatensystem der Lösung ist die Anzahl zulässiger ganzzahliger Phasenpositionen dann
$$g(c,s,p,q)=\max\!\left(0,\ u+\left\lfloor M\right\rfloor\right).$$
Das äußere Maximum ist nötig, weil manche Tripel überhaupt keine gültige diskrete Position zulassen. Genau diese Formel ist der mathematische Kern der gesamten Berechnung.
Das kleinste mögliche zulässige Tripel ist \((s,p,q)=(5,5,6)\). Dann gilt
$$u=10,\qquad v=11,\qquad w=11-2\pi\approx 4.7168146928.$$
Aus den Kosinusformeln folgt
$$\theta\approx 1.1409056324,\qquad \varphi\approx 1.5575630607.$$
Somit ist
$$M=\frac{11\theta-10\varphi}{\pi}\approx -0.9631002437.$$
Daher \(\lfloor M\rfloor=-1\), also
$$g(16,5,5,6)=\max(0,10-1)=9.$$
Dieses Beispiel ist besonders nützlich, weil \(16=5+5+6\) die kleinste mögliche Gesamtzahnzahl ist. Es gibt also genau ein zulässiges Tripel mit \(s+p+q\le 16\), und damit sofort
$$G(16)=9.$$
Ist \(g(c,s,p,q)\) für ein einzelnes Tripel bekannt, erhält man die globale Antwort durch direkte 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).$$
Jede innere Auswertung kostet \(O(1)\). Die mathematische Schwierigkeit liegt also in der exakten geschlossenen Formel für \(g\), nicht in einer komplizierten Datenstruktur.
Die C++-, Python- und Java-Implementierungen folgen derselben Formel. Sie iterieren über \(s\), berechnen das Restbudget \(r=n-s\), bestimmen daraus den größten zulässigen Wert für \(p\) und durchlaufen anschließend jedes \(q\) von \(p+1\) bis \(r-p\). Für jedes Tripel werden die beiden Kosinusausdrücke ausgewertet, in \([-1,1]\) geklemmt, per Umkehrfunktion in Winkel umgerechnet, zu \(M=(v\theta-u\varphi)/\pi\) zusammengesetzt und anschließend in eine ganze Anzahl überführt.
Vor dem Abrunden wird ein sehr kleines Epsilon addiert, damit Werte, die numerisch knapp ober- oder unterhalb einer ganzen Zahl liegen, nicht durch Rundungsfehler auf die falsche Seite kippen. Der Beitrag jedes Tripels wird danach bei \(0\) abgeschnitten und zu einer 64-Bit-Gesamtsumme addiert. Die Python-Implementierung rechnet seriell; die C++- und Java-Implementierungen verteilen die äußere \(s\)-Schleife auf mehrere Worker-Threads und addieren zum Schluss die Teilsummen.
Für jedes zulässige Tripel \((s,p,q)\) kostet die Berechnung von \(g\) konstante Zeit. Die Gesamtlaufzeit ist daher proportional zur Anzahl zulässiger Tripel:
$$\sum_{s=5}^{n}\sum_{p=5}^{\left\lfloor\frac{n-s-1}{2}\right\rfloor} (n-s-2p)=O(n^3).$$
In der Praxis ist der konstante Faktor klein, weil jede Iteration nur wenige arithmetische Operationen und zwei Aufrufe von \(\arccos\) enthält. Der Speicherverbrauch ist \(O(1)\) in der seriellen Variante und \(O(t)\) in den parallelen Varianten, wobei \(t\) die Anzahl der Threads mit Teilsummen bezeichnet.
\(s\ge 5\), \(p\ge 5\), \(q>p\) koşullarını sağlayan her tamsayı diş sayısı üçlüsü \((s,p,q)\) için \(c=s+p+q\) alınsın ve \(g(c,s,p,q)\), bu üçlüye karşılık gelen geçerli gezegensel dişli düzenlerinin sayısı olsun. Aranan büyüklük
$$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),$$
olup problem \(G(500)\) değerini ister. Uygulamalar, \((s,p,q)\) sabitlenince sayma işinin kapalı bir geometrik formüle indiğini gösterir; geriye yalnızca tüm uygun üçlüleri sistemli biçimde dolaşmak kalır.
İlk kritik nokta şudur: \(c\) bağımsız bir değişken değildir. \((s,p,q)\) seçildiği anda \(c=s+p+q\) otomatik olarak belirlenir. Bu yüzden problem önce tek bir üçlü için \(g(c,s,p,q)\) değerini tam hesaplamaya, sonra da bunu tüm uygun üçlüler üzerinde toplamaya dönüşür.
\(q>p\) koşulu sayesinde her sırasız \(\{p,q\}\) çifti yalnızca bir kez sayılır. Sabit bir \(n\) üst sınırı ve sabit bir \(s\) için
$$r=n-s$$
yazalım. O zaman \(p\) ancak
$$p\le \left\lfloor\frac{r-1}{2}\right\rfloor$$
olabilir; çünkü \(q\ge p+1\) ve \(p+q\le r\) birlikte bu üst sınırı verir. \(p\) seçildikten sonra üçüncü dişli
$$q=p+1,p+2,\dots,r-p$$
aralığında dolaşır. Uygulamaların kurduğu döngü yapısı tam olarak budur.
Sabit bir \((s,p,q)\) üçlüsü için sayım, uygulamalarda şu üç pozitif büyüklük üzerinden yapılır:
$$u=s+p,\qquad v=s+q,\qquad w=p+q-2\pi.$$
Burada \(w>0\) olması otomatik olarak sağlanır; çünkü \(p\ge 5\) ve \(q>p\) olduğundan \(p+q\ge 11>2\pi\). Bu üç sayı, geometrik alt problemin etkili girdileridir. Çözüm, özgün dişli resminin ayrıntılarıyla uğraşmak yerine her şeyi \(u\), \(v\) ve \(w\) ile belirlenen açı sınırlarına çevirir.
Gerekli açı sınırları kosinüs teoremi ifadelerinden gelir:
$$\cos\theta=\frac{v^2+w^2-u^2}{2vw},\qquad \cos\varphi=\frac{u^2+w^2-v^2}{2uw}.$$
Dolayısıyla
$$\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).$$
Bu iki açı, gezegensel düzen için uygun faz penceresinin uçlarını belirler. Saf matematikte kosinüs girişlerinin \([-1,1]\) aralığında olması gerekir; uygulamalar buna rağmen kayan nokta sapmalarını bastırmak için bu değerleri yine de bu aralığa sıkıştırır.
İki açı belirlendikten sonra sürekli faz aralığı, tamsayı sayma problemine dönüşür. Uygulamalar üst sınırı
$$M=\frac{v\theta-u\varphi}{\pi}$$
olarak kodlar. Çözümün kullandığı kaydırılmış koordinat sisteminde uygun tamsayı faz konumlarının sayısı
$$g(c,s,p,q)=\max\!\left(0,\ u+\left\lfloor M\right\rfloor\right)$$
olur. Dıştaki maksimum gereklidir; çünkü bazı üçlüler hiç geçerli ayrık konum bırakmaz. Bütün hesabın matematiksel çekirdeği bu tek formüldür.
Mümkün olan en küçük uygun üçlü \((s,p,q)=(5,5,6)\) olur. Bu durumda
$$u=10,\qquad v=11,\qquad w=11-2\pi\approx 4.7168146928.$$
Kosinüs formüllerinden
$$\theta\approx 1.1409056324,\qquad \varphi\approx 1.5575630607$$
elde edilir. Böylece
$$M=\frac{11\theta-10\varphi}{\pi}\approx -0.9631002437.$$
O halde \(\lfloor M\rfloor=-1\) ve sonuç
$$g(16,5,5,6)=\max(0,10-1)=9$$
olur. Bu örnek ayrıca çok faydalıdır; çünkü \(16=5+5+6\) mümkün olan en küçük toplam diş sayısıdır. Demek ki \(s+p+q\le 16\) koşulunu sağlayan yalnızca tek bir üçlü vardır ve toplam doğrudan
$$G(16)=9$$
çıkar.
Tek bir üçlü için \(g(c,s,p,q)\) hesaplandıktan sonra küresel sonuç doğrudan şu toplamla elde edilir:
$$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).$$
İçteki her değerlendirme \(O(1)\) maliyetlidir. Dolayısıyla matematiksel zorluk, gelişmiş bir veri yapısında değil, \(g\) için bulunan tam kapalı formdadır.
C++, Python ve Java uygulamaları aynı formülü izler. Önce \(s\) üzerinde dönerler, sonra kalan bütçeyi \(r=n-s\) olarak hesaplarlar, buradan mümkün olan en büyük \(p\) değerini çıkarırlar ve her \(q\) değerini \(p+1\) ile \(r-p\) arasında gezerler. Her üçlü için iki kosinüs ifadesi hesaplanır, sonuçlar \([-1,1]\) aralığına sıkıştırılır, ters kosinüs alınır, \(M=(v\theta-u\varphi)/\pi\) oluşturulur ve bu reel sınır bir tamsayı sayısına çevrilir.
Kayan nokta yuvarlama hataları yüzünden tam sayı sınırlarında yanlış tarafa düşmemek için taban alma işleminden önce çok küçük bir epsilon eklenir. Üçlünün katkısı daha sonra \(0\) ile aşağıdan sınırlandırılır ve 64 bitlik toplamın üzerine eklenir. Python uygulaması döngüleri seri yürütür; C++ ve Java uygulamaları ise dıştaki \(s\) döngüsünü işçi parçacıklarına dağıtıp sonunda kısmi toplamları birleştirir.
Her uygun \((s,p,q)\) üçlüsü için \(g\) hesabı sabit zaman alır. Bu nedenle toplam çalışma süresi uygun üçlü sayısıyla orantılıdır:
$$\sum_{s=5}^{n}\sum_{p=5}^{\left\lfloor\frac{n-s-1}{2}\right\rfloor} (n-s-2p)=O(n^3).$$
Pratikte sabit katsayı küçüktür; çünkü her yineleme yalnızca birkaç aritmetik işlem ve iki adet \(\arccos\) çağrısı yapar. Bellek kullanımı seri sürümde \(O(1)\), çok iş parçacıklı sürümlerde ise kısmi toplam tutan işçi sayısı \(t\) olmak üzere \(O(t)\) düzeyindedir.
Para cada triple admisible de números enteros de dientes \((s,p,q)\) con \(s\ge 5\), \(p\ge 5\), \(q>p\) y \(c=s+p+q\), sea \(g(c,s,p,q)\) el número de configuraciones planetarias válidas asociadas a ese triple. La cantidad buscada es
$$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),$$
y la tarea pide \(G(500)\). Las implementaciones muestran que, una vez fijado \((s,p,q)\), el conteo se reduce a una fórmula geométrica cerrada; después solo queda enumerar con cuidado todos los triples admisibles.
La primera observación importante es que \(c\) no es una variable independiente. En cuanto se fija \((s,p,q)\), automáticamente se tiene \(c=s+p+q\). Así, el problema consiste en calcular primero el valor exacto de \(g(c,s,p,q)\) para un solo triple y luego sumarlo sobre todos los triples permitidos.
Como \(q>p\), cada par no ordenado \(\{p,q\}\) se cuenta una sola vez. Para un límite superior fijo \(n\) y un valor fijo de \(s\), escribimos
$$r=n-s.$$
Entonces \(p\) solo puede llegar hasta
$$p\le \left\lfloor\frac{r-1}{2}\right\rfloor,$$
porque \(q\ge p+1\) y \(p+q\le r\). Una vez elegido \(p\), el tercer engranaje recorre
$$q=p+1,p+2,\dots,r-p.$$
Esa es exactamente la estructura de bucles utilizada por las implementaciones.
Para un triple fijo \((s,p,q)\), las implementaciones obtienen el conteo a partir de tres cantidades positivas:
$$u=s+p,\qquad v=s+q,\qquad w=p+q-2\pi.$$
Aquí \(w>0\) de forma automática, porque \(p\ge 5\) y \(q>p\) implican \(p+q\ge 11>2\pi\). Estos tres números son las entradas efectivas del subproblema geométrico. En lugar de trabajar directamente con la figura mecánica original, la solución traduce todo a cotas angulares determinadas por \(u\), \(v\) y \(w\).
Las cotas angulares relevantes salen de expresiones del teorema del coseno:
$$\cos\theta=\frac{v^2+w^2-u^2}{2vw},\qquad \cos\varphi=\frac{u^2+w^2-v^2}{2uw}.$$
Por tanto,
$$\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).$$
Estos dos ángulos describen los extremos de la ventana de fase admisible para la configuración planetaria. En matemáticas exactas, las entradas del coseno inverso deberían pertenecer a \([-1,1]\); aun así, las implementaciones las recortan a ese intervalo para evitar desviaciones numéricas cerca de los bordes.
Una vez conocidos los dos ángulos, la ventana continua de fase se convierte en un problema de contar enteros. Las implementaciones codifican su extremo superior como
$$M=\frac{v\theta-u\varphi}{\pi}.$$
En el sistema de coordenadas desplazado que usa la solución, el número de posiciones de fase enteras admisibles es
$$g(c,s,p,q)=\max\!\left(0,\ u+\left\lfloor M\right\rfloor\right).$$
El máximo exterior es necesario porque algunos triples no dejan ninguna posición discreta válida. Esta única fórmula concentra el núcleo matemático de todo el cálculo.
El triple admisible más pequeño es \((s,p,q)=(5,5,6)\). Entonces
$$u=10,\qquad v=11,\qquad w=11-2\pi\approx 4.7168146928.$$
Aplicando las fórmulas del coseno obtenemos
$$\theta\approx 1.1409056324,\qquad \varphi\approx 1.5575630607.$$
Así,
$$M=\frac{11\theta-10\varphi}{\pi}\approx -0.9631002437.$$
Por lo tanto, \(\lfloor M\rfloor=-1\), y queda
$$g(16,5,5,6)=\max(0,10-1)=9.$$
Este ejemplo también es útil a escala global, porque \(16=5+5+6\) es la suma mínima posible. En consecuencia, solo existe un triple admisible con \(s+p+q\le 16\), y por eso
$$G(16)=9.$$
Una vez calculado \(g(c,s,p,q)\) para un triple, la respuesta global se obtiene con la suma directa
$$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).$$
Cada evaluación interior cuesta \(O(1)\), así que la dificultad matemática está en encontrar la forma cerrada exacta de \(g\), no en construir una estructura de datos sofisticada.
Las implementaciones en C++, Python y Java siguen exactamente la misma fórmula. Recorren \(s\), calculan el presupuesto restante \(r=n-s\), deducen a partir de él el mayor valor posible de \(p\) y luego prueban cada \(q\) desde \(p+1\) hasta \(r-p\). Para cada triple evalúan las dos expresiones de coseno, las ajustan al intervalo \([-1,1]\), toman los dos arccosenos, forman \(M=(v\theta-u\varphi)/\pi\) y convierten esa cota real en un conteo entero.
Antes de aplicar el piso se suma un epsilon muy pequeño para que un valor que numéricamente esté apenas por encima o por debajo de un entero no caiga del lado incorrecto por redondeo de coma flotante. Después, la contribución del triple se corta inferiormente en \(0\) y se añade a un total de 64 bits. La implementación en Python recorre todo en serie; las de C++ y Java reparten el bucle exterior sobre \(s\) entre varios hilos de trabajo y combinan las sumas parciales al final.
Para cada triple admisible \((s,p,q)\), la fórmula de \(g\) cuesta tiempo constante. Por eso el tiempo total es proporcional al número de triples admisibles:
$$\sum_{s=5}^{n}\sum_{p=5}^{\left\lfloor\frac{n-s-1}{2}\right\rfloor} (n-s-2p)=O(n^3).$$
En la práctica el factor constante es pequeño, porque cada iteración realiza solo unas pocas operaciones aritméticas y dos llamadas a \(\arccos\). El uso de memoria es \(O(1)\) en la versión en serie y \(O(t)\) en las versiones paralelas, donde \(t\) es el número de hilos que guardan sumas parciales.
对每一个满足 \(s\ge 5\)、\(p\ge 5\)、\(q>p\) 的整数齿数三元组 \((s,p,q)\)，令 \(c=s+p+q\)，并把 \(g(c,s,p,q)\) 定义为该三元组对应的合法行星齿轮排布数。题目要求的是
$$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),$$
最终目标是求 \(G(500)\)。从三份实现可以看出，一旦固定 \((s,p,q)\)，局部计数并不需要再做复杂搜索，而是会收缩成一条明确的几何公式；真正剩下的工作只是把所有合法三元组完整枚举并累加。
首先要看清一点：\(c\) 不是独立枚举的变量。只要 \((s,p,q)\) 确定，\(c=s+p+q\) 就自动确定。因此整个问题可以拆成两层：先求单个三元组的精确值 \(g(c,s,p,q)\)，再把它对所有合法三元组求和。
由于条件是 \(q>p\)，所以无序对 \(\{p,q\}\) 只会被计算一次，不会出现镜像重复。对固定的上界 \(n\) 和固定的 \(s\)，记
$$r=n-s.$$
因为必须同时满足 \(q\ge p+1\) 与 \(p+q\le r\)，所以 \(p\) 的最大值只能是
$$p\le \left\lfloor\frac{r-1}{2}\right\rfloor.$$
在 \(p\) 已经选定之后，第三个齿轮的齿数范围就是
$$q=p+1,p+2,\dots,r-p.$$
这正是实现中三重循环的来源。也就是说，程序根本不需要单独遍历 \(c\)，因为它始终由三元组本身给出。
对固定的 \((s,p,q)\)，实现把局部几何问题压缩成三个正量
$$u=s+p,\qquad v=s+q,\qquad w=p+q-2\pi.$$
这里 \(w\) 一定为正，因为 \(p\ge 5\) 且 \(q>p\) 推出 \(p+q\ge 11>2\pi\)。这三个量就是后续公式真正需要的输入。换句话说，解法并不是直接在原始机械图形上做连续搜索，而是把约束改写成只依赖 \(u\)、\(v\)、\(w\) 的角度边界问题。
实现中决定答案的两个角，来自下面这组余弦定理形式：
$$\cos\theta=\frac{v^2+w^2-u^2}{2vw},\qquad \cos\varphi=\frac{u^2+w^2-v^2}{2uw}.$$
因此
$$\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).$$
这两个角给出了合法相位窗口的两端。在精确数学里，反余弦的输入本应天然落在 \([-1,1]\) 内；实现仍然额外做一次截断，是为了防止浮点误差把非常接近边界的值推到区间外面。
当两个角已经确定之后，连续几何约束就变成了“有多少个整数相位索引落在允许区间里”的问题。实现把这个区间的上端写成
$$M=\frac{v\theta-u\varphi}{\pi}.$$
在解法采用的平移坐标系下，合法整数相位位置的个数正好是
$$g(c,s,p,q)=\max\!\left(0,\ u+\left\lfloor M\right\rfloor\right).$$
外层的 \(\max\) 不能省略，因为某些三元组根本没有合法的离散位置。整个问题里最核心的数学内容，其实就凝聚在这一条公式中。
最小的合法三元组是 \((s,p,q)=(5,5,6)\)。此时
$$u=10,\qquad v=11,\qquad w=11-2\pi\approx 4.7168146928.$$
代入余弦公式后可得
$$\theta\approx 1.1409056324,\qquad \varphi\approx 1.5575630607.$$
于是
$$M=\frac{11\theta-10\varphi}{\pi}\approx -0.9631002437.$$
所以 \(\lfloor M\rfloor=-1\)，从而
$$g(16,5,5,6)=\max(0,10-1)=9.$$
这个例子还顺手说明了一个全局校验点。因为 \(16=5+5+6\) 是可能的最小总齿数，所以满足 \(s+p+q\le 16\) 的合法三元组只有这一组，立刻得到
$$G(16)=9.$$
这与实现中的小规模断言完全一致。
一旦单个三元组的值已经能用闭式公式给出，总答案就是直接累加：
$$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).$$
每次内部计算都是 \(O(1)\)，所以这里没有筛法、动态规划或数论预处理一类的重型工具。真正重要的是局部公式必须足够准确，尤其是在浮点边界附近不能把 \(\lfloor M\rfloor\) 算错。
C++、Python 和 Java 三个实现遵循同一套数学流程。它们先遍历 \(s\)，再把剩余预算写成 \(r=n-s\)，由此计算出 \(p\) 的最大可能值，然后对每个 \(p\) 让 \(q\) 从 \(p+1\) 扫到 \(r-p\)。对每个三元组，程序都会计算两条余弦表达式，把结果截断到 \([-1,1]\) 区间，求出两个反余弦，组成 \(M=(v\theta-u\varphi)/\pi\)，最后把这个实数上界转换成整数个数。
为了避免浮点舍入把本来应该落在整数边界上的值推到错误的一侧，实现在取整之前会先加上一个极小的 epsilon。随后，单个三元组的贡献会被下截到 \(0\)，并累加到 64 位整数总和中。Python 版本使用直接的串行循环；C++ 与 Java 版本则把最外层的 \(s\) 循环分给多个工作线程，并在最后汇总各线程的部分和。
对每个合法三元组 \((s,p,q)\)，计算 \(g\) 的代价都是常数时间。因此总时间复杂度与合法三元组总数同阶：
$$\sum_{s=5}^{n}\sum_{p=5}^{\left\lfloor\frac{n-s-1}{2}\right\rfloor} (n-s-2p)=O(n^3).$$
常数项并不大，因为每次迭代只包含少量加减乘除以及两次 \(\arccos\) 调用。空间复杂度在串行版本中是 \(O(1)\)；在线程化版本中，需要为每个工作线程保存部分和，因此是 \(O(t)\)，其中 \(t\) 是线程数。
Для каждого допустимого тройственного набора целых чисел зубьев \((s,p,q)\), где \(s\ge 5\), \(p\ge 5\), \(q>p\) и \(c=s+p+q\), величина \(g(c,s,p,q)\) обозначает число корректных планетарных конфигураций для этого набора. Требуется вычислить
$$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),$$
а именно значение \(G(500)\). Из реализаций видно, что после фиксации \((s,p,q)\) локальная задача сводится к явной геометрической формуле, и затем остаётся лишь аккуратно просуммировать её по всем допустимым тройкам.
Первое важное замечание: \(c\) не является независимой переменной. Как только выбрана тройка \((s,p,q)\), значение \(c=s+p+q\) уже определено. Поэтому задача естественно распадается на две части: сначала вычислить точное значение \(g(c,s,p,q)\) для одной тройки, а потом просуммировать его по всем допустимым тройкам.
Условие \(q>p\) гарантирует, что каждая неупорядоченная пара \(\{p,q\}\) учитывается только один раз. Для фиксированного верхнего предела \(n\) и фиксированного \(s\) введём
$$r=n-s.$$
Тогда \(p\) может принимать значения только до
$$p\le \left\lfloor\frac{r-1}{2}\right\rfloor,$$
поскольку одновременно должны выполняться \(q\ge p+1\) и \(p+q\le r\). После выбора \(p\) третье колесо пробегает значения
$$q=p+1,p+2,\dots,r-p.$$
Именно такая структура циклов присутствует во всех реализациях.
Для фиксированной тройки \((s,p,q)\) локальный счёт выражается через три положительные величины
$$u=s+p,\qquad v=s+q,\qquad w=p+q-2\pi.$$
Здесь \(w>0\) автоматически, потому что из \(p\ge 5\) и \(q>p\) следует \(p+q\ge 11>2\pi\). Именно эти три числа служат эффективными параметрами геометрической подзадачи. Вместо прямой работы с исходной картиной передачи решение переводит всё в систему угловых ограничений, зависящих только от \(u\), \(v\) и \(w\).
Нужные углы получаются из выражений типа закона косинусов:
$$\cos\theta=\frac{v^2+w^2-u^2}{2vw},\qquad \cos\varphi=\frac{u^2+w^2-v^2}{2uw}.$$
Следовательно,
$$\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).$$
Эти два угла задают концы допустимого фазового окна. В точной математике аргументы \(\arccos\) должны лежать в интервале \([-1,1]\); реализации всё равно дополнительно ограничивают их этим интервалом, чтобы компенсировать погрешности плавающей точки у границы.
После нахождения углов непрерывное фазовое условие становится задачей о числе целых индексов в допустимом интервале. Верхний конец этого интервала реализации записывают как
$$M=\frac{v\theta-u\varphi}{\pi}.$$
В сдвинутой системе координат, принятой в решении, число допустимых целочисленных фазовых положений равно
$$g(c,s,p,q)=\max\!\left(0,\ u+\left\lfloor M\right\rfloor\right).$$
Внешний максимум обязателен, потому что для некоторых троек допустимых дискретных положений нет вовсе. Именно эта формула составляет математическое ядро вычисления.
Минимальная допустимая тройка имеет вид \((s,p,q)=(5,5,6)\). Тогда
$$u=10,\qquad v=11,\qquad w=11-2\pi\approx 4.7168146928.$$
Из формул закона косинусов получаем
$$\theta\approx 1.1409056324,\qquad \varphi\approx 1.5575630607.$$
Следовательно,
$$M=\frac{11\theta-10\varphi}{\pi}\approx -0.9631002437.$$
Значит, \(\lfloor M\rfloor=-1\), и потому
$$g(16,5,5,6)=\max(0,10-1)=9.$$
Этот пример полезен ещё и как глобальная проверка. Поскольку \(16=5+5+6\) является минимальной возможной суммой зубьев, при условии \(s+p+q\le 16\) существует ровно одна допустимая тройка. Поэтому сразу получаем
$$G(16)=9.$$
Как только значение \(g(c,s,p,q)\) для одной тройки выражено в явном виде, полный ответ получается прямой суммой:
$$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).$$
Каждое внутреннее вычисление стоит \(O(1)\), поэтому главная математическая трудность связана не со структурами данных, а с точной формулой для \(g\), особенно вблизи границ округления.
Реализации на C++, Python и Java следуют одной и той же схеме. Они перебирают \(s\), затем вычисляют остаточный бюджет \(r=n-s\), по нему определяют максимально допустимое \(p\), после чего для каждого \(p\) перебирают все \(q\) от \(p+1\) до \(r-p\). Для каждой тройки программа вычисляет два косинусных выражения, ограничивает их интервалом \([-1,1]\), берёт два арккосинуса, строит величину \(M=(v\theta-u\varphi)/\pi\) и преобразует её в целочисленный вклад.
Перед операцией взятия пола добавляется очень маленькое epsilon, чтобы число, которое численно оказалось чуть выше или чуть ниже целой границы, не перешло на неверную сторону из-за ошибок округления. После этого вклад тройки обрезается снизу нулём и добавляется к 64-битной сумме. Вариант на Python выполняет перебор последовательно, а варианты на C++ и Java распределяют внешний цикл по \(s\) между рабочими потоками и затем суммируют частичные результаты.
Для каждой допустимой тройки \((s,p,q)\) вычисление \(g\) занимает постоянное время. Поэтому суммарная трудоёмкость пропорциональна числу допустимых троек:
$$\sum_{s=5}^{n}\sum_{p=5}^{\left\lfloor\frac{n-s-1}{2}\right\rfloor} (n-s-2p)=O(n^3).$$
На практике константа невелика, потому что одна итерация содержит лишь несколько арифметических операций и два вызова \(\arccos\). Память равна \(O(1)\) в последовательной версии и \(O(t)\) в параллельных версиях, где \(t\) — число потоков, хранящих частичные суммы.
لكل ثلاثية مسموح بها من أعداد الأسنان الصحيحة \((s,p,q)\) بحيث \(s\ge 5\)، و\(p\ge 5\)، و\(q>p\)، ومع \(c=s+p+q\)، نرمز بـ \(g(c,s,p,q)\) إلى عدد ترتيبات التروس الكوكبية الصحيحة الموافقة لهذه الثلاثية. الكمية المطلوبة هي
$$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),$$
والمطلوب في المسألة هو \(G(500)\). وتُظهر التطبيقات أن مشكلة العد، بعد تثبيت \((s,p,q)\)، تنكمش إلى صيغة هندسية مغلقة، ثم لا يبقى إلا جمع هذه القيمة على جميع الثلاثيات المسموح بها.
الملاحظة الأساسية الأولى هي أن \(c\) ليس متغيرًا مستقلًا. فبمجرد اختيار \((s,p,q)\) يصبح \(c=s+p+q\) معلومًا تلقائيًا. لذلك تنقسم المسألة طبيعيًا إلى مرحلتين: حساب القيمة الدقيقة \(g(c,s,p,q)\) لثلاثية واحدة، ثم جمعها على كل الثلاثيات الممكنة.
بسبب الشرط \(q>p\)، فإن كل زوج غير مرتب \(\{p,q\}\) يُحسب مرة واحدة فقط. ولحد علوي ثابت \(n\) وقيمة ثابتة لـ \(s\)، نكتب
$$r=n-s.$$
عندئذ لا يمكن أن يتجاوز \(p\) القيمة
$$p\le \left\lfloor\frac{r-1}{2}\right\rfloor,$$
لأن الشرطين \(q\ge p+1\) و\(p+q\le r\) يفرضان ذلك بالضبط. وبعد اختيار \(p\)، يتحرك الترس الثالث ضمن المجال
$$q=p+1,p+2,\dots,r-p.$$
وهذا هو بعينه شكل الحلقات المستعمل في التطبيقات.
لثلاثية ثابتة \((s,p,q)\)، تستخرج التطبيقات العد من ثلاث كميات موجبة هي
$$u=s+p,\qquad v=s+q,\qquad w=p+q-2\pi.$$
وهنا تكون \(w>0\) تلقائيًا، لأن \(p\ge 5\) و\(q>p\) يؤديان إلى \(p+q\ge 11>2\pi\). هذه الأعداد الثلاثة هي المدخلات الفعلية للمسألة الهندسية الجزئية. فبدل التعامل المباشر مع الصورة الميكانيكية الأصلية، يحول الحل القيود إلى حدود زاوية تعتمد فقط على \(u\) و\(v\) و\(w\).
حدود الزوايا المطلوبة تأتي من صيغ من نوع قانون جيب التمام:
$$\cos\theta=\frac{v^2+w^2-u^2}{2vw},\qquad \cos\varphi=\frac{u^2+w^2-v^2}{2uw}.$$
ومن ثم
$$\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).$$
هاتان الزاويتان تحددان طرفي نافذة الطور المسموح بها. وفي الرياضيات الدقيقة يُفترض أن تقع مدخلات \(\arccos\) داخل \([-1,1]\)، لكن التطبيقات تقيدها بهذا المجال أيضًا كإجراء وقائي ضد انحرافات الفاصلة العائمة قرب الحدود.
بعد معرفة الزاويتين، تتحول النافذة المستمرة إلى مسألة عدّ لمواضع طور صحيحة. وتمثل التطبيقات الحد العلوي لهذه النافذة بالقيمة
$$M=\frac{v\theta-u\varphi}{\pi}.$$
وفي الجهاز الإحداثي المزاح الذي يعتمده الحل، يكون عدد مواضع الطور الصحيحة المسموح بها مساويًا لـ
$$g(c,s,p,q)=\max\!\left(0,\ u+\left\lfloor M\right\rfloor\right).$$
ولا بد من وجود \(\max\) الخارجية، لأن بعض الثلاثيات لا تعطي أي موضع صحيح صالح أصلًا. هذه الصيغة الواحدة هي جوهر الحساب كله.
أصغر ثلاثية مسموح بها هي \((s,p,q)=(5,5,6)\). عندها
$$u=10,\qquad v=11,\qquad w=11-2\pi\approx 4.7168146928.$$
ومن صيغ جيب التمام نحصل على
$$\theta\approx 1.1409056324,\qquad \varphi\approx 1.5575630607.$$
إذن
$$M=\frac{11\theta-10\varphi}{\pi}\approx -0.9631002437.$$
ومن ثم \(\lfloor M\rfloor=-1\)، وبالتالي
$$g(16,5,5,6)=\max(0,10-1)=9.$$
وهذا المثال مفيد أيضًا على مستوى المجموع الكلي، لأن \(16=5+5+6\) هو أصغر مجموع ممكن لعدد الأسنان. لذلك لا توجد إلا ثلاثية واحدة تحقق \(s+p+q\le 16\)، ومن ثم نحصل مباشرة على
$$G(16)=9.$$
بعد أن تصبح قيمة \(g(c,s,p,q)\) لثلاثية واحدة معروفة بصيغة مغلقة، تكون الإجابة النهائية مجرد مجموع مباشر:
$$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).$$
كل تقييم داخلي يكلف \(O(1)\)، لذا فالصعوبة الرياضية الحقيقية ليست في بنية بيانات معقدة، بل في الوصول إلى صيغة دقيقة لـ \(g\) لا تخطئ قرب حدود التقريب العددي.
تتبع تطبيقات C++ وPython وJava الصيغة نفسها. فهي تمر على قيم \(s\)، ثم تحسب الميزانية المتبقية \(r=n-s\)، وتستخرج منها أكبر قيمة ممكنة لـ \(p\)، وبعد ذلك تمر على كل \(q\) من \(p+1\) حتى \(r-p\). ولكل ثلاثية تحسب عبارتي جيب التمام، وتقيد النتيجة داخل \([-1,1]\)، ثم تأخذ قيمتي \(\arccos\)، وتبني \(M=(v\theta-u\varphi)/\pi\)، ثم تحول هذا الحد الحقيقي إلى عدد صحيح من المواضع.
وقبل أخذ الجزء الصحيح تُضاف قيمة صغيرة جدًا من نوع epsilon حتى لا يؤدي التقريب العشري إلى إسقاط قيمة قريبة من حد صحيح على الجانب الخاطئ. ثم تُقص مساهمة الثلاثية من الأسفل عند \(0\)، وتُجمع في مجموع صحيح من 64 بت. نسخة Python تنفذ الحلقات على نحو تسلسلي، بينما توزع نسختا C++ وJava الحلقة الخارجية الخاصة بـ \(s\) على عدة خيوط عمل ثم تجمعان المجاميع الجزئية في النهاية.
لكل ثلاثية مسموح بها \((s,p,q)\)، يُحسب \(g\) في زمن ثابت. لذلك يكون الزمن الكلي متناسبًا مع عدد الثلاثيات المسموح بها:
$$\sum_{s=5}^{n}\sum_{p=5}^{\left\lfloor\frac{n-s-1}{2}\right\rfloor} (n-s-2p)=O(n^3).$$
في التطبيق العملي يكون الثابت صغيرًا، لأن كل دورة تحتوي فقط على عدد قليل من العمليات الحسابية واستدعاءين للدالة \(\arccos\). استهلاك الذاكرة هو \(O(1)\) في النسخة التسلسلية و\(O(t)\) في النسخ المتوازية، حيث \(t\) هو عدد خيوط العمل التي تحتفظ بالمجاميع الجزئية.