For positive integers \(m\), \(k\), and \(s\), define the generalized McCarthy function
$$M_{m,k,s}(n)=\begin{cases}n-s,&n>m,\\M_{m,k,s}\!\left(M_{m,k,s}(n+k)\right),&n\le m.\end{cases}$$
For each pair \(1\le s<k\le p\), we look at all fixed points \(n\) satisfying \(M_{m,k,s}(n)=n\), and we add those fixed points to the global total. The task is therefore to compute
$$S(p,m)=\sum_{1\le s<k\le p}\ \sum_{\substack{n\in\mathbb{Z}\\ M_{m,k,s}(n)=n}} n$$
for very large parameters. Directly expanding the recursion for every \((k,s)\) would be hopeless, so the solution first characterizes exactly when fixed points exist and what interval they form.
The implementations are based on turning the recursion into a divisibility problem. Once that is done, the answer becomes a single \(O(p)\) summation.
Set
$$g=k-s.$$
Because the problem only considers \(s<k\), we always have \(g>0\). The key identity is that for every \(n\le m\),
$$M_{m,k,s}(n)=M_{m,k,s}(n+g).$$
Why is this true? If \(n+k>m\), then the inner call is already in the base case:
$$M_{m,k,s}(n+k)=n+k-s=n+g,$$
so indeed \(M_{m,k,s}(n)=M_{m,k,s}(n+g)\).
If \(n+k\le m\), we apply the same statement to the larger argument \(n+k\) and obtain
$$M_{m,k,s}(n+k)=M_{m,k,s}(n+k+g).$$
Substituting this into the recursion gives
$$M_{m,k,s}(n)=M_{m,k,s}\!\left(M_{m,k,s}(n+k)\right)=M_{m,k,s}\!\left(M_{m,k,s}(n+k+g)\right)=M_{m,k,s}(n+g).$$
So below the threshold \(m\), each recursive layer effectively shifts the argument upward by exactly \(g\).
Take some \(n\le m\), and let \(q\) be the smallest positive integer such that
$$n+qg>m.$$
Equivalently,
$$q=\left\lfloor\frac{m-n}{g}\right\rfloor+1.$$
Repeatedly applying the shift identity from Step 1 gives
$$M_{m,k,s}(n)=M_{m,k,s}(n+qg).$$
Now the argument \(n+qg\) is above \(m\), so the base rule applies and yields
$$M_{m,k,s}(n)=n+qg-s.$$
This explicit formula is the turning point of the whole solution: the nested recursion disappears, replaced by a simple linear expression once \(q\) is known.
A fixed point satisfies \(M_{m,k,s}(n)=n\). Using the closed form above, this means
$$n+qg-s=n,$$
so
$$qg=s.$$
Therefore fixed points exist if and only if \(g\) divides \(s\). When that happens, \(q=s/g\), and the minimality condition on \(q\) becomes
$$n+(q-1)g\le m<n+qg.$$
Substituting \(q=s/g\) gives
$$m-s<n\le m-s+g.$$
Hence the complete set of fixed points is the interval
$$\{m-s+1,\ m-s+2,\ \dots,\ m-s+g\},$$
and its length is exactly \(g=k-s\). If \(g\nmid s\), there are no fixed points at all.
Whenever \(g\mid s\), write
$$s=g(t-1),\qquad k=s+g=gt,$$
with \(t\ge 2\). The bound \(k\le p\) becomes
$$2\le t\le \left\lfloor\frac{p}{g}\right\rfloor.$$
This change of variables is exactly what the implementations use. Instead of iterating over all pairs \((k,s)\), they iterate over the gap \(g\) and over the quotient \(t=k/g\). Every valid pair appears once, and every invalid pair disappears automatically because the divisibility condition is already built in.
For a valid pair, the fixed points form the arithmetic interval
$$m-s+1,\ m-s+2,\ \dots,\ m-s+g.$$
Its sum is
$$\sum_{r=1}^{g}(m-s+r)=g(m-s)+\frac{g(g+1)}{2}.$$
Substitute \(s=g(t-1)\):
$$\Sigma(g,t)=g\bigl(m-g(t-1)\bigr)+\frac{g(g+1)}{2}.$$
After rearranging, this becomes
$$\Sigma(g,t)=g(m+g+1)+\frac{g(g-1)}{2}-g^2t.$$
This is the exact per-pair contribution accumulated by the three implementations.
For a fixed \(g\), define
$$T=\left\lfloor\frac{p}{g}\right\rfloor.$$
Then \(t\) runs through the consecutive interval \(2,3,\dots,T\). Therefore
$$S(p,m)=\sum_{g=1}^{p}\ \sum_{t=2}^{\lfloor p/g\rfloor}\left(g(m+g+1)+\frac{g(g-1)}{2}-g^2t\right).$$
Now the inner sum is just arithmetic-series algebra. Since
$$\#\{2,\dots,T\}=T-1,\qquad \sum_{t=2}^{T} t=\frac{T(T+1)}{2}-1,$$
the contribution of one \(g\) is
$$\begin{aligned} &(T-1)\,g(m+g+1)+(T-1)\,\frac{g(g-1)}{2}\\ &\qquad -g^2\left(\frac{T(T+1)}{2}-1\right). \end{aligned}$$
This is why the final program needs only one loop over \(g\), with constant-time arithmetic inside that loop.
The value \(S(10,10)\) is a useful checkpoint. We group terms by \(g\):
$$\begin{aligned} g=1&:&&10+9+8+7+6+5+4+3+2=54,\\ g=2&:&&19+15+11+7=52,\\ g=3&:&&27+18=45,\\ g=4&:&&34,\\ g=5&:&&40. \end{aligned}$$
For \(g\ge 6\), we have \(\lfloor 10/g\rfloor<2\), so there are no valid pairs. Summing the nonzero groups gives
$$54+52+45+34+40=225,$$
which matches the implementation checkpoint.
The C++, Python, and Java implementations all follow the grouped formula from Step 6. They iterate \(g\) from \(1\) to \(p\), compute
$$T=\left\lfloor\frac{p}{g}\right\rfloor,$$
and skip the iteration when \(T<2\), because then no valid \(t\) exists. Otherwise they evaluate the closed form for the whole block \(t=2,\dots,T\): one factor counts how many terms there are, one factor supplies the arithmetic-series sum of \(t\), and the three resulting pieces are combined into the contribution for that \(g\).
No recursion is executed at runtime. The implementations work entirely with the derived summation formula. Python relies on arbitrary-precision integers automatically, Java uses arbitrary-precision integer arithmetic for the running total, and C++ accumulates in unsigned 128-bit arithmetic and converts the final value to decimal text for output.
The loop over \(g\) runs exactly \(p\) times, and each iteration performs only \(O(1)\) arithmetic. Therefore the total running time is \(O(p)\), and the auxiliary memory usage is \(O(1)\). This is a dramatic improvement over trying to analyze each recursive function instance separately.
Für positive ganze Zahlen \(m\), \(k\) und \(s\) sei die verallgemeinerte McCarthy-Funktion definiert durch
$$M_{m,k,s}(n)=\begin{cases}n-s,&n>m,\\M_{m,k,s}\!\left(M_{m,k,s}(n+k)\right),&n\le m.\end{cases}$$
Für jedes Paar \(1\le s<k\le p\) betrachten wir alle Fixpunkte \(n\) mit \(M_{m,k,s}(n)=n\) und addieren diese Fixpunkte. Gesucht ist also
$$S(p,m)=\sum_{1\le s<k\le p}\ \sum_{\substack{n\in\mathbb{Z}\\ M_{m,k,s}(n)=n}} n.$$
Die Rekursion direkt für alle \((k,s)\) auszuwerten, wäre viel zu teuer. Deshalb bestimmt die Lösung zuerst exakt, wann Fixpunkte existieren und welches Intervall sie bilden.
Die Implementierungen verwandeln die verschachtelte Rekursion in ein Teilbarkeitsproblem. Danach bleibt nur noch eine einzige Summe der Größenordnung \(O(p)\).
Setze
$$g=k-s.$$
Da stets \(s<k\) gilt, ist \(g>0\). Die zentrale Identität lautet für jedes \(n\le m\):
$$M_{m,k,s}(n)=M_{m,k,s}(n+g).$$
Falls \(n+k>m\), liegt der innere Aufruf bereits im Basisfall:
$$M_{m,k,s}(n+k)=n+k-s=n+g,$$
also folgt sofort \(M_{m,k,s}(n)=M_{m,k,s}(n+g)\).
Falls \(n+k\le m\), wenden wir dieselbe Aussage auf das größere Argument \(n+k\) an und erhalten
$$M_{m,k,s}(n+k)=M_{m,k,s}(n+k+g).$$
Einsetzen in die Rekursion liefert dann
$$M_{m,k,s}(n)=M_{m,k,s}\!\left(M_{m,k,s}(n+k)\right)=M_{m,k,s}\!\left(M_{m,k,s}(n+k+g)\right)=M_{m,k,s}(n+g).$$
Unterhalb der Schranke \(m\) verschiebt jede Rekursionsebene das Argument also effektiv um genau \(g\) nach oben.
Sei nun \(n\le m\), und \(q\) die kleinste positive ganze Zahl mit
$$n+qg>m.$$
Äquivalent ist
$$q=\left\lfloor\frac{m-n}{g}\right\rfloor+1.$$
Wegen Schritt 1 dürfen wir so lange um \(g\) weiterschieben, bis die Schranke überschritten wird:
$$M_{m,k,s}(n)=M_{m,k,s}(n+qg).$$
Jetzt greift der Basisfall, also
$$M_{m,k,s}(n)=n+qg-s.$$
Damit verschwindet die verschachtelte Rekursion vollständig; übrig bleibt ein linearer Ausdruck, sobald \(q\) feststeht.
Ein Fixpunkt erfüllt \(M_{m,k,s}(n)=n\). Mit der geschlossenen Form bedeutet das
$$n+qg-s=n,$$
also
$$qg=s.$$
Fixpunkte existieren daher genau dann, wenn \(g\) ein Teiler von \(s\) ist. In diesem Fall gilt \(q=s/g\), und die Minimalitätsbedingung für \(q\) lautet
$$n+(q-1)g\le m<n+qg.$$
Nach Einsetzen von \(q=s/g\) erhält man
$$m-s<n\le m-s+g.$$
Die gesamte Fixpunktmenge ist also das Intervall
$$\{m-s+1,\ m-s+2,\ \dots,\ m-s+g\},$$
mit genau \(g=k-s\) Elementen. Wenn \(g\nmid s\) gilt, gibt es überhaupt keinen Fixpunkt.
Immer wenn \(g\mid s\) gilt, schreiben wir
$$s=g(t-1),\qquad k=s+g=gt,$$
wobei \(t\ge 2\) ist. Aus \(k\le p\) folgt
$$2\le t\le \left\lfloor\frac{p}{g}\right\rfloor.$$
Genau diese Umparametrisierung steckt im Programm. Statt alle Paare \((k,s)\) direkt durchzugehen, werden die Lücke \(g\) und der Quotient \(t=k/g\) durchlaufen. Jedes gültige Paar erscheint genau einmal, und ungültige Paare verschwinden automatisch, weil die Teilbarkeitsbedingung bereits eingebaut ist.
Für ein gültiges Paar bilden die Fixpunkte die arithmetische Folge
$$m-s+1,\ m-s+2,\ \dots,\ m-s+g.$$
Ihre Summe ist
$$\sum_{r=1}^{g}(m-s+r)=g(m-s)+\frac{g(g+1)}{2}.$$
Setzt man \(s=g(t-1)\) ein, so folgt
$$\Sigma(g,t)=g\bigl(m-g(t-1)\bigr)+\frac{g(g+1)}{2}.$$
Nach Umformen erhält man
$$\Sigma(g,t)=g(m+g+1)+\frac{g(g-1)}{2}-g^2t.$$
Das ist genau der Pro-Paar-Beitrag, den die Implementierungen aufsummieren.
Für festes \(g\) definieren wir
$$T=\left\lfloor\frac{p}{g}\right\rfloor.$$
Dann läuft \(t\) durch \(2,3,\dots,T\). Daher gilt
$$S(p,m)=\sum_{g=1}^{p}\ \sum_{t=2}^{\lfloor p/g\rfloor}\left(g(m+g+1)+\frac{g(g-1)}{2}-g^2t\right).$$
Die innere Summe ist nun reine Arithmetik. Wegen
$$\#\{2,\dots,T\}=T-1,\qquad \sum_{t=2}^{T} t=\frac{T(T+1)}{2}-1$$
ist der Beitrag eines festen \(g\)
$$\begin{aligned} &(T-1)\,g(m+g+1)+(T-1)\,\frac{g(g-1)}{2}\\ &\qquad -g^2\left(\frac{T(T+1)}{2}-1\right). \end{aligned}$$
Darum benötigt das endgültige Verfahren nur eine einzige Schleife über \(g\) mit konstant vielen Rechenoperationen pro Iteration.
Der Wert \(S(10,10)\) dient als Kontrollpunkt. Nach \(g\) gruppiert erhält man
$$\begin{aligned} g=1&:&&10+9+8+7+6+5+4+3+2=54,\\ g=2&:&&19+15+11+7=52,\\ g=3&:&&27+18=45,\\ g=4&:&&34,\\ g=5&:&&40. \end{aligned}$$
Für \(g\ge 6\) gilt bereits \(\lfloor 10/g\rfloor<2\), also gibt es keine gültigen Paare mehr. Insgesamt folgt
$$54+52+45+34+40=225,$$
genau wie im Implementierungs-Check.
Die C++-, Python- und Java-Implementierungen benutzen direkt die gruppierte Formel aus Schritt 6. Sie iterieren \(g\) von \(1\) bis \(p\), berechnen
$$T=\left\lfloor\frac{p}{g}\right\rfloor,$$
und überspringen den Fall \(T<2\), weil es dann kein gültiges \(t\) gibt. Andernfalls wird die geschlossene Form für den gesamten Block \(t=2,\dots,T\) ausgewertet: ein Faktor zählt die Anzahl der Terme, ein weiterer liefert die Summe der \(t\)-Werte, und daraus wird der Gesamtbeitrag dieses \(g\) gebildet.
Zur Laufzeit wird keinerlei Rekursion mehr ausgewertet. Python nutzt automatisch Ganzzahlen beliebiger Größe, Java verwendet für den laufenden Gesamtwert Ganzzahlarithmetik mit unbegrenzter Präzision, und C++ akkumuliert in vorzeichenloser 128-Bit-Arithmetik und wandelt das Endergebnis anschließend in Dezimaldarstellung um.
Die Schleife über \(g\) läuft genau \(p\)-mal, und jede Iteration benötigt nur \(O(1)\) Rechenzeit. Damit beträgt die Gesamtlaufzeit \(O(p)\), und der zusätzliche Speicherbedarf ist \(O(1)\). Gegenüber einer direkten Analyse jeder rekursiven Instanz ist das ein gewaltiger Gewinn.
Pozitif \(m\), \(k\) ve \(s\) için genelleştirilmiş McCarthy fonksiyonu
$$M_{m,k,s}(n)=\begin{cases}n-s,&n>m,\\M_{m,k,s}\!\left(M_{m,k,s}(n+k)\right),&n\le m.\end{cases}$$
şeklinde tanımlanır. Her \(1\le s<k\le p\) çifti için \(M_{m,k,s}(n)=n\) koşulunu sağlayan tüm sabit noktalar alınır ve bunların toplamı genel cevaba eklenir. Dolayısıyla hesaplanan büyüklük
$$S(p,m)=\sum_{1\le s<k\le p}\ \sum_{\substack{n\in\mathbb{Z}\\ M_{m,k,s}(n)=n}} n$$
olur. Her \((k,s)\) çifti için özyinelemeyi tek tek açmak mümkün değildir; çözüm önce sabit noktaların ne zaman var olduğunu ve hangi aralığı oluşturduğunu cebirsel olarak çıkarır.
Uygulamanın özü, iç içe özyinelemeyi bir bölünebilme problemine dönüştürmektir. Bundan sonra geriye yalnızca \(O(p)\) boyutlu tek bir toplam kalır.
Şunu koyalım:
$$g=k-s.$$
Problemde her zaman \(s<k\) olduğundan \(g>0\) olur. Kritik özdeşlik şu şekildedir: her \(n\le m\) için
$$M_{m,k,s}(n)=M_{m,k,s}(n+g).$$
Eğer \(n+k>m\) ise iç çağrı doğrudan taban duruma düşer:
$$M_{m,k,s}(n+k)=n+k-s=n+g,$$
dolayısıyla hemen \(M_{m,k,s}(n)=M_{m,k,s}(n+g)\) elde edilir.
Eğer \(n+k\le m\) ise aynı ifadeyi daha büyük argüman \(n+k\) için uygularız ve
$$M_{m,k,s}(n+k)=M_{m,k,s}(n+k+g)$$
buluruz. Bunu özyinelemeye geri koyunca
$$M_{m,k,s}(n)=M_{m,k,s}\!\left(M_{m,k,s}(n+k)\right)=M_{m,k,s}\!\left(M_{m,k,s}(n+k+g)\right)=M_{m,k,s}(n+g)$$
olur. Yani \(m\)'nin altında her özyineleme katmanı argümanı etkili biçimde tam \(g\) kadar yukarı taşır.
Şimdi \(n\le m\) olsun ve
$$n+qg>m$$
eşitsizliğini sağlayan en küçük pozitif \(q\)'yu seçelim. Bu
$$q=\left\lfloor\frac{m-n}{g}\right\rfloor+1$$
şeklinde yazılır. Adım 1'deki kaydırma özdeşliğini art arda kullanırsak
$$M_{m,k,s}(n)=M_{m,k,s}(n+qg)$$
olur. Artık argüman \(m\)'yi geçtiği için taban kuralı uygulanır ve
$$M_{m,k,s}(n)=n+qg-s$$
elde edilir. Böylece iç içe özyineleme tamamen kaybolur; \(q\) bilindiğinde yalnızca doğrusal bir ifade kalır.
Sabit nokta için \(M_{m,k,s}(n)=n\) gerekir. Yukarıdaki kapalı formu kullanırsak
$$n+qg-s=n,$$
yani
$$qg=s.$$
Demek ki sabit noktalar ancak ve ancak \(g\), \(s\)'yi bölüyorsa vardır. Bu durumda \(q=s/g\) olur ve \(q\)'nun en küçük seçim olması
$$n+(q-1)g\le m<n+qg$$
koşulunu verir. \(q=s/g\) yerine konursa
$$m-s<n\le m-s+g$$
elde edilir. O halde tüm sabit noktalar
$$\{m-s+1,\ m-s+2,\ \dots,\ m-s+g\}$$
aralığını oluşturur ve bu aralığın uzunluğu tam olarak \(g=k-s\)'dir. Eğer \(g\nmid s\) ise hiç sabit nokta yoktur.
\(g\mid s\) olduğunda
$$s=g(t-1),\qquad k=s+g=gt$$
yazabiliriz; burada \(t\ge 2\)'dir. \(k\le p\) koşulu da
$$2\le t\le \left\lfloor\frac{p}{g}\right\rfloor$$
haline gelir. Uygulamaların kullandığı parametrizasyon tam olarak budur. Böylece bütün \((k,s)\) çiftlerini dolaşmak yerine fark \(g\) ve bölüm \(t=k/g\) dolaşılır. Her geçerli çift bir kez görünür; geçersiz çiftler ise bölünebilme koşulu parametrizasyona gömülü olduğu için otomatik olarak elenir.
Geçerli bir çift için sabit noktalar
$$m-s+1,\ m-s+2,\ \dots,\ m-s+g$$
aritmetik dizisini oluşturur. Toplamları
$$\sum_{r=1}^{g}(m-s+r)=g(m-s)+\frac{g(g+1)}{2}$$
olur. \(s=g(t-1)\) yerine konursa
$$\Sigma(g,t)=g\bigl(m-g(t-1)\bigr)+\frac{g(g+1)}{2}$$
ve düzenlenince
$$\Sigma(g,t)=g(m+g+1)+\frac{g(g-1)}{2}-g^2t$$
elde edilir. Üç uygulamanın topladığı tam katkı budur.
Sabit bir \(g\) için
$$T=\left\lfloor\frac{p}{g}\right\rfloor$$
tanımını yapalım. O zaman \(t\), \(2,3,\dots,T\) aralığında gezer. Böylece
$$S(p,m)=\sum_{g=1}^{p}\ \sum_{t=2}^{\lfloor p/g\rfloor}\left(g(m+g+1)+\frac{g(g-1)}{2}-g^2t\right)$$
yazılır. İç toplam artık yalnızca aritmetik seri hesabıdır. Çünkü
$$\#\{2,\dots,T\}=T-1,\qquad \sum_{t=2}^{T} t=\frac{T(T+1)}{2}-1,$$
dolayısıyla sabit bir \(g\) için katkı
$$\begin{aligned} &(T-1)\,g(m+g+1)+(T-1)\,\frac{g(g-1)}{2}\\ &\qquad -g^2\left(\frac{T(T+1)}{2}-1\right) \end{aligned}$$
olur. Son programın yalnızca tek bir dış döngüye ihtiyaç duymasının sebebi budur.
\(S(10,10)\) değeri iyi bir kontrol örneğidir. Terimleri \(g\)'ye göre gruplayalım:
$$\begin{aligned} g=1&:&&10+9+8+7+6+5+4+3+2=54,\\ g=2&:&&19+15+11+7=52,\\ g=3&:&&27+18=45,\\ g=4&:&&34,\\ g=5&:&&40. \end{aligned}$$
\(g\ge 6\) için \(\lfloor 10/g\rfloor<2\) olduğundan katkı yoktur. Toplam
$$54+52+45+34+40=225$$
çıkar; bu da uygulamadaki doğrulama değeriyle aynıdır.
C++, Python ve Java uygulamaları doğrudan Adım 6'daki gruplanmış formülü uygular. \(g\), \(1\)'den \(p\)'ye kadar dolaşılır; sonra
$$T=\left\lfloor\frac{p}{g}\right\rfloor$$
hesaplanır ve \(T<2\) ise bu adım atlanır, çünkü geçerli \(t\) yoktur. Aksi halde \(t=2,\dots,T\) bloğunun tamamı kapalı formülle toplanır: bir terim kaç adet \(t\) olduğunu, bir terim de \(t\) değerlerinin aritmetik seri toplamını verir; ardından bu parçalar birleştirilerek o \(g\)'nin katkısı eklenir.
Çalışma anında özyineleme hiç yürütülmez. Python kendiliğinden keyfi büyüklükte tamsayılar kullanır, Java toplam için keyfi hassasiyetli tamsayı aritmetiğine başvurur, C++ ise işaretsiz 128 bit aritmetikle biriktirip sonucu onluk metne çevirerek yazar.
\(g\) döngüsü tam olarak \(p\) kez çalışır ve her yinelemede yalnızca \(O(1)\) aritmetik yapılır. Bu yüzden toplam süre \(O(p)\), ek bellek kullanımı \(O(1)\) olur. Bu yaklaşım, her özyinelemeli örneği ayrı ayrı çözmeye göre çok daha verimlidir.
Para enteros positivos \(m\), \(k\) y \(s\), la función generalizada de McCarthy se define por
$$M_{m,k,s}(n)=\begin{cases}n-s,&n>m,\\M_{m,k,s}\!\left(M_{m,k,s}(n+k)\right),&n\le m.\end{cases}$$
Para cada par \(1\le s<k\le p\), se toman todos los puntos fijos \(n\) tales que \(M_{m,k,s}(n)=n\), y esos puntos fijos se suman al total global. En otras palabras, hay que calcular
$$S(p,m)=\sum_{1\le s<k\le p}\ \sum_{\substack{n\in\mathbb{Z}\\ M_{m,k,s}(n)=n}} n.$$
Desenrollar la recursión para todos los pares \((k,s)\) sería completamente inviable, así que la solución primero identifica con exactitud cuándo existen puntos fijos y qué intervalo forman.
La idea central es convertir la recursión anidada en un problema de divisibilidad. Una vez hecho eso, la respuesta final se reduce a una sola suma de tamaño \(O(p)\).
Definimos
$$g=k-s.$$
Como siempre se cumple \(s<k\), tenemos \(g>0\). La identidad clave es que, para todo \(n\le m\),
$$M_{m,k,s}(n)=M_{m,k,s}(n+g).$$
Si \(n+k>m\), la llamada interna ya cae en el caso base:
$$M_{m,k,s}(n+k)=n+k-s=n+g,$$
y por tanto \(M_{m,k,s}(n)=M_{m,k,s}(n+g)\).
Si \(n+k\le m\), aplicamos la misma observación al argumento mayor \(n+k\) y obtenemos
$$M_{m,k,s}(n+k)=M_{m,k,s}(n+k+g).$$
Al sustituir esto en la definición recursiva resulta
$$M_{m,k,s}(n)=M_{m,k,s}\!\left(M_{m,k,s}(n+k)\right)=M_{m,k,s}\!\left(M_{m,k,s}(n+k+g)\right)=M_{m,k,s}(n+g).$$
Así, por debajo del umbral \(m\), cada capa recursiva avanza efectivamente el argumento en exactamente \(g\).
Tomemos \(n\le m\) y sea \(q\) el menor entero positivo tal que
$$n+qg>m.$$
Eso equivale a
$$q=\left\lfloor\frac{m-n}{g}\right\rfloor+1.$$
Aplicando repetidamente el desplazamiento del Paso 1 se obtiene
$$M_{m,k,s}(n)=M_{m,k,s}(n+qg).$$
Ahora el argumento ya está por encima de \(m\), así que entra en vigor el caso base y queda
$$M_{m,k,s}(n)=n+qg-s.$$
Con esto desaparece la recursión anidada: una vez conocido \(q\), solo queda una expresión lineal.
Un punto fijo satisface \(M_{m,k,s}(n)=n\). Sustituyendo la fórmula anterior:
$$n+qg-s=n,$$
de donde
$$qg=s.$$
Por tanto, hay puntos fijos si y solo si \(g\) divide a \(s\). En ese caso \(q=s/g\), y la minimalidad de \(q\) impone
$$n+(q-1)g\le m<n+qg.$$
Al reemplazar \(q=s/g\) aparece
$$m-s<n\le m-s+g.$$
Luego el conjunto completo de puntos fijos es el intervalo
$$\{m-s+1,\ m-s+2,\ \dots,\ m-s+g\},$$
de longitud exacta \(g=k-s\). Si \(g\nmid s\), no existe ningún punto fijo.
Siempre que \(g\mid s\), escribimos
$$s=g(t-1),\qquad k=s+g=gt,$$
con \(t\ge 2\). La cota \(k\le p\) pasa a ser
$$2\le t\le \left\lfloor\frac{p}{g}\right\rfloor.$$
Esta es exactamente la parametrización utilizada por las implementaciones. En vez de recorrer todos los pares \((k,s)\), se recorre la diferencia \(g\) y el cociente \(t=k/g\). Cada par válido aparece una sola vez y los pares inválidos desaparecen porque la condición de divisibilidad ya está incorporada.
Para un par válido, los puntos fijos forman la progresión aritmética
$$m-s+1,\ m-s+2,\ \dots,\ m-s+g.$$
Su suma es
$$\sum_{r=1}^{g}(m-s+r)=g(m-s)+\frac{g(g+1)}{2}.$$
Sustituyendo \(s=g(t-1)\) obtenemos
$$\Sigma(g,t)=g\bigl(m-g(t-1)\bigr)+\frac{g(g+1)}{2},$$
y al reorganizar términos resulta
$$\Sigma(g,t)=g(m+g+1)+\frac{g(g-1)}{2}-g^2t.$$
Esa es exactamente la contribución por par que agregan las implementaciones.
Para un \(g\) fijo definimos
$$T=\left\lfloor\frac{p}{g}\right\rfloor.$$
Entonces \(t\) recorre el intervalo consecutivo \(2,3,\dots,T\). Por tanto,
$$S(p,m)=\sum_{g=1}^{p}\ \sum_{t=2}^{\lfloor p/g\rfloor}\left(g(m+g+1)+\frac{g(g-1)}{2}-g^2t\right).$$
La suma interior ya es solo álgebra de progresiones. Como
$$\#\{2,\dots,T\}=T-1,\qquad \sum_{t=2}^{T} t=\frac{T(T+1)}{2}-1,$$
la contribución de un \(g\) fijo queda
$$\begin{aligned} &(T-1)\,g(m+g+1)+(T-1)\,\frac{g(g-1)}{2}\\ &\qquad -g^2\left(\frac{T(T+1)}{2}-1\right). \end{aligned}$$
Por eso el programa final solo necesita un único bucle sobre \(g\) y trabajo constante dentro de cada iteración.
El valor \(S(10,10)\) es una buena comprobación intermedia. Agrupando por \(g\) se obtiene
$$\begin{aligned} g=1&:&&10+9+8+7+6+5+4+3+2=54,\\ g=2&:&&19+15+11+7=52,\\ g=3&:&&27+18=45,\\ g=4&:&&34,\\ g=5&:&&40. \end{aligned}$$
Para \(g\ge 6\), ya se tiene \(\lfloor 10/g\rfloor<2\), así que no hay pares válidos. La suma total es
$$54+52+45+34+40=225,$$
que coincide con el valor de verificación de la implementación.
Las implementaciones en C++, Python y Java usan directamente la fórmula agrupada del Paso 6. Recorren \(g\) desde \(1\) hasta \(p\), calculan
$$T=\left\lfloor\frac{p}{g}\right\rfloor,$$
y descartan el caso \(T<2\), porque entonces no existe ningún \(t\) válido. En caso contrario evalúan la forma cerrada para todo el bloque \(t=2,\dots,T\): un factor cuenta cuántos términos hay, otro factor proporciona la suma aritmética de los valores de \(t\), y las piezas resultantes se combinan en la contribución correspondiente a ese \(g\).
La recursión no se ejecuta en tiempo de ejecución. Python se apoya en enteros de precisión arbitraria de manera natural, Java usa aritmética entera de precisión arbitraria para el acumulado, y C++ acumula en aritmética sin signo de 128 bits antes de convertir el resultado final a texto decimal.
El bucle sobre \(g\) se ejecuta exactamente \(p\) veces, y cada iteración hace solo \(O(1)\) operaciones aritméticas. Por ello, el tiempo total es \(O(p)\) y la memoria auxiliar es \(O(1)\). Es una mejora enorme frente a intentar estudiar cada instancia recursiva por separado.
对正整数 \(m\)、\(k\)、\(s\)，广义 McCarthy 函数定义为
$$M_{m,k,s}(n)=\begin{cases}n-s,&n>m,\\M_{m,k,s}\!\left(M_{m,k,s}(n+k)\right),&n\le m.\end{cases}$$
对于每个满足 \(1\le s<k\le p\) 的参数对，我们把所有满足 \(M_{m,k,s}(n)=n\) 的不动点 \(n\) 全部找出来，并把这些不动点加入总和。因此要求的量是
$$S(p,m)=\sum_{1\le s<k\le p}\ \sum_{\substack{n\in\mathbb{Z}\\ M_{m,k,s}(n)=n}} n.$$
如果对每个 \((k,s)\) 都直接展开递归，规模会大得无法接受。真正可行的办法，是先从数学上判定不动点何时存在、存在时落在哪个整数区间里，然后再整体求和。
实现采用的核心思路，是把嵌套递归改写成一个整除条件问题。这样一来，最后的答案就能整理成一个仅需 \(O(p)\) 次迭代的求和公式。
令
$$g=k-s.$$
由于题目只考虑 \(s<k\)，所以总有 \(g>0\)。最关键的等式是：对所有 \(n\le m\)，都有
$$M_{m,k,s}(n)=M_{m,k,s}(n+g).$$
先看最直接的情形。如果 \(n+k>m\)，那么内层调用已经进入基例，于是
$$M_{m,k,s}(n+k)=n+k-s=n+g,$$
从而立刻得到 \(M_{m,k,s}(n)=M_{m,k,s}(n+g)\)。
如果 \(n+k\le m\)，则把同样的观察应用到更大的参数 \(n+k\) 上，得到
$$M_{m,k,s}(n+k)=M_{m,k,s}(n+k+g).$$
把它代回递归定义，便有
$$M_{m,k,s}(n)=M_{m,k,s}\!\left(M_{m,k,s}(n+k)\right)=M_{m,k,s}\!\left(M_{m,k,s}(n+k+g)\right)=M_{m,k,s}(n+g).$$
这说明在阈值 \(m\) 以下，递归的实际效果并不是“复杂地双重展开”，而是把输入不断向上平移 \(g\)。
固定一个 \(n\le m\)。设 \(q\) 是满足
$$n+qg>m$$
的最小正整数。那么
$$q=\left\lfloor\frac{m-n}{g}\right\rfloor+1.$$
利用步骤 1 的平移关系，可以把函数值一直推到第一次越过阈值的位置：
$$M_{m,k,s}(n)=M_{m,k,s}(n+qg).$$
因为 \(n+qg>m\)，此时已经落入基例，所以
$$M_{m,k,s}(n)=n+qg-s.$$
这一步非常重要，因为它把原先的嵌套递归彻底压缩成了一个线性表达式。只要知道“要平移多少次”也就是 \(q\)，函数值就完全确定了。
不动点满足 \(M_{m,k,s}(n)=n\)。代入上面的闭式，得到
$$n+qg-s=n,$$
也就是
$$qg=s.$$
因此，不动点存在的充要条件是 \(g\mid s\)。如果这个整除关系不成立，那么无论怎样选 \(n\)，都不可能满足不动点方程。
当 \(g\mid s\) 时，必有
$$q=\frac{s}{g}.$$
同时，由于 \(q\) 是最小的越界次数，还必须满足
$$n+(q-1)g\le m<n+qg.$$
把 \(q=s/g\) 代入可得
$$m-s<n\le m-s+g.$$
所以全部不动点恰好构成区间
$$\{m-s+1,\ m-s+2,\ \dots,\ m-s+g\}.$$
这个区间的长度正好是 \(g=k-s\)。换句话说，一个参数对要么一个不动点都没有，要么就给出一段长度为 \(g\) 的连续整数区间。
既然只有 \(g\mid s\) 的情况才有贡献，就把所有有效对写成
$$s=g(t-1),\qquad k=s+g=gt,$$
其中 \(t\ge 2\)。再利用约束 \(k\le p\)，就得到
$$2\le t\le \left\lfloor\frac{p}{g}\right\rfloor.$$
这正是实现里采用的枚举方式。程序并不显式遍历所有 \((k,s)\)，而是先选差值 \(g\)，再选商 \(t=k/g\)。这样每个有效参数对只出现一次，而所有无效参数对都会被自动排除，因为整除条件已经吸收到参数化里了。
对固定的有效参数对，不动点是一个等差区间
$$m-s+1,\ m-s+2,\ \dots,\ m-s+g.$$
它们的和为
$$\sum_{r=1}^{g}(m-s+r)=g(m-s)+\frac{g(g+1)}{2}.$$
再把 \(s=g(t-1)\) 代回去：
$$\Sigma(g,t)=g\bigl(m-g(t-1)\bigr)+\frac{g(g+1)}{2}.$$
整理后可写成
$$\Sigma(g,t)=g(m+g+1)+\frac{g(g-1)}{2}-g^2t.$$
这就是每个有效参数对在总答案中产生的精确贡献，也是三种语言实现所累加的核心表达式。
对固定的 \(g\)，记
$$T=\left\lfloor\frac{p}{g}\right\rfloor.$$
则 \(t\) 的范围就是连续区间 \(2,3,\dots,T\)。因此总和可以写成
$$S(p,m)=\sum_{g=1}^{p}\ \sum_{t=2}^{\lfloor p/g\rfloor}\left(g(m+g+1)+\frac{g(g-1)}{2}-g^2t\right).$$
这里内层和已经完全变成等差数列求和。因为
$$\#\{2,\dots,T\}=T-1,\qquad \sum_{t=2}^{T} t=\frac{T(T+1)}{2}-1,$$
所以固定一个 \(g\) 的总贡献为
$$\begin{aligned} &(T-1)\,g(m+g+1)+(T-1)\,\frac{g(g-1)}{2}\\ &\qquad -g^2\left(\frac{T(T+1)}{2}-1\right). \end{aligned}$$
这就是最终程序的来源。每个 \(g\) 只需常数次整数运算，不再需要真正执行递归。
\(S(10,10)\) 是一个非常好的校验点。按 \(g\) 分组后：
$$\begin{aligned} g=1&:&&10+9+8+7+6+5+4+3+2=54,\\ g=2&:&&19+15+11+7=52,\\ g=3&:&&27+18=45,\\ g=4&:&&34,\\ g=5&:&&40. \end{aligned}$$
当 \(g\ge 6\) 时，\(\lfloor 10/g\rfloor<2\)，已经没有合法的 \(t\)。于是
$$54+52+45+34+40=225,$$
恰好与实现中的校验值一致。
C++、Python 和 Java 实现都直接使用步骤 6 的分组公式。它们让 \(g\) 从 \(1\) 循环到 \(p\)，计算
$$T=\left\lfloor\frac{p}{g}\right\rfloor,$$
如果 \(T<2\)，就说明没有合法的 \(t\)，当前 \(g\) 直接跳过。否则，程序用闭式一次性求出整个区间 \(t=2,\dots,T\) 的贡献：一个部分负责“有多少项”，一个部分负责“这些 \(t\) 的和是多少”，然后把三块代数项合并成这个 \(g\) 的总贡献。
运行时不会真的展开递归。Python 自带任意精度整数，Java 对累计总和使用任意精度整数运算，C++ 则使用无符号 128 位整数进行累加，并在最后把结果转换成十进制字符串输出。
外层关于 \(g\) 的循环总共执行 \(p\) 次，而每次迭代只做 \(O(1)\) 次算术运算。因此总时间复杂度是 \(O(p)\)，额外空间复杂度是 \(O(1)\)。与逐个研究递归过程相比，这个化简把问题压缩到了线性规模。
Для положительных целых \(m\), \(k\) и \(s\) обобщенная функция Маккарти задается формулой
$$M_{m,k,s}(n)=\begin{cases}n-s,&n>m,\\M_{m,k,s}\!\left(M_{m,k,s}(n+k)\right),&n\le m.\end{cases}$$
Для каждой пары \(1\le s<k\le p\) рассматриваются все неподвижные точки \(n\), удовлетворяющие \(M_{m,k,s}(n)=n\), и эти значения добавляются к общему ответу. Следовательно, требуется вычислить
$$S(p,m)=\sum_{1\le s<k\le p}\ \sum_{\substack{n\in\mathbb{Z}\\ M_{m,k,s}(n)=n}} n.$$
Если пытаться разворачивать рекурсию отдельно для каждой пары \((k,s)\), задача становится непрактичной. Поэтому решение сначала точно описывает, когда неподвижные точки вообще существуют и какой интервал они образуют.
Основа решения состоит в том, чтобы заменить вложенную рекурсию условием делимости. После этого весь ответ сводится к одной сумме порядка \(O(p)\).
Положим
$$g=k-s.$$
Так как всегда \(s<k\), имеем \(g>0\). Ключевое тождество для любого \(n\le m\) выглядит так:
$$M_{m,k,s}(n)=M_{m,k,s}(n+g).$$
Если \(n+k>m\), внутренний вызов уже попадает в базовый случай:
$$M_{m,k,s}(n+k)=n+k-s=n+g,$$
поэтому немедленно получаем \(M_{m,k,s}(n)=M_{m,k,s}(n+g)\).
Если же \(n+k\le m\), применяем ту же идею к большему аргументу \(n+k\) и имеем
$$M_{m,k,s}(n+k)=M_{m,k,s}(n+k+g).$$
Подставляя это в рекурсивное определение, получаем
$$M_{m,k,s}(n)=M_{m,k,s}\!\left(M_{m,k,s}(n+k)\right)=M_{m,k,s}\!\left(M_{m,k,s}(n+k+g)\right)=M_{m,k,s}(n+g).$$
Значит, ниже порога \(m\) эффект рекурсии эквивалентен последовательному сдвигу аргумента вверх на \(g\).
Пусть \(n\le m\), а \(q\) — наименьшее положительное целое, для которого
$$n+qg>m.$$
Эквивалентно,
$$q=\left\lfloor\frac{m-n}{g}\right\rfloor+1.$$
Многократно применяя тождество из шага 1, можно дойти до первого значения выше порога:
$$M_{m,k,s}(n)=M_{m,k,s}(n+qg).$$
Теперь действует базовое правило, и потому
$$M_{m,k,s}(n)=n+qg-s.$$
Именно здесь сложная вложенная рекурсия исчезает: после определения \(q\) значение функции выражается линейно.
Неподвижная точка должна удовлетворять равенству \(M_{m,k,s}(n)=n\). Подставляя закрытую формулу, получаем
$$n+qg-s=n,$$
то есть
$$qg=s.$$
Следовательно, неподвижные точки существуют тогда и только тогда, когда \(g\) делит \(s\). В этом случае \(q=s/g\), а условие минимальности для \(q\) имеет вид
$$n+(q-1)g\le m<n+qg.$$
После подстановки \(q=s/g\) получаем
$$m-s<n\le m-s+g.$$
Значит, все неподвижные точки образуют интервал
$$\{m-s+1,\ m-s+2,\ \dots,\ m-s+g\},$$
содержащий ровно \(g=k-s\) целых чисел. Если же \(g\nmid s\), вклад этой пары равен нулю.
Когда \(g\mid s\), можно написать
$$s=g(t-1),\qquad k=s+g=gt,$$
где \(t\ge 2\). Ограничение \(k\le p\) превращается в
$$2\le t\le \left\lfloor\frac{p}{g}\right\rfloor.$$
Именно этой параметризацией пользуются реализации. Вместо перебора всех пар \((k,s)\) они перебирают разность \(g\) и частное \(t=k/g\). Каждая допустимая пара появляется ровно один раз, а все недопустимые автоматически отсеиваются, потому что условие делимости уже встроено в такую запись.
Для фиксированной допустимой пары неподвижные точки составляют арифметический интервал
$$m-s+1,\ m-s+2,\ \dots,\ m-s+g.$$
Их сумма равна
$$\sum_{r=1}^{g}(m-s+r)=g(m-s)+\frac{g(g+1)}{2}.$$
Подставляя \(s=g(t-1)\), получаем
$$\Sigma(g,t)=g\bigl(m-g(t-1)\bigr)+\frac{g(g+1)}{2}.$$
После упрощения имеем
$$\Sigma(g,t)=g(m+g+1)+\frac{g(g-1)}{2}-g^2t.$$
Это и есть точный вклад одной пары параметров в итоговую сумму.
Для фиксированного \(g\) обозначим
$$T=\left\lfloor\frac{p}{g}\right\rfloor.$$
Тогда \(t\) пробегает последовательность \(2,3,\dots,T\). Значит,
$$S(p,m)=\sum_{g=1}^{p}\ \sum_{t=2}^{\lfloor p/g\rfloor}\left(g(m+g+1)+\frac{g(g-1)}{2}-g^2t\right).$$
Внутренняя сумма теперь полностью сводится к формулам для арифметической прогрессии. Так как
$$\#\{2,\dots,T\}=T-1,\qquad \sum_{t=2}^{T} t=\frac{T(T+1)}{2}-1,$$
вклад фиксированного \(g\) равен
$$\begin{aligned} &(T-1)\,g(m+g+1)+(T-1)\,\frac{g(g-1)}{2}\\ &\qquad -g^2\left(\frac{T(T+1)}{2}-1\right). \end{aligned}$$
Именно поэтому окончательный алгоритм обходится одним циклом по \(g\) и константным числом арифметических операций внутри цикла.
Значение \(S(10,10)\) удобно использовать как контроль. После группировки по \(g\) получаем
$$\begin{aligned} g=1&:&&10+9+8+7+6+5+4+3+2=54,\\ g=2&:&&19+15+11+7=52,\\ g=3&:&&27+18=45,\\ g=4&:&&34,\\ g=5&:&&40. \end{aligned}$$
При \(g\ge 6\) уже выполняется \(\lfloor 10/g\rfloor<2\), то есть допустимых значений \(t\) больше нет. Поэтому
$$54+52+45+34+40=225,$$
что в точности совпадает с проверочным значением реализации.
Реализации на C++, Python и Java напрямую используют сгруппированную формулу из шага 6. Они перебирают \(g\) от \(1\) до \(p\), вычисляют
$$T=\left\lfloor\frac{p}{g}\right\rfloor,$$
и пропускают случай \(T<2\), потому что тогда не существует допустимого \(t\). Иначе сразу вычисляется закрытая формула для всего блока \(t=2,\dots,T\): один множитель отвечает за число слагаемых, другой за сумму значений \(t\), а затем все части объединяются во вклад данного \(g\).
Рекурсия во время выполнения не раскрывается вовсе. Python использует целые числа произвольной длины автоматически, Java ведет накопление ответа с помощью целочисленной арифметики произвольной точности, а C++ суммирует в беззнаковом 128-битном типе и затем переводит результат в десятичную строку.
Цикл по \(g\) выполняется ровно \(p\) раз, и каждая итерация делает только \(O(1)\) арифметических действий. Значит, итоговая временная сложность равна \(O(p)\), а дополнительная память — \(O(1)\). По сравнению с прямым анализом рекурсивного процесса это принципиально более эффективный подход.
لأعداد صحيحة موجبة \(m\) و\(k\) و\(s\)، تُعرَّف دالة مكارثي المعممة بالصيغة
$$M_{m,k,s}(n)=\begin{cases}n-s,&n>m,\\M_{m,k,s}\!\left(M_{m,k,s}(n+k)\right),&n\le m.\end{cases}$$
ولكل زوج يحقق \(1\le s<k\le p\)، نأخذ جميع النقاط الثابتة \(n\) التي تحقق \(M_{m,k,s}(n)=n\)، ثم نجمع هذه القيم في المجموع الكلي. إذن المطلوب هو حساب
$$S(p,m)=\sum_{1\le s<k\le p}\ \sum_{\substack{n\in\mathbb{Z}\\ M_{m,k,s}(n)=n}} n.$$
تفكيك الاستدعاء العودي مباشرة لكل زوج \((k,s)\) غير عملي تمامًا. لذلك يبدأ الحل بتحديد متى توجد نقاط ثابتة أصلًا، وما هو المجال العددي الذي تشغله.
الفكرة الأساسية هي تحويل العودية المتداخلة إلى مسألة تتعلق بالقابلية للقسمة. وبعد هذا التحويل يصبح الجواب كله مجموعًا واحدًا من رتبة \(O(p)\).
نضع
$$g=k-s.$$
وبما أن \(s<k\)، فلدينا دائمًا \(g>0\). والهوية الحاسمة هي أنه لكل \(n\le m\)،
$$M_{m,k,s}(n)=M_{m,k,s}(n+g).$$
إذا كان \(n+k>m\)، فإن النداء الداخلي يقع مباشرة في الحالة الأساسية:
$$M_{m,k,s}(n+k)=n+k-s=n+g,$$
ومن ثم نحصل فورًا على \(M_{m,k,s}(n)=M_{m,k,s}(n+g)\).
أما إذا كان \(n+k\le m\)، فنطبق الملاحظة نفسها على القيمة الأكبر \(n+k\) فنجد
$$M_{m,k,s}(n+k)=M_{m,k,s}(n+k+g).$$
وبالتعويض داخل التعريف العودي نحصل على
$$M_{m,k,s}(n)=M_{m,k,s}\!\left(M_{m,k,s}(n+k)\right)=M_{m,k,s}\!\left(M_{m,k,s}(n+k+g)\right)=M_{m,k,s}(n+g).$$
وهذا يعني أن العودية تحت العتبة \(m\) لا تفعل شيئًا غامضًا، بل تدفع المدخل إلى الأعلى بمقدار ثابت هو \(g\).
لنأخذ \(n\le m\)، ولتكن \(q\) أصغر قيمة صحيحة موجبة تحقق
$$n+qg>m.$$
وهذا يكافئ
$$q=\left\lfloor\frac{m-n}{g}\right\rfloor+1.$$
وباستخدام هوية الإزاحة من الخطوة 1 عدة مرات، يمكن دفع قيمة الدالة حتى أول موضع يتجاوز العتبة:
$$M_{m,k,s}(n)=M_{m,k,s}(n+qg).$$
وبما أن \(n+qg>m\)، فإننا نصل إلى الحالة الأساسية، وبالتالي
$$M_{m,k,s}(n)=n+qg-s.$$
هنا تختفي العودية المتداخلة تمامًا، ويتحول كل شيء إلى تعبير خطي بسيط بمجرد معرفة \(q\).
النقطة الثابتة تحقق \(M_{m,k,s}(n)=n\). وبالتعويض في الصيغة المغلقة نحصل على
$$n+qg-s=n,$$
أي
$$qg=s.$$
إذن توجد نقاط ثابتة إذا وفقط إذا كان \(g\) يقسم \(s\). وعند تحقق ذلك يكون
$$q=\frac{s}{g}.$$
لكن \(q\) هو أيضًا أصغر عدد من الإزاحات اللازمة لتجاوز \(m\)، ولذلك يجب أن يتحقق
$$n+(q-1)g\le m<n+qg.$$
وبإحلال \(q=s/g\) نحصل على
$$m-s<n\le m-s+g.$$
إذن جميع النقاط الثابتة تشكل المجال
$$\{m-s+1,\ m-s+2,\ \dots,\ m-s+g\},$$
وطوله يساوي تمامًا \(g=k-s\). وإذا لم يكن \(g\) قاسمًا لـ \(s\)، فلا توجد أي نقطة ثابتة.
عندما يكون \(g\mid s\)، يمكن كتابة
$$s=g(t-1),\qquad k=s+g=gt,$$
حيث \(t\ge 2\). ومن الشرط \(k\le p\) نحصل على
$$2\le t\le \left\lfloor\frac{p}{g}\right\rfloor.$$
وهذا هو بالضبط الترميز الذي تستعمله التطبيقات. فبدل المرور على كل زوج \((k,s)\) مباشرة، يجري المرور على الفرق \(g\) ثم على النسبة \(t=k/g\). كل زوج صالح يظهر مرة واحدة فقط، وكل زوج غير صالح يختفي تلقائيًا لأن شرط القسمة صار جزءًا من الترميز نفسه.
بالنسبة إلى زوج صالح، تكون النقاط الثابتة هي المتتالية الحسابية
$$m-s+1,\ m-s+2,\ \dots,\ m-s+g.$$
ومجموعها يساوي
$$\sum_{r=1}^{g}(m-s+r)=g(m-s)+\frac{g(g+1)}{2}.$$
ثم نعوض \(s=g(t-1)\) فنحصل على
$$\Sigma(g,t)=g\bigl(m-g(t-1)\bigr)+\frac{g(g+1)}{2}.$$
وبإعادة الترتيب يصبح التعبير
$$\Sigma(g,t)=g(m+g+1)+\frac{g(g-1)}{2}-g^2t.$$
وهذا هو الإسهام الدقيق لكل زوج صالح في المجموع النهائي.
لـ \(g\) ثابت، نعرف
$$T=\left\lfloor\frac{p}{g}\right\rfloor.$$
وعندها يمر \(t\) على المجال المتتالي \(2,3,\dots,T\). لذلك يمكن كتابة
$$S(p,m)=\sum_{g=1}^{p}\ \sum_{t=2}^{\lfloor p/g\rfloor}\left(g(m+g+1)+\frac{g(g-1)}{2}-g^2t\right).$$
وأصبح الجمع الداخلي الآن مجرد حساب لمتتالية حسابية، لأن
$$\#\{2,\dots,T\}=T-1,\qquad \sum_{t=2}^{T} t=\frac{T(T+1)}{2}-1.$$
ومن ثم يكون إسهام \(g\) الواحد هو
$$\begin{aligned} &(T-1)\,g(m+g+1)+(T-1)\,\frac{g(g-1)}{2}\\ &\qquad -g^2\left(\frac{T(T+1)}{2}-1\right). \end{aligned}$$
لهذا السبب تحتاج الخوارزمية النهائية إلى حلقة واحدة فقط على \(g\)، مع عدد ثابت من العمليات داخل كل دورة.
القيمة \(S(10,10)\) تمثل نقطة فحص جيدة. بعد التجميع حسب \(g\) نحصل على
$$\begin{aligned} g=1&:&&10+9+8+7+6+5+4+3+2=54,\\ g=2&:&&19+15+11+7=52,\\ g=3&:&&27+18=45,\\ g=4&:&&34,\\ g=5&:&&40. \end{aligned}$$
وعندما \(g\ge 6\)، يكون \(\lfloor 10/g\rfloor<2\)، فلا يبقى أي \(t\) صالح. لذلك
$$54+52+45+34+40=225,$$
وهو نفس مقدار التحقق الذي تعطيه التطبيقات.
تعتمد تطبيقات C++ وPython وJava مباشرة على الصيغة المجمعة في الخطوة 6. فهي تمر على \(g\) من \(1\) إلى \(p\)، ثم تحسب
$$T=\left\lfloor\frac{p}{g}\right\rfloor,$$
وتتجاوز الحالة \(T<2\) لأن هذا يعني عدم وجود \(t\) صالح. وفي غير ذلك تحسب الصيغة المغلقة للكتلة الكاملة \(t=2,\dots,T\): جزء منها يحسب عدد الحدود، وجزء آخر يعطي مجموع قيم \(t\)، ثم تُدمج الحدود الجبرية الثلاثة لإنتاج مساهمة ذلك \(g\).
لا تُنفذ العودية فعلًا أثناء التشغيل. Python تستفيد تلقائيًا من الأعداد الصحيحة ذات الدقة غير المحدودة، وJava تستخدم حسابًا صحيحًا بدقة غير محدودة للمجموع التراكمي، أما C++ فتجمع باستخدام حساب غير موقع بعرض 128 بت ثم تحول الناتج النهائي إلى نص عشري.
تعمل الحلقة الخارجية على \(g\) عددًا مقداره \(p\) من المرات بالضبط، وكل دورة تنفذ \(O(1)\) من العمليات الحسابية فقط. لذلك يكون الزمن الكلي \(O(p)\)، واستهلاك الذاكرة الإضافية \(O(1)\). وهذا أبسط بكثير من محاولة دراسة كل حالة عودية على حدة.