For each base \(B=6k+3\) with \(2 \le k \le 300\), we consider every integer \(i\) with \(0 \lt i \lt B^5\), write it as a 5-digit base-\(B\) string with leading zeros allowed, sort its digits in decreasing and increasing order, subtract, and repeat. For these bases, the 5-digit routine has a unique non-zero Kaprekar constant \(C_B\).
Define \(s_B(i)=0\) when \(i=C_B\) or when the 5 digits of \(i\) are all equal, and otherwise let \(s_B(i)\) be the number of iterations needed to reach \(C_B\). Then
$$S(B)=\sum_{0 \lt i \lt B^5} s_B(i),$$
and the goal is the last \(18\) digits of
$$\sum_{k=2}^{300} S(6k+3).$$
Let the sorted digits of the current 5-digit string be
$$x_0 \le x_1 \le x_2 \le x_3 \le x_4.$$
The descending and ascending numbers are
$$N_{\downarrow}=x_4 B^4 + x_3 B^3 + x_2 B^2 + x_1 B + x_0,$$
$$N_{\uparrow}=x_0 B^4 + x_1 B^3 + x_2 B^2 + x_3 B + x_4.$$
The Kaprekar subtraction is therefore
$$N_{\downarrow}-N_{\uparrow}=(x_4-x_0)(B^4-1)+(x_3-x_1)(B^3-B).$$
So the next value depends only on the two outer gaps
$$u=x_4-x_0,\qquad v=x_3-x_1,$$
with \(0 \le v \le u \le B-1\). Define
$$R_B(u,v)=u(B^4-1)+vB(B^2-1).$$
To advance one step, the implementation writes \(R_B(u,v)\) in base \(B\), sorts its five digits, and recomputes the new pair \((u',v')\). This gives a deterministic transition
$$T_B(u,v)=(u',v').$$
The original \(B^5\) search space is thus reduced to only \(O(B^2)\) gap states.
Because \(B=6k+3\), the base is divisible by \(3\). Write
$$B=3m,$$
where \(m\) is odd. The non-zero fixed state used by the routine is
$$u=2m,\qquad v=m.$$
Substituting these values into the closed form gives
$$R_B(2m,m)=2m(B^4-1)+m(B^3-B)=2mB^4+mB^3-mB-2m.$$
In base \(B\), this is exactly
$$R_B(2m,m)=(2m,\; m-1,\; B-1,\; 2m-1,\; m)_B.$$
Its sorted digit multiset is
$$\{m-1,\; m,\; 2m-1,\; 2m,\; B-1\},$$
so the outer differences remain
$$u=(B-1)-(m-1)=2m,\qquad v=(2m)-m=m,$$
hence
$$T_B(2m,m)=(2m,m).$$
This is the Kaprekar constant state. For example, when \(B=15\) we have \(m=5\), so the constant is
$$C_{15}=(10,4,14,9,5)_{15},$$
and when \(B=21\) we get
$$C_{21}=(14,6,20,13,7)_{21}.$$
Let \(M_B(u,v)\) be the number of 5-digit base-\(B\) strings whose sorted digits have outer gaps \((u,v)\). Fix \(u \gt 0\), let the smallest digit be \(a\), and let the largest digit be \(e=a+u\). There are exactly
$$B-u$$
possible values of \(a\). For each such \(a\), the count depends only on the equality pattern of the middle digits. The constants \(20,30,60,120\) below are multinomial counts such as \(5!/3!\), \(5!/(2!2!)\), \(5!/2!\), and \(5!\).
Case \(v=0\). Then the second and fourth sorted digits are equal, so the multiset has the form
$$[a,c,c,c,e].$$
If \(c=a\) or \(c=e\), there are \(5\) permutations in each case. If \(a \lt c \lt e\), there are \(u-1\) choices for \(c\), each with \(20\) permutations. Therefore
$$M_B(u,0)=(B-u)\bigl(5+5+20(u-1)\bigr),\qquad u \ge 1.$$
Case \(u=v\). Now the second digit must equal the minimum and the fourth digit must equal the maximum, so the multiset is
$$[a,a,c,e,e].$$
If \(c=a\) or \(c=e\), there are \(10\) permutations in each case. If \(a \lt c \lt e\), there are \(u-1\) choices and \(30\) permutations each. Hence
$$M_B(u,u)=(B-u)\bigl(10+10+30(u-1)\bigr),\qquad u \ge 1.$$
Case \(0 \lt v \lt u\). There are two boundary families where one inner digit collapses onto an endpoint:
$$[a,a,c,d,e],\quad [a,a,d,d,e],\quad [a,a,a,d,e],$$
and symmetrically
$$[a,b,c,e,e],\quad [a,b,b,e,e],\quad [a,b,e,e,e].$$
These contribute
$$2\bigl(60(v-1)+30+20\bigr).$$
If both inner gaps are strict, choose \(b\) with \(a \lt b \lt e-v\), so there are \(u-v-1\) possibilities. Then \(d=b+v\), and the remaining multisets are
$$[a,b,b,d,e],\qquad [a,b,d,d,e],\qquad [a,b,c,d,e],$$
where in the last form the middle digit satisfies \(b \lt c \lt d\), giving \(v-1\) choices. Their total contribution is
$$60(u-v-1)+60(u-v-1)+120(u-v-1)(v-1).$$
Combining everything,
$$M_B(u,v)=(B-u)\Bigl(100+120(v-1)+120(u-v-1)+120(u-v-1)(v-1)\Bigr),$$
for \(0 \lt v \lt u\).
Every state \((u,v)\) has exactly one outgoing edge, namely \(T_B(u,v)\). So the gap states form a functional graph. Let \(D_B(u,v)\) be the number of additional Kaprekar steps needed after the first subtraction has produced the state \((u,v)\). Then
$$D_B(u,v)= \begin{cases} 0,& T_B(u,v)=(u,v),\\ 1 + D_B\!\bigl(T_B(u,v)\bigr),& T_B(u,v)\ne(u,v). \end{cases}$$
The implementation memoizes this recurrence, so each state depth is computed only once.
Among the \(B^5-1\) positive 5-digit strings, exactly \(B-1\) have all digits equal, and the Kaprekar constant itself also contributes \(0\). Every other starting value contributes one unavoidable first iteration before the gap-state depth takes over. Therefore the universal first-step contribution is
$$B^5-1-(B-1)-1=B^5-B-1.$$
After that first step, only the gap state matters, so
$$\boxed{S(B)=B^5-B-1+\sum_{u=1}^{B-1}\sum_{v=0}^{u} M_B(u,v)\,D_B(u,v).}$$
This is exactly the quantity accumulated by the implementation. The published checkpoints
$$S(15)=5274369,\qquad S(111)=400668930299$$
are recovered by this formula.
The C++, Python, and Java implementations all use the same mathematical reduction. For each base \(B\), they enumerate the triangular set of gap states \((u,v)\), compute the deterministic successor by evaluating \(R_B(u,v)\) and sorting its five base-\(B\) digits, memoize the depth to the fixed state, multiply that depth by the corresponding multiplicity \(M_B(u,v)\), and finally add the universal offset \(B^5-B-1\). All arithmetic is reduced modulo \(10^{18}\) because only the last \(18\) digits are required.
For a fixed base \(B\), the number of states is \(O(B^2)\). Each transition uses only constant-time arithmetic plus a sort of five digits, which is also constant. Memoization ensures that each state depth is evaluated once, so the total work per base is \(O(B^2)\) time and \(O(B^2)\) memory. This is exponentially smaller than brute-forcing all \(B^5\) starting values.
Für jede Basis \(B=6k+3\) mit \(2 \le k \le 300\) betrachten wir alle ganzen Zahlen \(i\) mit \(0 \lt i \lt B^5\), schreiben sie mit führenden Nullen als 5-stellige Zahl zur Basis \(B\), sortieren die Ziffern absteigend und aufsteigend, subtrahieren und wiederholen den Vorgang. Für diese Basen besitzt die 5-stellige Routine eine eindeutige von Null verschiedene Kaprekar-Konstante \(C_B\).
Definiert sei \(s_B(i)=0\), falls \(i=C_B\) ist oder alle fünf Ziffern von \(i\) gleich sind; andernfalls sei \(s_B(i)\) die Anzahl der Iterationen bis \(C_B\) erreicht wird. Dann ist
$$S(B)=\sum_{0 \lt i \lt B^5} s_B(i),$$
und gesucht sind die letzten \(18\) Ziffern von
$$\sum_{k=2}^{300} S(6k+3).$$
Seien die sortierten Ziffern
$$x_0 \le x_1 \le x_2 \le x_3 \le x_4.$$
Dann lauten die absteigende und die aufsteigende Zahl
$$N_{\downarrow}=x_4 B^4 + x_3 B^3 + x_2 B^2 + x_1 B + x_0,$$
$$N_{\uparrow}=x_0 B^4 + x_1 B^3 + x_2 B^2 + x_3 B + x_4.$$
Ihre Differenz ist
$$N_{\downarrow}-N_{\uparrow}=(x_4-x_0)(B^4-1)+(x_3-x_1)(B^3-B).$$
Damit hängt der nächste Kaprekar-Schritt nur von
$$u=x_4-x_0,\qquad v=x_3-x_1,$$
ab, also von \(0 \le v \le u \le B-1\). Definiere
$$R_B(u,v)=u(B^4-1)+vB(B^2-1).$$
Der Nachfolgerzustand \(T_B(u,v)\) entsteht, indem man \(R_B(u,v)\) in Basis \(B\) schreibt, die fünf Ziffern sortiert und die beiden Abstände erneut bildet. Aus \(B^5\) Startwerten wird so ein Zustandsraum der Größe \(O(B^2)\).
Da \(B=6k+3\), ist die Basis durch \(3\) teilbar. Schreibe
$$B=3m,$$
wobei \(m\) ungerade ist. Der nichttriviale Fixzustand ist
$$u=2m,\qquad v=m.$$
Einsetzen liefert
$$R_B(2m,m)=2m(B^4-1)+m(B^3-B)=2mB^4+mB^3-mB-2m.$$
In Basis \(B\) ist das genau
$$R_B(2m,m)=(2m,\; m-1,\; B-1,\; 2m-1,\; m)_B.$$
Sortiert erhält man die Ziffernmenge
$$\{m-1,\; m,\; 2m-1,\; 2m,\; B-1\},$$
also wieder
$$u=(B-1)-(m-1)=2m,\qquad v=(2m)-m=m.$$
Folglich gilt
$$T_B(2m,m)=(2m,m).$$
Für \(B=15\) ist damit
$$C_{15}=(10,4,14,9,5)_{15},$$
und für \(B=21\)
$$C_{21}=(14,6,20,13,7)_{21}.$$
Sei \(M_B(u,v)\) die Anzahl der 5-stelligen Basis-\(B\)-Zahlen, deren sortierte Ziffern die Abstände \((u,v)\) besitzen. Für festes \(u \gt 0\) sei \(a\) die kleinste und \(e=a+u\) die größte Ziffer. Dann gibt es genau
$$B-u$$
Möglichkeiten für \(a\). Der Rest ist reine Multimengen- und Permutationszählung. Die Konstanten \(20,30,60,120\) stammen aus Multinomialkoeffizienten wie \(5!/3!\), \(5!/(2!2!)\), \(5!/2!\) und \(5!\).
Fall \(v=0\). Dann ist die Form
$$[a,c,c,c,e].$$
Für \(c=a\) oder \(c=e\) gibt es jeweils \(5\) Permutationen. Für \(a \lt c \lt e\) existieren \(u-1\) Werte von \(c\) und jeweils \(20\) Permutationen. Also
$$M_B(u,0)=(B-u)\bigl(5+5+20(u-1)\bigr),\qquad u \ge 1.$$
Fall \(u=v\). Dann hat die Multimenge die Form
$$[a,a,c,e,e].$$
Für \(c=a\) oder \(c=e\) gibt es jeweils \(10\) Permutationen. Für \(a \lt c \lt e\) gibt es \(u-1\) Möglichkeiten und jeweils \(30\) Permutationen. Daher
$$M_B(u,u)=(B-u)\bigl(10+10+30(u-1)\bigr),\qquad u \ge 1.$$
Fall \(0 \lt v \lt u\). Zunächst gibt es Randfälle, in denen eine innere Ziffer mit einem Endpunkt zusammenfällt:
$$[a,a,c,d,e],\quad [a,a,d,d,e],\quad [a,a,a,d,e],$$
und symmetrisch
$$[a,b,c,e,e],\quad [a,b,b,e,e],\quad [a,b,e,e,e].$$
Diese liefern zusammen
$$2\bigl(60(v-1)+30+20\bigr).$$
Wenn beide inneren Abstände echt sind, wählt man \(b\) mit \(a \lt b \lt e-v\), also \(u-v-1\) Möglichkeiten, und setzt \(d=b+v\). Dann bleiben die Typen
$$[a,b,b,d,e],\qquad [a,b,d,d,e],\qquad [a,b,c,d,e],$$
wobei im letzten Fall \(b \lt c \lt d\) gilt und deshalb \(v-1\) Möglichkeiten für \(c\) vorhanden sind. Das ergibt
$$60(u-v-1)+60(u-v-1)+120(u-v-1)(v-1).$$
Insgesamt also
$$M_B(u,v)=(B-u)\Bigl(100+120(v-1)+120(u-v-1)+120(u-v-1)(v-1)\Bigr),$$
für \(0 \lt v \lt u\).
Jeder Zustand \((u,v)\) besitzt genau einen Nachfolger \(T_B(u,v)\). Die Zustände bilden also einen funktionalen Graphen. Sei \(D_B(u,v)\) die Anzahl der zusätzlichen Kaprekar-Schritte, nachdem die erste Subtraktion bereits in den Zustand \((u,v)\) geführt hat. Dann gilt
$$D_B(u,v)= \begin{cases} 0,& T_B(u,v)=(u,v),\\ 1 + D_B\!\bigl(T_B(u,v)\bigr),& T_B(u,v)\ne(u,v). \end{cases}$$
Mit Memoisierung wird jede Tiefe nur einmal berechnet.
Unter den \(B^5-1\) positiven 5-Ziffern-Strings haben genau \(B-1\) überall dieselbe Ziffer, und die Kaprekar-Konstante selbst trägt ebenfalls \(0\) bei. Jeder andere Startwert liefert mindestens einen ersten Schritt. Dieser universelle Beitrag ist
$$B^5-1-(B-1)-1=B^5-B-1.$$
Danach zählt nur noch der Zustandsabstand, also
$$\boxed{S(B)=B^5-B-1+\sum_{u=1}^{B-1}\sum_{v=0}^{u} M_B(u,v)\,D_B(u,v).}$$
Genau diese Formel reproduziert die Prüfwerte
$$S(15)=5274369,\qquad S(111)=400668930299.$$
Die C++-, Python- und Java-Implementierungen benutzen dieselbe Reduktion auf den zweidimensionalen Abstandszustand. Für jede Basis \(B\) durchlaufen sie die dreieckige Zustandsmenge \((u,v)\), berechnen den eindeutigen Nachfolger über \(R_B(u,v)\), speichern die Tiefe zum Fixzustand per Memoisierung, multiplizieren diese Tiefe mit der passenden Multiplizität \(M_B(u,v)\) und addieren am Ende den universellen Offset \(B^5-B-1\). Da nur die letzten \(18\) Stellen benötigt werden, wird modulo \(10^{18}\) gerechnet.
Für eine feste Basis \(B\) gibt es \(O(B^2)\) Zustände. Ein Übergang besteht nur aus konstant vielen arithmetischen Operationen und einer Sortierung von fünf Ziffern, also ebenfalls konstanter Arbeit. Durch Memoisierung wird jede Tiefe höchstens einmal bestimmt. Daher benötigt die Methode pro Basis \(O(B^2)\) Zeit und \(O(B^2)\) Speicher statt einer Brute-Force-Suche über \(B^5\) Startwerte.
Her \(B=6k+3\) tabanı için (\(2 \le k \le 300\)), \(0 \lt i \lt B^5\) aralığındaki her tam sayı önde sıfırlar izinli olacak şekilde 5 basamaklı base-\(B\) yazıma çevrilir; basamaklar azalan ve artan sırada düzenlenip çıkarılır; sonra işlem tekrarlanır. Bu tabanlarda 5 basamaklı rutin için sıfırdan farklı tek bir Kaprekar sabiti \(C_B\) vardır.
\(i=C_B\) ise veya \(i\)'nin beş basamağı da eşitse \(s_B(i)=0\) tanımlanır; aksi halde \(s_B(i)\), \(C_B\)'ye ulaşmak için gereken iterasyon sayısıdır. Dolayısıyla
$$S(B)=\sum_{0 \lt i \lt B^5} s_B(i),$$
ve aranan değer
$$\sum_{k=2}^{300} S(6k+3)$$
toplamının son \(18\) basamağıdır.
Sıralanmış basamaklar
$$x_0 \le x_1 \le x_2 \le x_3 \le x_4$$
olsun. Azalan ve artan sayılar
$$N_{\downarrow}=x_4 B^4 + x_3 B^3 + x_2 B^2 + x_1 B + x_0,$$
$$N_{\uparrow}=x_0 B^4 + x_1 B^3 + x_2 B^2 + x_3 B + x_4$$
olur. Farkları
$$N_{\downarrow}-N_{\uparrow}=(x_4-x_0)(B^4-1)+(x_3-x_1)(B^3-B)$$
şeklindedir. Yani bir sonraki Kaprekar adımı sadece iki dış farka bağlıdır:
$$u=x_4-x_0,\qquad v=x_3-x_1,$$
burada \(0 \le v \le u \le B-1\). Şunu tanımlayalım:
$$R_B(u,v)=u(B^4-1)+vB(B^2-1).$$
Bir sonraki durum \(T_B(u,v)\), \(R_B(u,v)\)'yi base-\(B\) basamaklarına ayırıp bu beş basamağı sıralayarak ve iki farkı yeniden hesaplayarak bulunur. Böylece \(B^5\) aday yerine yalnızca \(O(B^2)\) durum incelenir.
\(B=6k+3\) olduğundan taban \(3\)'e bölünür. Şöyle yazalım:
$$B=3m,$$
burada \(m\) tektir. Sıfır dışı sabit durum
$$u=2m,\qquad v=m$$
olur. Yerine koyarsak
$$R_B(2m,m)=2m(B^4-1)+m(B^3-B)=2mB^4+mB^3-mB-2m.$$
Bunun base-\(B\) gösterimi tam olarak
$$R_B(2m,m)=(2m,\; m-1,\; B-1,\; 2m-1,\; m)_B$$
şeklindedir. Sıralanmış basamak çokluğu
$$\{m-1,\; m,\; 2m-1,\; 2m,\; B-1\}$$
olduğundan yine
$$u=(B-1)-(m-1)=2m,\qquad v=(2m)-m=m$$
elde edilir; yani
$$T_B(2m,m)=(2m,m).$$
Örneğin \(B=15\) için
$$C_{15}=(10,4,14,9,5)_{15},$$
\(B=21\) içinse
$$C_{21}=(14,6,20,13,7)_{21}.$$
\(M_B(u,v)\), sıralandığında fark çifti \((u,v)\) veren 5 basamaklı base-\(B\) dizilerinin sayısı olsun. \(u \gt 0\) sabitken en küçük basamağa \(a\), en büyüğe \(e=a+u\) diyelim. O halde \(a\) için tam
$$B-u$$
seçenek vardır. Geriye kalan sayı, orta basamakların eşitlik örüntüsünü saymaktır. Aşağıdaki \(20,30,60,120\) katsayıları \(5!/3!\), \(5!/(2!2!)\), \(5!/2!\) ve \(5!\) gibi multinom katsayılarından gelir.
Durum \(v=0\). Biçim
$$[a,c,c,c,e]$$
olur. \(c=a\) veya \(c=e\) için ayrı ayrı \(5\) permütasyon vardır. \(a \lt c \lt e\) için \(u-1\) farklı \(c\) seçimi ve her biri için \(20\) permütasyon bulunur. Demek ki
$$M_B(u,0)=(B-u)\bigl(5+5+20(u-1)\bigr),\qquad u \ge 1.$$
Durum \(u=v\). Bu kez çokluk
$$[a,a,c,e,e]$$
şeklindedir. \(c=a\) veya \(c=e\) için \(10\) permütasyon vardır. \(a \lt c \lt e\) olduğunda \(u-1\) seçim ve her biri için \(30\) permütasyon gelir. Böylece
$$M_B(u,u)=(B-u)\bigl(10+10+30(u-1)\bigr),\qquad u \ge 1.$$
Durum \(0 \lt v \lt u\). Önce iç basamaklardan birinin uçlara yapıştığı sınır aileleri vardır:
$$[a,a,c,d,e],\quad [a,a,d,d,e],\quad [a,a,a,d,e],$$
ve simetrik olarak
$$[a,b,c,e,e],\quad [a,b,b,e,e],\quad [a,b,e,e,e].$$
Bunların toplam katkısı
$$2\bigl(60(v-1)+30+20\bigr)$$
olur. Her iki iç aralık da sıkıysa, \(a \lt b \lt e-v\) olacak şekilde \(b\) seçilir; bunun \(u-v-1\) olasılığı vardır ve \(d=b+v\) olur. Geriye
$$[a,b,b,d,e],\qquad [a,b,d,d,e],\qquad [a,b,c,d,e]$$
tipleri kalır. Son tipte \(b \lt c \lt d\) olduğundan \(c\) için \(v-1\) seçim vardır. Toplam katkı
$$60(u-v-1)+60(u-v-1)+120(u-v-1)(v-1)$$
eder. Dolayısıyla
$$M_B(u,v)=(B-u)\Bigl(100+120(v-1)+120(u-v-1)+120(u-v-1)(v-1)\Bigr),$$
\(0 \lt v \lt u\) için geçerlidir.
Her \((u,v)\) durumunun tam bir ardılı vardır: \(T_B(u,v)\). Bu yüzden durumlar bir fonksiyonel graf oluşturur. İlk çıkarma yapıldıktan sonra \((u,v)\) durumundan başlayarak gereken ek Kaprekar adım sayısına \(D_B(u,v)\) diyelim. O zaman
$$D_B(u,v)= \begin{cases} 0,& T_B(u,v)=(u,v),\\ 1 + D_B\!\bigl(T_B(u,v)\bigr),& T_B(u,v)\ne(u,v). \end{cases}$$
Uygulama bu bağıntıyı bellekleyerek her derinliği yalnızca bir kez hesaplar.
\(B^5-1\) pozitif 5 basamaklı dizinin tam \(B-1\) tanesinin tüm basamakları eşittir; ayrıca Kaprekar sabitinin kendisi de \(0\) katkı verir. Geriye kalan her sayı için ilk adım kaçınılmazdır. Bu evrensel ilk-adım katkısı
$$B^5-1-(B-1)-1=B^5-B-1$$
olur. Bundan sonra sadece durum derinliği kaldığı için
$$\boxed{S(B)=B^5-B-1+\sum_{u=1}^{B-1}\sum_{v=0}^{u} M_B(u,v)\,D_B(u,v).}$$
Bu kapalı ifade, yayımlanmış kontrol değerlerini de verir:
$$S(15)=5274369,\qquad S(111)=400668930299.$$
C++, Python ve Java uygulamaları aynı matematiksel indirgemeyi kullanır. Her taban \(B\) için üçgensel durum kümesi \((u,v)\) dolaşılır, \(R_B(u,v)\) üzerinden tekil ardıl hesaplanır, sabit duruma kalan derinlik belleklenir, bu derinlik uygun çokluk \(M_B(u,v)\) ile çarpılır ve son olarak evrensel ofset \(B^5-B-1\) eklenir. Sadece son \(18\) basamak istendiğinden tüm toplamlar \(10^{18}\) modunda tutulur.
Sabit bir \(B\) için durum sayısı \(O(B^2)\)'dir. Her geçiş yalnızca sabit sayıda aritmetik işlem ve beş basamağın sıralanmasını içerir; bu da sabit maliyetlidir. Bellekleme sayesinde her durumun derinliği bir kez bulunur. Sonuç olarak yöntem taban başına \(O(B^2)\) zaman ve \(O(B^2)\) bellek kullanır; bu, \(B^5\) başlangıç değerini kaba kuvvetle denemekten çok daha küçüktür.
Para cada base \(B=6k+3\) con \(2 \le k \le 300\), tomamos todos los enteros \(i\) con \(0 \lt i \lt B^5\), los escribimos como cadenas de 5 dígitos en base \(B\) permitiendo ceros iniciales, ordenamos sus dígitos en orden decreciente y creciente, restamos y repetimos. En estas bases, la rutina de 5 dígitos tiene una única constante de Kaprekar no nula \(C_B\).
Se define \(s_B(i)=0\) cuando \(i=C_B\) o cuando los cinco dígitos de \(i\) son iguales; en caso contrario, \(s_B(i)\) es el número de iteraciones necesarias para llegar a \(C_B\). Entonces
$$S(B)=\sum_{0 \lt i \lt B^5} s_B(i),$$
y debemos hallar los últimos \(18\) dígitos de
$$\sum_{k=2}^{300} S(6k+3).$$
Sean los dígitos ordenados
$$x_0 \le x_1 \le x_2 \le x_3 \le x_4.$$
Los números decreciente y creciente son
$$N_{\downarrow}=x_4 B^4 + x_3 B^3 + x_2 B^2 + x_1 B + x_0,$$
$$N_{\uparrow}=x_0 B^4 + x_1 B^3 + x_2 B^2 + x_3 B + x_4.$$
La resta de Kaprekar vale
$$N_{\downarrow}-N_{\uparrow}=(x_4-x_0)(B^4-1)+(x_3-x_1)(B^3-B).$$
Por tanto, el siguiente valor solo depende de
$$u=x_4-x_0,\qquad v=x_3-x_1,$$
con \(0 \le v \le u \le B-1\). Definimos
$$R_B(u,v)=u(B^4-1)+vB(B^2-1).$$
El estado siguiente \(T_B(u,v)\) se obtiene escribiendo \(R_B(u,v)\) en base \(B\), ordenando sus cinco dígitos y recalculando las dos diferencias. Así, el problema pasa de \(B^5\) entradas a solo \(O(B^2)\) estados.
Como \(B=6k+3\), la base es múltiplo de \(3\). Escribimos
$$B=3m,$$
con \(m\) impar. El estado fijo no nulo es
$$u=2m,\qquad v=m.$$
Sustituyendo,
$$R_B(2m,m)=2m(B^4-1)+m(B^3-B)=2mB^4+mB^3-mB-2m.$$
Su representación en base \(B\) es exactamente
$$R_B(2m,m)=(2m,\; m-1,\; B-1,\; 2m-1,\; m)_B.$$
Los dígitos ordenados son
$$\{m-1,\; m,\; 2m-1,\; 2m,\; B-1\},$$
y vuelven a producir
$$u=(B-1)-(m-1)=2m,\qquad v=(2m)-m=m.$$
En consecuencia,
$$T_B(2m,m)=(2m,m).$$
Esto coincide con los ejemplos
$$C_{15}=(10,4,14,9,5)_{15},\qquad C_{21}=(14,6,20,13,7)_{21}.$$
Sea \(M_B(u,v)\) el número de cadenas de 5 dígitos en base \(B\) cuya versión ordenada tiene diferencias \((u,v)\). Fijado \(u \gt 0\), llamemos \(a\) al dígito mínimo y \(e=a+u\) al máximo. Entonces hay exactamente
$$B-u$$
opciones para \(a\). El resto es un conteo de multiconjuntos y permutaciones. Los números \(20,30,60,120\) son coeficientes multinomiales.
Caso \(v=0\). La forma es
$$[a,c,c,c,e].$$
Si \(c=a\) o \(c=e\), hay \(5\) permutaciones en cada caso. Si \(a \lt c \lt e\), hay \(u-1\) posibilidades para \(c\) y \(20\) permutaciones cada una. Por tanto,
$$M_B(u,0)=(B-u)\bigl(5+5+20(u-1)\bigr),\qquad u \ge 1.$$
Caso \(u=v\). Ahora el multiconjunto es
$$[a,a,c,e,e].$$
Si \(c=a\) o \(c=e\), aparecen \(10\) permutaciones en cada caso. Si \(a \lt c \lt e\), hay \(u-1\) elecciones y \(30\) permutaciones cada una. Así,
$$M_B(u,u)=(B-u)\bigl(10+10+30(u-1)\bigr),\qquad u \ge 1.$$
Caso \(0 \lt v \lt u\). Primero están las familias de borde, donde un dígito interior coincide con un extremo:
$$[a,a,c,d,e],\quad [a,a,d,d,e],\quad [a,a,a,d,e],$$
y simétricamente
$$[a,b,c,e,e],\quad [a,b,b,e,e],\quad [a,b,e,e,e].$$
Su contribución total es
$$2\bigl(60(v-1)+30+20\bigr).$$
Si ambas separaciones interiores son estrictas, elegimos \(b\) con \(a \lt b \lt e-v\), lo que da \(u-v-1\) posibilidades, y ponemos \(d=b+v\). Los tipos restantes son
$$[a,b,b,d,e],\qquad [a,b,d,d,e],\qquad [a,b,c,d,e],$$
donde en el último caso \(b \lt c \lt d\), así que hay \(v-1\) opciones para \(c\). La contribución total es
$$60(u-v-1)+60(u-v-1)+120(u-v-1)(v-1).$$
Por ello,
$$M_B(u,v)=(B-u)\Bigl(100+120(v-1)+120(u-v-1)+120(u-v-1)(v-1)\Bigr),$$
para \(0 \lt v \lt u\).
Cada estado \((u,v)\) tiene exactamente un sucesor, \(T_B(u,v)\). Por eso los estados forman un grafo funcional. Sea \(D_B(u,v)\) el número de pasos de Kaprekar adicionales necesarios una vez que la primera resta ya produjo el estado \((u,v)\). Entonces
$$D_B(u,v)= \begin{cases} 0,& T_B(u,v)=(u,v),\\ 1 + D_B\!\bigl(T_B(u,v)\bigr),& T_B(u,v)\ne(u,v). \end{cases}$$
La implementación memoriza esta recurrencia, así que cada profundidad se calcula una sola vez.
Entre las \(B^5-1\) cadenas positivas de 5 dígitos, exactamente \(B-1\) tienen todos los dígitos iguales, y la propia constante de Kaprekar también aporta \(0\). Toda entrada restante contribuye con un primer paso inevitable. Ese término universal es
$$B^5-1-(B-1)-1=B^5-B-1.$$
Después de ese primer paso, solo importa el estado comprimido, así que
$$\boxed{S(B)=B^5-B-1+\sum_{u=1}^{B-1}\sum_{v=0}^{u} M_B(u,v)\,D_B(u,v).}$$
Esta fórmula reproduce los puntos de control publicados
$$S(15)=5274369,\qquad S(111)=400668930299.$$
Las implementaciones en C++, Python y Java usan exactamente esta reducción matemática. Para cada base \(B\), recorren el conjunto triangular de estados \((u,v)\), calculan el sucesor determinista evaluando \(R_B(u,v)\) y ordenando sus cinco dígitos en base \(B\), memorizan la profundidad hasta el estado fijo, multiplican esa profundidad por la multiplicidad \(M_B(u,v)\) y añaden al final el desplazamiento universal \(B^5-B-1\). Todo se reduce módulo \(10^{18}\) porque solo interesan los últimos \(18\) dígitos.
Para una base fija \(B\), el número de estados es \(O(B^2)\). Cada transición realiza solo aritmética de costo constante y una ordenación de cinco dígitos, también constante. Gracias a la memoización, cada profundidad se evalúa una sola vez. Por tanto, el método cuesta \(O(B^2)\) tiempo y \(O(B^2)\) memoria por base, muy por debajo del barrido ingenuo de las \(B^5\) entradas.
对每个基数 \(B=6k+3\)（其中 \(2 \le k \le 300\)），考虑所有满足 \(0 \lt i \lt B^5\) 的整数，把它写成允许前导零的 5 位 base-\(B\) 数，按降序和升序排列数字后相减，再重复这一过程。对这些基数，5 位 Kaprekar 过程存在唯一的非零固定点 \(C_B\)。
定义 \(s_B(i)=0\)，当 \(i=C_B\) 或者 \(i\) 的五个数字全部相同时取该值；否则 \(s_B(i)\) 为到达 \(C_B\) 所需的迭代次数。于是
$$S(B)=\sum_{0 \lt i \lt B^5} s_B(i),$$
题目要求的是
$$\sum_{k=2}^{300} S(6k+3)$$
的末 \(18\) 位。
设排序后的数字为
$$x_0 \le x_1 \le x_2 \le x_3 \le x_4.$$
降序数与升序数分别是
$$N_{\downarrow}=x_4 B^4 + x_3 B^3 + x_2 B^2 + x_1 B + x_0,$$
$$N_{\uparrow}=x_0 B^4 + x_1 B^3 + x_2 B^2 + x_3 B + x_4.$$
因此一次 Kaprekar 相减可写成
$$N_{\downarrow}-N_{\uparrow}=(x_4-x_0)(B^4-1)+(x_3-x_1)(B^3-B).$$
也就是说，下一步只取决于两个外层差值
$$u=x_4-x_0,\qquad v=x_3-x_1,$$
其中 \(0 \le v \le u \le B-1\)。定义
$$R_B(u,v)=u(B^4-1)+vB(B^2-1).$$
将 \(R_B(u,v)\) 展开成 base-\(B\) 的 5 个数字，再排序并重新取这两个差值，就得到确定性的转移
$$T_B(u,v).$$
这样，原来的 \(B^5\) 个输入被压缩成仅有 \(O(B^2)\) 个状态。
因为 \(B=6k+3\)，所以 \(B\) 可被 \(3\) 整除。记
$$B=3m,$$
其中 \(m\) 为奇数。非零固定状态是
$$u=2m,\qquad v=m.$$
代入闭式可得
$$R_B(2m,m)=2m(B^4-1)+m(B^3-B)=2mB^4+mB^3-mB-2m.$$
它的 base-\(B\) 表示恰好是
$$R_B(2m,m)=(2m,\; m-1,\; B-1,\; 2m-1,\; m)_B.$$
排序后的数字多重集为
$$\{m-1,\; m,\; 2m-1,\; 2m,\; B-1\},$$
于是再次得到
$$u=(B-1)-(m-1)=2m,\qquad v=(2m)-m=m,$$
因此
$$T_B(2m,m)=(2m,m).$$
这正对应题目给出的例子
$$C_{15}=(10,4,14,9,5)_{15},\qquad C_{21}=(14,6,20,13,7)_{21}.$$
记 \(M_B(u,v)\) 为所有 5 位 base-\(B\) 数字串中，排序后差值为 \((u,v)\) 的个数。固定 \(u \gt 0\)，设最小数字为 \(a\)，最大数字为 \(e=a+u\)。那么 \(a\) 恰有
$$B-u$$
种选择。剩下的就是中间数字重复模式的计数。公式中的 \(20,30,60,120\) 都来自多项式系数。
情形 \(v=0\)。 此时多重集形如
$$[a,c,c,c,e].$$
若 \(c=a\) 或 \(c=e\)，各有 \(5\) 个排列；若 \(a \lt c \lt e\)，则 \(c\) 有 \(u-1\) 种取值，每种有 \(20\) 个排列。因此
$$M_B(u,0)=(B-u)\bigl(5+5+20(u-1)\bigr),\qquad u \ge 1.$$
情形 \(u=v\)。 此时多重集为
$$[a,a,c,e,e].$$
若 \(c=a\) 或 \(c=e\)，各有 \(10\) 个排列；若 \(a \lt c \lt e\)，则有 \(u-1\) 种选择，每种对应 \(30\) 个排列。所以
$$M_B(u,u)=(B-u)\bigl(10+10+30(u-1)\bigr),\qquad u \ge 1.$$
情形 \(0 \lt v \lt u\)。 先看边界家族，也就是某个内层数字与端点重合的情况：
$$[a,a,c,d,e],\quad [a,a,d,d,e],\quad [a,a,a,d,e],$$
以及对称的
$$[a,b,c,e,e],\quad [a,b,b,e,e],\quad [a,b,e,e,e].$$
它们总共贡献
$$2\bigl(60(v-1)+30+20\bigr).$$
若两个内层间隔都是真正的间隔，则选 \(b\) 满足 \(a \lt b \lt e-v\)，共有 \(u-v-1\) 种，再令 \(d=b+v\)。剩余模式为
$$[a,b,b,d,e],\qquad [a,b,d,d,e],\qquad [a,b,c,d,e],$$
其中最后一种还要求 \(b \lt c \lt d\)，所以 \(c\) 有 \(v-1\) 种选择。总贡献为
$$60(u-v-1)+60(u-v-1)+120(u-v-1)(v-1).$$
于是
$$M_B(u,v)=(B-u)\Bigl(100+120(v-1)+120(u-v-1)+120(u-v-1)(v-1)\Bigr),$$
对所有 \(0 \lt v \lt u\) 成立。
每个状态 \((u,v)\) 只有一个后继 \(T_B(u,v)\)，因此所有状态构成一个函数图。记 \(D_B(u,v)\) 为第一次相减已经得到状态 \((u,v)\) 之后，还需要的额外 Kaprekar 步数。那么
$$D_B(u,v)= \begin{cases} 0,& T_B(u,v)=(u,v),\\ 1 + D_B\!\bigl(T_B(u,v)\bigr),& T_B(u,v)\ne(u,v). \end{cases}$$
实现用记忆化处理该递推，所以每个状态深度只求一次。
在 \(B^5-1\) 个正的 5 位数字串里，恰有 \(B-1\) 个是“所有数字都相同”的情况，而 Kaprekar 常数本身也贡献 \(0\)。其他每个起点都必然先走一步，因此统一的首步贡献为
$$B^5-1-(B-1)-1=B^5-B-1.$$
首步之后，只剩压缩状态的深度，所以
$$\boxed{S(B)=B^5-B-1+\sum_{u=1}^{B-1}\sum_{v=0}^{u} M_B(u,v)\,D_B(u,v).}$$
这正好复现公开的校验值
$$S(15)=5274369,\qquad S(111)=400668930299.$$
C++、Python 和 Java 实现都遵循同一套数学化简。对每个基数 \(B\)，程序遍历三角形状态集合 \((u,v)\)，通过计算 \(R_B(u,v)\) 并排序其五个 base-\(B\) 数字来得到确定性后继，记忆化固定点深度，把该深度乘以对应的重数 \(M_B(u,v)\)，最后再加上统一偏移量 \(B^5-B-1\)。由于最终只需要末 \(18\) 位，整个求和过程都在模 \(10^{18}\) 下进行。
对固定基数 \(B\)，状态数为 \(O(B^2)\)。每次转移只包含常数次整数运算和 5 个数字的排序，因此仍是常数成本。借助记忆化，每个状态深度仅计算一次，所以每个基数的总时间复杂度为 \(O(B^2)\)，空间复杂度也为 \(O(B^2)\)。这比直接枚举 \(B^5\) 个起点小得多。
Для каждого основания \(B=6k+3\), где \(2 \le k \le 300\), рассматриваются все числа \(i\) с \(0 \lt i \lt B^5\). Каждое число записывается как 5-значная запись в системе счисления по основанию \(B\) с ведущими нулями, цифры сортируются по убыванию и возрастанию, затем выполняется вычитание, и процесс повторяется. Для этих оснований у 5-значной процедуры существует единственная ненулевая константа Капрекара \(C_B\).
Положим \(s_B(i)=0\), если \(i=C_B\) или все пять цифр у \(i\) одинаковы; в противном случае \(s_B(i)\) равно числу итераций до достижения \(C_B\). Тогда
$$S(B)=\sum_{0 \lt i \lt B^5} s_B(i),$$
и требуется найти последние \(18\) цифр числа
$$\sum_{k=2}^{300} S(6k+3).$$
Пусть отсортированные цифры равны
$$x_0 \le x_1 \le x_2 \le x_3 \le x_4.$$
Тогда убывающая и возрастающая записи имеют вид
$$N_{\downarrow}=x_4 B^4 + x_3 B^3 + x_2 B^2 + x_1 B + x_0,$$
$$N_{\uparrow}=x_0 B^4 + x_1 B^3 + x_2 B^2 + x_3 B + x_4.$$
Их разность равна
$$N_{\downarrow}-N_{\uparrow}=(x_4-x_0)(B^4-1)+(x_3-x_1)(B^3-B).$$
Следовательно, следующий шаг определяется только двумя внешними разностями
$$u=x_4-x_0,\qquad v=x_3-x_1,$$
где \(0 \le v \le u \le B-1\). Введём
$$R_B(u,v)=u(B^4-1)+vB(B^2-1).$$
Чтобы получить переход \(T_B(u,v)\), достаточно представить \(R_B(u,v)\) в базе \(B\), отсортировать его пять цифр и заново вычислить те же две разности. Так пространство из \(B^5\) входов сжимается до \(O(B^2)\) состояний.
Так как \(B=6k+3\), основание делится на \(3\). Запишем
$$B=3m,$$
где \(m\) нечётно. Нетривиальное фиксированное состояние имеет вид
$$u=2m,\qquad v=m.$$
Подстановка даёт
$$R_B(2m,m)=2m(B^4-1)+m(B^3-B)=2mB^4+mB^3-mB-2m.$$
Его запись в базе \(B\) равна
$$R_B(2m,m)=(2m,\; m-1,\; B-1,\; 2m-1,\; m)_B.$$
После сортировки получается мультимножество цифр
$$\{m-1,\; m,\; 2m-1,\; 2m,\; B-1\},$$
а значит снова
$$u=(B-1)-(m-1)=2m,\qquad v=(2m)-m=m.$$
Поэтому
$$T_B(2m,m)=(2m,m).$$
Это и есть состояние константы Капрекара; примеры из условия:
$$C_{15}=(10,4,14,9,5)_{15},\qquad C_{21}=(14,6,20,13,7)_{21}.$$
Обозначим через \(M_B(u,v)\) число 5-значных строк в базе \(B\), у которых после сортировки разности равны \((u,v)\). Для фиксированного \(u \gt 0\) пусть \(a\) — минимальная цифра, а \(e=a+u\) — максимальная. Тогда для \(a\) есть ровно
$$B-u$$
вариантов. Остальное — чистая комбинаторика мультимножеств и перестановок. Коэффициенты \(20,30,60,120\) возникают из мультиномиальных подсчётов.
Случай \(v=0\). Тогда мультимножество имеет вид
$$[a,c,c,c,e].$$
Если \(c=a\) или \(c=e\), получаем по \(5\) перестановок. Если \(a \lt c \lt e\), то для \(c\) есть \(u-1\) вариантов и по \(20\) перестановок на каждый. Следовательно,
$$M_B(u,0)=(B-u)\bigl(5+5+20(u-1)\bigr),\qquad u \ge 1.$$
Случай \(u=v\). Теперь форма такова:
$$[a,a,c,e,e].$$
При \(c=a\) или \(c=e\) имеем по \(10\) перестановок. Если \(a \lt c \lt e\), то вариантов \(u-1\), и каждый даёт \(30\) перестановок. Значит,
$$M_B(u,u)=(B-u)\bigl(10+10+30(u-1)\bigr),\qquad u \ge 1.$$
Случай \(0 \lt v \lt u\). Сначала идут граничные семейства, где одна внутренняя цифра совпадает с концом интервала:
$$[a,a,c,d,e],\quad [a,a,d,d,e],\quad [a,a,a,d,e],$$
и симметрично
$$[a,b,c,e,e],\quad [a,b,b,e,e],\quad [a,b,e,e,e].$$
Их общий вклад равен
$$2\bigl(60(v-1)+30+20\bigr).$$
Если оба внутренних промежутка строгие, выбирается \(b\) так, что \(a \lt b \lt e-v\), то есть есть \(u-v-1\) возможностей, а затем кладётся \(d=b+v\). Остаются типы
$$[a,b,b,d,e],\qquad [a,b,d,d,e],\qquad [a,b,c,d,e],$$
где в последнем случае требуется \(b \lt c \lt d\), так что для \(c\) существует \(v-1\) вариант. Их суммарный вклад равен
$$60(u-v-1)+60(u-v-1)+120(u-v-1)(v-1).$$
Итак,
$$M_B(u,v)=(B-u)\Bigl(100+120(v-1)+120(u-v-1)+120(u-v-1)(v-1)\Bigr),$$
для всех \(0 \lt v \lt u\).
У каждого состояния \((u,v)\) есть ровно один исходящий переход, а именно \(T_B(u,v)\). Значит, состояния образуют функциональный граф. Пусть \(D_B(u,v)\) — число дополнительных шагов Капрекара после того, как первое вычитание уже привело к состоянию \((u,v)\). Тогда
$$D_B(u,v)= \begin{cases} 0,& T_B(u,v)=(u,v),\\ 1 + D_B\!\bigl(T_B(u,v)\bigr),& T_B(u,v)\ne(u,v). \end{cases}$$
Благодаря мемоизации каждая глубина вычисляется только один раз.
Среди \(B^5-1\) положительных 5-значных строк ровно \(B-1\) состоят из одинаковых цифр, а сама константа Капрекара тоже даёт вклад \(0\). Все остальные входы обязательно делают хотя бы один первый шаг. Этот универсальный вклад равен
$$B^5-1-(B-1)-1=B^5-B-1.$$
После первого шага всё определяется только сжатым состоянием, поэтому
$$\boxed{S(B)=B^5-B-1+\sum_{u=1}^{B-1}\sum_{v=0}^{u} M_B(u,v)\,D_B(u,v).}$$
Эта формула даёт опубликованные контрольные значения
$$S(15)=5274369,\qquad S(111)=400668930299.$$
Реализации на C++, Python и Java используют один и тот же математический переход к двум разностям. Для каждого основания \(B\) они перебирают треугольное множество состояний \((u,v)\), вычисляют детерминированного потомка через \(R_B(u,v)\) и сортировку пяти цифр, мемоизируют глубину до фиксированного состояния, умножают её на соответствующую кратность \(M_B(u,v)\) и в конце добавляют универсальный слагаемый \(B^5-B-1\). Все вычисления ведутся по модулю \(10^{18}\), поскольку нужны только последние \(18\) цифр.
Для фиксированного основания \(B\) число состояний равно \(O(B^2)\). Один переход требует лишь константного числа арифметических операций и сортировки пяти цифр, то есть тоже константной работы. Мемoизация гарантирует, что глубина каждого состояния вычисляется один раз. Следовательно, на одну базу алгоритм использует \(O(B^2)\) времени и \(O(B^2)\) памяти, что несравнимо меньше полного перебора всех \(B^5\) стартов.
لكل أساس \(B=6k+3\) حيث \(2 \le k \le 300\)، نأخذ كل عدد صحيح \(i\) يحقق \(0 \lt i \lt B^5\)، ونكتبه على هيئة عدد من 5 خانات في الأساس \(B\) مع السماح بالأصفار البادئة، ثم نرتب الخانات ترتيبًا تنازليًا وترتيبًا تصاعديًا ونطرح، ونكرر العملية. في هذه الأسس توجد قيمة كابريكار ثابتة غير صفرية وحيدة نرمز لها بـ \(C_B\).
نعرّف \(s_B(i)=0\) إذا كان \(i=C_B\) أو إذا كانت الخانات الخمس كلها متساوية، وإلا فـ \(s_B(i)\) هو عدد التكرارات اللازمة للوصول إلى \(C_B\). وعندئذ
$$S(B)=\sum_{0 \lt i \lt B^5} s_B(i),$$
والمطلوب هو آخر \(18\) رقمًا من
$$\sum_{k=2}^{300} S(6k+3).$$
لتكن الخانات بعد الفرز
$$x_0 \le x_1 \le x_2 \le x_3 \le x_4.$$
فالعددان الناتجان من الترتيب التنازلي والتصاعدي هما
$$N_{\downarrow}=x_4 B^4 + x_3 B^3 + x_2 B^2 + x_1 B + x_0,$$
$$N_{\uparrow}=x_0 B^4 + x_1 B^3 + x_2 B^2 + x_3 B + x_4.$$
إذن فرق كابريكار يساوي
$$N_{\downarrow}-N_{\uparrow}=(x_4-x_0)(B^4-1)+(x_3-x_1)(B^3-B).$$
وبالتالي فإن الخطوة التالية تعتمد فقط على الفارقين الخارجيين
$$u=x_4-x_0,\qquad v=x_3-x_1,$$
حيث \(0 \le v \le u \le B-1\). نعرّف
$$R_B(u,v)=u(B^4-1)+vB(B^2-1).$$
ومن خلال كتابة \(R_B(u,v)\) في الأساس \(B\)، ثم فرز خاناته الخمس وإعادة حساب الفارقين، نحصل على الانتقال الحتمي
$$T_B(u,v).$$
وهكذا ينخفض فضاء البحث من \(B^5\) مدخلات إلى \(O(B^2)\) حالات فقط.
بما أن \(B=6k+3\)، فإن الأساس يقبل القسمة على \(3\). نكتب
$$B=3m,$$
حيث \(m\) فردي. الحالة الثابتة غير الصفرية هي
$$u=2m,\qquad v=m.$$
وبالتعويض نحصل على
$$R_B(2m,m)=2m(B^4-1)+m(B^3-B)=2mB^4+mB^3-mB-2m.$$
وتمثيل هذا العدد في الأساس \(B\) هو
$$R_B(2m,m)=(2m,\; m-1,\; B-1,\; 2m-1,\; m)_B.$$
وعند الفرز تصبح مجموعة الخانات
$$\{m-1,\; m,\; 2m-1,\; 2m,\; B-1\},$$
فتعود الفروق إلى
$$u=(B-1)-(m-1)=2m,\qquad v=(2m)-m=m.$$
إذًا
$$T_B(2m,m)=(2m,m).$$
وهذا يطابق المثالين
$$C_{15}=(10,4,14,9,5)_{15},\qquad C_{21}=(14,6,20,13,7)_{21}.$$
لنرمز بـ \(M_B(u,v)\) إلى عدد السلاسل ذات الخانات الخمس في الأساس \(B\) التي تعطي بعد الفرز الفارقين \((u,v)\). مع تثبيت \(u \gt 0\)، وليكن \(a\) أصغر خانة و\(e=a+u\) أكبر خانة. عندئذ يوجد بالضبط
$$B-u$$
اختيارًا ممكنًا لـ \(a\). وما يبقى هو عدّ أنماط تكرار الخانات الوسطى. الأعداد \(20,30,60,120\) في الصيغ الآتية هي معاملات متعددة الحدود.
الحالة \(v=0\). يكون الشكل
$$[a,c,c,c,e].$$
إذا كان \(c=a\) أو \(c=e\) فهناك \(5\) تبديلات في كل حالة. وإذا كان \(a \lt c \lt e\)، فهناك \(u-1\) اختيارات لـ \(c\)، ولكل اختيار \(20\) تبديلًا. لذلك
$$M_B(u,0)=(B-u)\bigl(5+5+20(u-1)\bigr),\qquad u \ge 1.$$
الحالة \(u=v\). يصبح النمط
$$[a,a,c,e,e].$$
إذا كان \(c=a\) أو \(c=e\) فهناك \(10\) تبديلات في كل حالة. وإذا كان \(a \lt c \lt e\)، فهناك \(u-1\) اختيارات ولكل منها \(30\) تبديلًا. ومن ثم
$$M_B(u,u)=(B-u)\bigl(10+10+30(u-1)\bigr),\qquad u \ge 1.$$
الحالة \(0 \lt v \lt u\). أولًا توجد عائلات حدّية يلتصق فيها أحد الأرقام الداخلية بالطرف:
$$[a,a,c,d,e],\quad [a,a,d,d,e],\quad [a,a,a,d,e],$$
وبشكل متناظر
$$[a,b,c,e,e],\quad [a,b,b,e,e],\quad [a,b,e,e,e].$$
ومجموع مساهمتها هو
$$2\bigl(60(v-1)+30+20\bigr).$$
أما إذا كان الفاصلان الداخليان حقيقيين، فنختار \(b\) بحيث \(a \lt b \lt e-v\)، وعدد هذه الاختيارات هو \(u-v-1\)، ثم نضع \(d=b+v\). وتبقى الأنماط
$$[a,b,b,d,e],\qquad [a,b,d,d,e],\qquad [a,b,c,d,e],$$
وفي النمط الأخير يكون \(b \lt c \lt d\)، لذا يوجد \(v-1\) اختيارًا ممكنًا لـ \(c\). وعليه فالمساهمة الكلية هي
$$60(u-v-1)+60(u-v-1)+120(u-v-1)(v-1).$$
إذن
$$M_B(u,v)=(B-u)\Bigl(100+120(v-1)+120(u-v-1)+120(u-v-1)(v-1)\Bigr),$$
لكل \(0 \lt v \lt u\).
كل حالة \((u,v)\) لها تابع وحيد هو \(T_B(u,v)\)، لذلك تشكل الحالات رسمًا داليًا. ولتكن \(D_B(u,v)\) عدد خطوات كابريكار الإضافية المطلوبة بعد أن تكون أول عملية طرح قد أوصلت بالفعل إلى الحالة \((u,v)\). عندها
$$D_B(u,v)= \begin{cases} 0,& T_B(u,v)=(u,v),\\ 1 + D_B\!\bigl(T_B(u,v)\bigr),& T_B(u,v)\ne(u,v). \end{cases}$$
وتستخدم التطبيقات الحفظ بالذاكرة، لذا لا يُحسب عمق أي حالة أكثر من مرة.
من بين \(B^5-1\) السلاسل الإيجابية ذات 5 خانات، يوجد بالضبط \(B-1\) سلاسل كل خاناتها متساوية، كما أن ثابت كابريكار نفسه يساهم بصفر. وكل مدخل آخر يضيف خطوة أولى لا مفر منها. لذلك تكون المساهمة العامة للخطوة الأولى
$$B^5-1-(B-1)-1=B^5-B-1.$$
وبعد هذه الخطوة الأولى يصبح كل شيء معتمدًا فقط على الحالة المضغوطة، ومن ثم
$$\boxed{S(B)=B^5-B-1+\sum_{u=1}^{B-1}\sum_{v=0}^{u} M_B(u,v)\,D_B(u,v).}$$
وهذه الصيغة تعطي أيضًا قيم التحقق المنشورة
$$S(15)=5274369,\qquad S(111)=400668930299.$$
تعتمد تطبيقات C++ وPython وJava على الاختزال الرياضي نفسه. فلكل أساس \(B\)، تُعدِّد الشيفرة المجموعة المثلثية من الحالات \((u,v)\)، وتحسب التابع الحتمي عبر تقييم \(R_B(u,v)\) وفرز خاناته الخمس في الأساس \(B\)، ثم تحفظ عمق الوصول إلى الحالة الثابتة، وتضرب هذا العمق في المضاعفية الموافقة \(M_B(u,v)\)، وأخيرًا تضيف الإزاحة العامة \(B^5-B-1\). وتُجرى الحسابات كلها بترديد \(10^{18}\) لأن المطلوب هو آخر \(18\) رقمًا فقط.
لأساس ثابت \(B\)، يكون عدد الحالات \(O(B^2)\). وكل انتقال يحتاج إلى عدد ثابت من العمليات الحسابية وإلى فرز خمس خانات فقط، أي كلفة ثابتة أيضًا. ومع الحفظ بالذاكرة يُحسب عمق كل حالة مرة واحدة، لذلك تكون الكلفة الكلية لكل أساس \(O(B^2)\) زمنًا و\(O(B^2)\) ذاكرة، وهي أصغر كثيرًا من الفحص المباشر لكل \(B^5\) قيمة ابتدائية.