Let \(\mathcal A\) be the set of positive integers whose decimal expansion never contains a block \(ddd\) of three equal consecutive digits. The required value is the convergent Kempner-like series
$$S=\sum_{n\in\mathcal A}\frac{1}{n}.$$
The local C++, Python, and Java programs all implement the same method and print \(S \approx 253.6135092068\). The real task is therefore not brute force, but how to sum the infinite tail of admissible numbers in a controlled way.
The forbidden pattern can be counted with the same state machine used by the code. Let \(a_k\) be the number of length-\(k\) digit strings with no three equal consecutive digits, allowing leading zeroes for counting purposes. Split them into strings ending with run length \(1\) and run length \(2\), say \(u_k\) and \(v_k\). Appending a different digit gives \(u_{k+1}=9(u_k+v_k)\), while appending the same digit is possible only from run length \(1\), so \(v_{k+1}=u_k\). Hence
$$a_{k+1}=9a_k+9a_{k-1}.$$
The dominant root of \(x^2-9x-9=0\) is
$$\rho=\frac{9+\sqrt{117}}{2}\lt 10.$$
Therefore the number of admissible \(k\)-digit denominators is \(O(\rho^k)\), so the total contribution of all \(k\)-digit terms is \(O((\rho/10)^k)\). Since \(\rho/10\lt 1\), the series converges exponentially fast by digit length.
To decide whether another digit may be appended, only two pieces of information matter: the last digit \(d\in\{0,\dots,9\}\) and whether the current run length is \(1\) or \(2\). This gives \(20\) states \(s=(d,r)\).
From \((d,1)\), every next digit is legal. If we append \(d\), the next state is \((d,2)\); if we append \(x\ne d\), the next state is \((x,1)\). From \((d,2)\), the digit \(d\) is forbidden, while each \(x\ne d\) leads to \((x,1)\). This is exactly what build_automaton constructs in all three language versions.
Fix a state \(s\), and let \(W_s\) be the set of all finite valid tails that may follow \(s\), including the empty tail \(\epsilon\). For \(m\ge 0\), define
$$H_s^{(m)}=\sum_{w\in W_s}\frac{\operatorname{val}(w)^m}{10^{(m+1)|w|}},$$
with the convention that the empty tail contributes \(1\) when \(m=0\) and \(0\) otherwise. If a non-empty tail is written as \(w=xu\), where the first appended digit is \(x\) and the remaining tail \(u\) starts from the next state \(t\), then
$$\operatorname{val}(xu)=x\cdot 10^{|u|}+\operatorname{val}(u).$$
Applying the binomial theorem gives the recurrence
$$H_s^{(m)}=\delta_{m,0}+\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}\sum_{j=0}^{m}\binom{m}{j}x^{m-j}H_t^{(j)},$$
where \(T(s)\) is the set of labeled outgoing transitions from state \(s\). The term \(j=m\) involves the unknown moments of the same order, so we move it to the left:
$$H_s^{(m)}-\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}H_t^{(m)} =\delta_{m,0}+\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}\sum_{j=0}^{m-1}\binom{m}{j}x^{m-j}H_t^{(j)}.$$
For each fixed \(m\), this is a \(20\times20\) linear system. Because the right-hand side uses only moments of order \(\lt m\), the code solves the systems in increasing order of \(m\), precomputing binomial coefficients and digit powers and then using Gaussian elimination with partial pivoting.
Choose a valid decimal prefix \(p\) and let \(s\) be the state determined by its last digit and current run length. Every admissible integer that begins with \(p\) can be written as
$$p\cdot 10^{|w|}+\operatorname{val}(w),\qquad w\in W_s.$$
Its entire contribution is therefore
$$R(p,s)=\sum_{w\in W_s}\frac{1}{p\cdot 10^{|w|}+\operatorname{val}(w)}.$$
Since \(0\le \operatorname{val}(w) \lt 10^{|w|}\), we have \(\operatorname{val}(w)/(p10^{|w|}) \lt 1/p\). For the actual computation the code uses prefixes with at least two or three digits, so this ratio is comfortably below \(1\). Hence
$$\frac{1}{p\cdot 10^{|w|}+\operatorname{val}(w)} =\sum_{m\ge 0}(-1)^m\frac{\operatorname{val}(w)^m}{p^{m+1}10^{(m+1)|w|}}.$$
Summing over all valid tails gives the key identity
$$R(p,s)=\sum_{m\ge 0}(-1)^m\frac{H_s^{(m)}}{p^{m+1}}.$$
This is the formula used by estimate_series_value. Small admissible integers are summed directly, and the rest are grouped by prefix; each prefix contributes an alternating series whose coefficients are the precomputed moments.
The C++ implementation verifies two facts before printing the final value. First, among \(1\le n\le 1200\), exactly \(20\) numbers contain three equal consecutive digits. Second, splitting the same infinite sum with prefix_digits = 2 and with prefix_digits = 3 gives answers that differ by less than \(10^{-15}\). These checks confirm both the automaton and the prefix-tail decomposition.
has_three_equal_consecutive tests the forbidden pattern directly. build_automaton creates the 20 labeled states. solve_moments computes \(H_s^{(m)}\) for \(0\le m\le 16\) using high-precision arithmetic: cpp_dec_float_100 in C++, Decimal in Python, and BigDecimal in Java. Finally, estimate_series_value adds exact reciprocals below \(10^{D-1}\), scans the admissible \(D\)-digit prefixes, determines their terminal state, and accumulates the truncated alternating expansion for \(R(p,s)\). The three solutions differ only in syntax, not in mathematics.
Let \(M\) be the largest moment index, with \(M=16\) in the repository. For each \(m\), one dense \(20\times20\) linear system is solved, so the dominant algebraic work is \(O(M\cdot 20^3)\). The prefix phase scans \(9\cdot 10^{D-1}\) candidate \(D\)-digit prefixes, which is tiny for \(D=3\). Memory usage is \(O(M\cdot 20)\) for the table of moments, plus \(O(20^2)\) temporary storage for elimination.
Sei \(\mathcal A\) die Menge aller positiven ganzen Zahlen, deren Dezimaldarstellung nirgends einen Block \(ddd\) aus drei gleichen aufeinanderfolgenden Ziffern enthält. Gesucht ist die konvergente Kempner-ähnliche Reihe
$$S=\sum_{n\in\mathcal A}\frac{1}{n}.$$
Die lokalen C++-, Python- und Java-Programme verwenden denselben Ansatz und liefern \(S \approx 253.6135092068\). Das Problem ist also nicht das reine Aufzählen, sondern die kontrollierte Summation des unendlichen Restes.
Die gleiche Zustandsmaschine, die im Code verwendet wird, liefert auch eine Konvergenzabschätzung. Sei \(a_k\) die Anzahl der zulässigen Ziffernfolgen der Länge \(k\), wobei führende Nullen für die Zählung erlaubt sind. Zerlege nach aktueller Lauflänge: \(u_k\) ende mit Lauflänge \(1\), \(v_k\) mit Lauflänge \(2\). Dann gilt \(u_{k+1}=9(u_k+v_k)\), denn man darf jede andere Ziffer anhängen, und \(v_{k+1}=u_k\), denn dieselbe Ziffer darf nur nach Lauflänge \(1\) noch einmal kommen. Also
$$a_{k+1}=9a_k+9a_{k-1}.$$
Die dominante Nullstelle von \(x^2-9x-9=0\) ist
$$\rho=\frac{9+\sqrt{117}}{2}\lt 10.$$
Damit ist die Anzahl zulässiger \(k\)-stelliger Nenner \(O(\rho^k)\), und der gesamte Beitrag der \(k\)-stelligen Zahlen ist \(O((\rho/10)^k)\). Da \(\rho/10\lt 1\), konvergiert die Reihe exponentiell schnell nach Stellenlänge.
Um zu entscheiden, ob eine weitere Ziffer angehängt werden darf, genügen zwei Informationen: die letzte Ziffer \(d\in\{0,\dots,9\}\) und die aktuelle Lauflänge \(r\in\{1,2\}\). Daraus entstehen \(20\) Zustände \(s=(d,r)\).
Von \((d,1)\) aus ist jede nächste Ziffer erlaubt. Beim Anhängen von \(d\) geht man zu \((d,2)\), beim Anhängen von \(x\ne d\) zu \((x,1)\). Von \((d,2)\) aus ist die Ziffer \(d\) verboten; jede andere Ziffer führt zu \((x,1)\). Genau diesen Übergangsgraphen erzeugt build_automaton in allen drei Implementierungen.
Fixiere einen Zustand \(s\), und sei \(W_s\) die Menge aller endlichen zulässigen Anhänge, die auf \(s\) folgen dürfen, einschließlich des leeren Anhangs \(\epsilon\). Für \(m\ge 0\) definieren wir
$$H_s^{(m)}=\sum_{w\in W_s}\frac{\operatorname{val}(w)^m}{10^{(m+1)|w|}},$$
wobei der leere Anhang bei \(m=0\) den Beitrag \(1\) und sonst den Beitrag \(0\) liefert. Schreibt man einen nichtleeren Anhang als \(w=xu\), wobei \(x\) die erste neue Ziffer ist und \(u\) der Rest vom Folgezustand \(t\), dann gilt
$$\operatorname{val}(xu)=x\cdot 10^{|u|}+\operatorname{val}(u).$$
Mit dem binomischen Lehrsatz folgt daraus
$$H_s^{(m)}=\delta_{m,0}+\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}\sum_{j=0}^{m}\binom{m}{j}x^{m-j}H_t^{(j)}.$$
Der Fall \(j=m\) enthält die unbekannten Momente derselben Ordnung. Deshalb wird er auf die linke Seite gebracht:
$$H_s^{(m)}-\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}H_t^{(m)} =\delta_{m,0}+\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}\sum_{j=0}^{m-1}\binom{m}{j}x^{m-j}H_t^{(j)}.$$
Für jedes feste \(m\) entsteht also ein lineares System der Größe \(20\times20\). Da auf der rechten Seite nur kleinere Momente vorkommen, kann der Code die Systeme der Reihe nach für \(m=0,1,\dots,16\) lösen. Genau das macht solve_moments mit vorberechneten Binomialkoeffizienten, Ziffernpotenzen und Gauß-Elimination mit Pivotisierung.
Wähle ein zulässiges Präfix \(p\) und sei \(s\) der Zustand, der durch die letzte Ziffer und die aktuelle Lauflänge dieses Präfixes bestimmt wird. Jede zulässige Zahl mit diesem Präfix hat die Form
$$p\cdot 10^{|w|}+\operatorname{val}(w),\qquad w\in W_s.$$
Ihr gesamter Beitrag ist damit
$$R(p,s)=\sum_{w\in W_s}\frac{1}{p\cdot 10^{|w|}+\operatorname{val}(w)}.$$
Weil \(0\le \operatorname{val}(w)\lt 10^{|w|}\), ist \(\operatorname{val}(w)/(p10^{|w|})\lt 1/p\). Für die tatsächlich benutzten Präfixlängen ist dieser Quotient also sicher kleiner als \(1\), und die geometrische Entwicklung ist erlaubt:
$$\frac{1}{p\cdot 10^{|w|}+\operatorname{val}(w)} =\sum_{m\ge 0}(-1)^m\frac{\operatorname{val}(w)^m}{p^{m+1}10^{(m+1)|w|}}.$$
Nach Summation über alle Anhänge erhält man die zentrale Identität
$$R(p,s)=\sum_{m\ge 0}(-1)^m\frac{H_s^{(m)}}{p^{m+1}}.$$
Genau diese Formel verwendet estimate_series_value: kleine Zahlen werden direkt aufsummiert, die unendlichen Reste werden nach Präfixen gruppiert und über die vorberechneten Momente ausgewertet.
Die C++-Version prüft vor der Endausgabe zwei einfache Fakten. Erstens enthalten unter \(1\le n\le 1200\) genau \(20\) Zahlen drei gleiche Ziffern in Folge. Zweitens liefern die beiden Zerlegungen mit prefix_digits = 2 und prefix_digits = 3 Ergebnisse, die sich um weniger als \(10^{-15}\) unterscheiden. Damit werden sowohl der Automat als auch die Präfix-Anhang-Formel getestet.
has_three_equal_consecutive erkennt das verbotene Muster direkt. build_automaton erzeugt die 20 Zustände samt Übergängen. solve_moments berechnet die Werte \(H_s^{(m)}\) für \(0\le m\le 16\) mit hochpräziser Arithmetik: cpp_dec_float_100 in C++, Decimal in Python und BigDecimal in Java. Danach summiert estimate_series_value alle Kehrwerte unterhalb von \(10^{D-1}\) exakt, läuft über die zulässigen \(D\)-stelligen Präfixe, bestimmt deren Endzustand und addiert die abgeschnittene alternierende Entwicklung für \(R(p,s)\). Mathematisch sind alle drei Fassungen identisch.
Sei \(M\) der größte Momentindex; im Repository ist \(M=16\). Für jedes \(m\) wird ein dichtes \(20\times20\)-System gelöst, also beträgt die dominierende algebraische Arbeit \(O(M\cdot 20^3)\). Die Präfixphase betrachtet \(9\cdot 10^{D-1}\) Kandidatenpräfixe, was für \(D=3\) sehr klein bleibt. Der Speicherbedarf ist \(O(M\cdot 20)\) für die Momenttabelle plus \(O(20^2)\) Arbeitsraum für die Elimination.
\(\mathcal A\), ondalık yazımında hiçbir yerde \(ddd\) biçiminde art arda üç eşit rakam içermeyen pozitif tamsayılar kümesi olsun. Hesaplanmak istenen yakınsak Kempner-benzeri seri şudur:
$$S=\sum_{n\in\mathcal A}\frac{1}{n}.$$
Depodaki C++, Python ve Java çözümleri aynı yöntemi uygular ve \(S \approx 253.6135092068\) sonucunu üretir. Dolayısıyla asıl mesele kaba kuvvet değil, sonsuz kuyruğun güvenli biçimde toplanmasıdır.
Koddaki aynı durum makinesi yakınsaklığı da açıklar. Sayım amacıyla başta sıfıra izin vererek, üç aynı ardışık rakam içermeyen uzunluğu \(k\) olan dizelerin sayısını \(a_k\) ile gösterelim. Bunları son tekrar uzunluğuna göre ayıralım: \(u_k\) son bloğu uzunluk \(1\), \(v_k\) son bloğu uzunluk \(2\) olanlar. Farklı bir rakam eklemek \(u_{k+1}=9(u_k+v_k)\) verir; aynı rakamı eklemek ise yalnızca tekrar uzunluğu \(1\) iken mümkündür, dolayısıyla \(v_{k+1}=u_k\). Buradan
$$a_{k+1}=9a_k+9a_{k-1}$$
elde edilir. \(x^2-9x-9=0\) denkleminin baskın kökü
$$\rho=\frac{9+\sqrt{117}}{2}\lt 10$$
olduğundan, uygun \(k\) basamaklı paydaların sayısı \(O(\rho^k)\), bunların terslerinin toplam katkısı ise \(O((\rho/10)^k)\) mertebesindedir. \(\rho/10\lt 1\) olduğu için seri basamak uzunluğuna göre üstel hızla yakınsar.
Yeni bir rakamın eklenip eklenemeyeceğini belirlemek için sadece iki bilgi gerekir: son rakam \(d\in\{0,\dots,9\}\) ve mevcut tekrar uzunluğu \(r\in\{1,2\}\). Böylece \(s=(d,r)\) biçiminde \(20\) durum elde edilir.
\((d,1)\) durumundan her rakam eklenebilir. Eğer eklenen rakam yine \(d\) ise yeni durum \((d,2)\), yoksa \((x,1)\) olur. \((d,2)\) durumunda ise \(d\) yasaktır; diğer dokuz rakamın her biri \((x,1)\) durumuna gider. Tüm dillerdeki build_automaton fonksiyonu tam olarak bu geçişleri kurar.
Bir \(s\) durumu için, \(W_s\) ile bu durumdan sonra gelebilecek tüm sonlu geçerli kuyrukların, yani boş kuyruk \(\epsilon\) dahil, kümesini gösterelim. \(m\ge 0\) için
$$H_s^{(m)}=\sum_{w\in W_s}\frac{\operatorname{val}(w)^m}{10^{(m+1)|w|}}$$
tanımını yapalım. Boş kuyruk \(m=0\) için \(1\), diğer durumlarda \(0\) katkısı verir. Boş olmayan bir kuyruğu \(w=xu\) biçiminde yazarsak, burada \(x\) ilk eklenen rakam, \(u\) ise sonraki durum \(t\)'den başlayan alt kuyruktur. O zaman
$$\operatorname{val}(xu)=x\cdot 10^{|u|}+\operatorname{val}(u).$$
Binom açılımı ile şu yineleme elde edilir:
$$H_s^{(m)}=\delta_{m,0}+\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}\sum_{j=0}^{m}\binom{m}{j}x^{m-j}H_t^{(j)}.$$
\(j=m\) terimi aynı dereceden bilinmeyenleri içerdiği için sola alınır:
$$H_s^{(m)}-\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}H_t^{(m)} =\delta_{m,0}+\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}\sum_{j=0}^{m-1}\binom{m}{j}x^{m-j}H_t^{(j)}.$$
Böylece her sabit \(m\) için \(20\times20\) boyutunda bir lineer sistem oluşur. Sağ tarafta yalnızca daha küçük dereceden momentler bulunduğundan kod bu sistemleri \(m=0,1,\dots,16\) sırasıyla çözer. solve_moments içinde binom katsayıları ve rakam kuvvetleri önceden hesaplanır, sonra kısmi pivotlamalı Gauss eliminasyonu uygulanır.
Geçerli bir \(p\) ön eki seçelim; bu ön ekin son rakamı ve tekrar uzunluğu bir \(s\) durumu belirler. \(p\) ile başlayan her uygun sayı
$$p\cdot 10^{|w|}+\operatorname{val}(w),\qquad w\in W_s$$
şeklinde yazılır. Dolayısıyla bu ön ekin toplam katkısı
$$R(p,s)=\sum_{w\in W_s}\frac{1}{p\cdot 10^{|w|}+\operatorname{val}(w)}$$
olur. \(0\le \operatorname{val}(w)\lt 10^{|w|}\) olduğu için \(\operatorname{val}(w)/(p10^{|w|})\lt 1/p\) yazabiliriz. Kodda kullanılan ön ekler en az iki ya da üç basamaklı olduğundan bu oran güvenle \(1\)'den küçüktür ve geometrik açılım geçerlidir:
$$\frac{1}{p\cdot 10^{|w|}+\operatorname{val}(w)} =\sum_{m\ge 0}(-1)^m\frac{\operatorname{val}(w)^m}{p^{m+1}10^{(m+1)|w|}}.$$
Tüm kuyruklar üzerinde toplarsak temel özdeşliği elde ederiz:
$$R(p,s)=\sum_{m\ge 0}(-1)^m\frac{H_s^{(m)}}{p^{m+1}}.$$
estimate_series_value tam olarak bunu uygular: küçük sayıları doğrudan toplar, geri kalan sonsuz kuyruğu ise ön eklerine göre gruplayıp önceden hesaplanmış momentlerle değerlendirir.
C++ sürümü son değeri yazmadan önce iki denetim yapar. Birincisi, \(1\le n\le 1200\) aralığında art arda üç eşit rakam içeren sayı sayısı tam olarak \(20\)'dir. İkincisi, aynı sonsuz toplamı prefix_digits = 2 ve prefix_digits = 3 ile parçalamak \(10^{-15}\)'ten küçük fark verir. Böylece hem otomaton hem de ön ek-kuyruk ayrıştırması doğrulanmış olur.
has_three_equal_consecutive yasak deseni doğrudan test eder. build_automaton 20 durumlu geçiş grafiğini kurar. solve_moments, \(0\le m\le 16\) için \(H_s^{(m)}\) değerlerini yüksek hassasiyetli sayılarla hesaplar: C++ tarafında cpp_dec_float_100, Python tarafında Decimal, Java tarafında BigDecimal kullanılır. Son olarak estimate_series_value, \(10^{D-1}\)'den küçük sayıları tam olarak toplar, uygun \(D\) basamaklı ön ekleri dolaşır, son durumlarını belirler ve \(R(p,s)\) için kesilmiş alternanslı seriyi ekler. Üç çözüm arasında yalnızca sözdizimi farkı vardır.
\(M\) en büyük moment derecesi olsun; bu depoda \(M=16\). Her \(m\) için bir adet yoğun \(20\times20\) lineer sistem çözülür, dolayısıyla baskın cebirsel maliyet \(O(M\cdot 20^3)\)'tür. Ön ek aşaması \(9\cdot 10^{D-1}\) kadar aday \(D\) basamaklı ön eki tarar; \(D=3\) için bu çok küçüktür. Bellek kullanımı moment tablosu için \(O(M\cdot 20)\), eliminasyon çalışma alanı için ek olarak \(O(20^2)\) düzeyindedir.
Sea \(\mathcal A\) el conjunto de enteros positivos cuya escritura decimal no contiene en ninguna posición un bloque \(ddd\) de tres dígitos iguales consecutivos. Debemos calcular la serie convergente de tipo Kempner
$$S=\sum_{n\in\mathcal A}\frac{1}{n}.$$
Las soluciones locales en C++, Python y Java implementan exactamente la misma idea y producen \(S \approx 253.6135092068\). El reto verdadero no es enumerar números, sino sumar correctamente la cola infinita.
La misma máquina de estados usada por el código permite justificar la convergencia. Sea \(a_k\) el número de cadenas decimales válidas de longitud \(k\), permitiendo ceros iniciales solo para contar. Separémoslas en \(u_k\), las que terminan con longitud de racha \(1\), y \(v_k\), las que terminan con longitud de racha \(2\). Al añadir un dígito distinto obtenemos \(u_{k+1}=9(u_k+v_k)\); al repetir el último dígito solo podemos partir de una racha de longitud \(1\), así que \(v_{k+1}=u_k\). En consecuencia,
$$a_{k+1}=9a_k+9a_{k-1}.$$
La raíz dominante de \(x^2-9x-9=0\) es
$$\rho=\frac{9+\sqrt{117}}{2}\lt 10.$$
Por tanto, el número de denominadores válidos de \(k\) cifras es \(O(\rho^k)\), y la contribución total de todas las fracciones con \(k\) cifras es \(O((\rho/10)^k)\). Como \(\rho/10\lt 1\), la serie converge de forma exponencial por número de cifras.
Para decidir si se puede añadir otro dígito, solo hacen falta dos datos: el último dígito \(d\in\{0,\dots,9\}\) y si la racha actual tiene longitud \(1\) o \(2\). Eso produce \(20\) estados \(s=(d,r)\).
Desde \((d,1)\) se puede añadir cualquier dígito. Si añadimos otra vez \(d\), pasamos a \((d,2)\); si añadimos \(x\ne d\), pasamos a \((x,1)\). Desde \((d,2)\), el dígito \(d\) queda prohibido y cualquiera de los otros nueve lleva a \((x,1)\). Eso es exactamente lo que construye build_automaton en las tres implementaciones.
Fijemos un estado \(s\) y llamemos \(W_s\) al conjunto de todas las colas finitas válidas que pueden seguir a \(s\), incluyendo la cola vacía \(\epsilon\). Para \(m\ge 0\) definimos
$$H_s^{(m)}=\sum_{w\in W_s}\frac{\operatorname{val}(w)^m}{10^{(m+1)|w|}}.$$
La cola vacía aporta \(1\) cuando \(m=0\) y \(0\) en los demás casos. Si una cola no vacía se escribe como \(w=xu\), donde \(x\) es el primer dígito añadido y \(u\) es la cola restante desde el estado siguiente \(t\), entonces
$$\operatorname{val}(xu)=x\cdot 10^{|u|}+\operatorname{val}(u).$$
Aplicando el teorema binomial se obtiene
$$H_s^{(m)}=\delta_{m,0}+\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}\sum_{j=0}^{m}\binom{m}{j}x^{m-j}H_t^{(j)}.$$
El término con \(j=m\) contiene incógnitas del mismo orden, así que se mueve al lado izquierdo:
$$H_s^{(m)}-\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}H_t^{(m)} =\delta_{m,0}+\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}\sum_{j=0}^{m-1}\binom{m}{j}x^{m-j}H_t^{(j)}.$$
Para cada \(m\) fijo aparece así un sistema lineal de tamaño \(20\times20\). Como el lado derecho solo depende de momentos de orden menor, el programa resuelve estos sistemas en orden creciente de \(m\), con coeficientes binomiales y potencias de dígitos precalculados y eliminación gaussiana con pivoteo parcial.
Tomemos un prefijo válido \(p\) y sea \(s\) el estado que determinan su último dígito y la longitud actual de su racha. Todo entero admisible que empiece por \(p\) puede escribirse como
$$p\cdot 10^{|w|}+\operatorname{val}(w),\qquad w\in W_s.$$
Su contribución total es
$$R(p,s)=\sum_{w\in W_s}\frac{1}{p\cdot 10^{|w|}+\operatorname{val}(w)}.$$
Como \(0\le \operatorname{val}(w)\lt 10^{|w|}\), tenemos \(\operatorname{val}(w)/(p10^{|w|})\lt 1/p\). Con prefijos de dos o tres cifras, que son los usados por el código, esta razón es menor que \(1\), así que la expansión geométrica es válida:
$$\frac{1}{p\cdot 10^{|w|}+\operatorname{val}(w)} =\sum_{m\ge 0}(-1)^m\frac{\operatorname{val}(w)^m}{p^{m+1}10^{(m+1)|w|}}.$$
Al sumar sobre todas las colas válidas se obtiene la identidad central
$$R(p,s)=\sum_{m\ge 0}(-1)^m\frac{H_s^{(m)}}{p^{m+1}}.$$
Esta es la fórmula que utiliza estimate_series_value. Los números pequeños se suman exactamente y la cola infinita se agrupa por prefijos, usando los momentos ya calculados.
La versión en C++ comprueba dos hechos antes de imprimir el resultado final. Primero, entre \(1\le n\le 1200\) hay exactamente \(20\) enteros que contienen tres cifras iguales consecutivas. Segundo, descomponer la misma suma infinita con prefix_digits = 2 o con prefix_digits = 3 produce valores cuya diferencia es menor que \(10^{-15}\). Son verificaciones directas del autómata y de la descomposición prefijo-cola.
has_three_equal_consecutive detecta directamente el patrón prohibido. build_automaton crea el grafo de 20 estados etiquetados. solve_moments calcula \(H_s^{(m)}\) para \(0\le m\le 16\) con aritmética de alta precisión: cpp_dec_float_100 en C++, Decimal en Python y BigDecimal en Java. Después, estimate_series_value suma de forma exacta los recíprocos por debajo de \(10^{D-1}\), recorre los prefijos admisibles de \(D\) cifras, determina su estado terminal y añade la expansión alternante truncada para \(R(p,s)\). Matemáticamente, las tres versiones son equivalentes.
Sea \(M\) el mayor índice de momento; en el repositorio se usa \(M=16\). Para cada \(m\) se resuelve un sistema denso \(20\times20\), así que el coste algebraico dominante es \(O(M\cdot 20^3)\). La fase de prefijos recorre \(9\cdot 10^{D-1}\) prefijos candidatos de \(D\) cifras, lo cual es muy pequeño para \(D=3\). La memoria es \(O(M\cdot 20)\) para la tabla de momentos, más \(O(20^2)\) de espacio temporal para la eliminación.
设 \(\mathcal A\) 为所有正整数中这样的一类：它们的十进制表示里从不出现 \(ddd\) 这种三个连续相同数字的块。要求计算的就是下面这个收敛的 Kempner 型级数：
$$S=\sum_{n\in\mathcal A}\frac{1}{n}.$$
仓库中的 C++、Python 和 Java 解法使用的是同一套数学结构，最终都输出 \(S \approx 253.6135092068\)。真正的难点不在于枚举，而在于如何把无限尾项稳定地求和。
代码中的状态机本身就能给出收敛性说明。令 \(a_k\) 表示长度为 \(k\) 的合法数字串个数，这里为了计数方便允许前导零。再把它们分成两类：\(u_k\) 表示末尾连续段长度为 \(1\) 的串，\(v_k\) 表示末尾连续段长度为 \(2\) 的串。下一位若换成不同数字，就有 \(u_{k+1}=9(u_k+v_k)\)；下一位若仍然与末位相同，则只能从连续段长度为 \(1\) 的状态转移，因此 \(v_{k+1}=u_k\)。于是
$$a_{k+1}=9a_k+9a_{k-1}.$$
方程 \(x^2-9x-9=0\) 的主根为
$$\rho=\frac{9+\sqrt{117}}{2}\lt 10.$$
因此合法的 \(k\) 位分母个数是 \(O(\rho^k)\)，所有 \(k\) 位项的倒数总贡献是 \(O((\rho/10)^k)\)。因为 \(\rho/10\lt 1\)，所以该级数按位数呈指数收敛。
判断能否继续追加一位，只需要保存两件事：最后一位数字 \(d\in\{0,\dots,9\}\)，以及当前连续相同数字段的长度 \(r\in\{1,2\}\)。这样总共有 \(20\) 个状态 \(s=(d,r)\)。
从 \((d,1)\) 出发，任意下一位都合法。如果追加的还是 \(d\)，状态变成 \((d,2)\)；如果追加的是 \(x\ne d\)，状态变成 \((x,1)\)。从 \((d,2)\) 出发，数字 \(d\) 被禁止，其余九个数字都转到 \((x,1)\)。三个语言版本里的 build_automaton 都是在构造这一张带标号的状态图。
固定一个状态 \(s\)，记 \(W_s\) 为从该状态出发可以接上的所有有限合法尾串的集合，其中包括空尾串 \(\epsilon\)。对任意 \(m\ge 0\)，定义
$$H_s^{(m)}=\sum_{w\in W_s}\frac{\operatorname{val}(w)^m}{10^{(m+1)|w|}}.$$
约定空尾串在 \(m=0\) 时贡献 \(1\)，在其他阶数时贡献 \(0\)。如果非空尾串写成 \(w=xu\)，其中 \(x\) 是新接上的第一位，\(u\) 是从下一状态 \(t\) 开始的剩余尾串，那么
$$\operatorname{val}(xu)=x\cdot 10^{|u|}+\operatorname{val}(u).$$
对上式应用二项式展开，可得
$$H_s^{(m)}=\delta_{m,0}+\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}\sum_{j=0}^{m}\binom{m}{j}x^{m-j}H_t^{(j)}.$$
其中 \(j=m\) 的项含有同阶未知量，所以移到左边：
$$H_s^{(m)}-\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}H_t^{(m)} =\delta_{m,0}+\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}\sum_{j=0}^{m-1}\binom{m}{j}x^{m-j}H_t^{(j)}.$$
于是每个固定的 \(m\) 都对应一个 \(20\times20\) 的线性方程组。由于右边只依赖更低阶的矩，程序可以按 \(m=0,1,\dots,16\) 的顺序求解。solve_moments 先预计算二项式系数和数字幂，再做带部分主元的高斯消元。
取一个合法前缀 \(p\)，由它的最后一位和当前连续长度确定一个状态 \(s\)。所有以 \(p\) 开头的合法整数都可以写成
$$p\cdot 10^{|w|}+\operatorname{val}(w),\qquad w\in W_s.$$
因此这一整个前缀类的贡献是
$$R(p,s)=\sum_{w\in W_s}\frac{1}{p\cdot 10^{|w|}+\operatorname{val}(w)}.$$
因为 \(0\le \operatorname{val}(w)\lt 10^{|w|}\)，所以 \(\operatorname{val}(w)/(p10^{|w|})\lt 1/p\)。代码实际使用的是两位或三位前缀，因此这个比例显然小于 \(1\)，可以作几何级数展开：
$$\frac{1}{p\cdot 10^{|w|}+\operatorname{val}(w)} =\sum_{m\ge 0}(-1)^m\frac{\operatorname{val}(w)^m}{p^{m+1}10^{(m+1)|w|}}.$$
对所有合法尾串求和后，就得到核心公式
$$R(p,s)=\sum_{m\ge 0}(-1)^m\frac{H_s^{(m)}}{p^{m+1}}.$$
estimate_series_value 正是据此工作：小整数直接精确求和，大整数按前缀分组，用预先求出的矩来近似无限尾项。
C++ 版本在输出最终结果前做了两个检查。第一，在 \(1\le n\le 1200\) 中，恰好有 \(20\) 个整数含有三个连续相同数字。第二，用 prefix_digits = 2 和 prefix_digits = 3 两种切分方式计算同一个无穷和，结果之差小于 \(10^{-15}\)。这两个检查分别验证了自动机和前缀-尾串分解。
has_three_equal_consecutive 直接判断禁用模式。build_automaton 构造 20 个状态及其带数字标签的转移。solve_moments 使用高精度数值类型计算 \(0\le m\le 16\) 的所有 \(H_s^{(m)}\)：C++ 用 cpp_dec_float_100，Python 用 Decimal，Java 用 BigDecimal。最后，estimate_series_value 先精确累加所有小于 \(10^{D-1}\) 的合法倒数，再遍历所有合法的 \(D\) 位前缀，求出其终止状态，并累加 \(R(p,s)\) 的截断交错级数。三份代码只是在语法上不同，数学内容完全一致。
设最大矩阶为 \(M\)，仓库中取 \(M=16\)。每个 \(m\) 都要解一个稠密的 \(20\times20\) 线性系统，因此主要代数成本是 \(O(M\cdot 20^3)\)。前缀阶段扫描 \(9\cdot 10^{D-1}\) 个候选 \(D\) 位前缀，而在 \(D=3\) 时这个规模很小。内存方面，矩表需要 \(O(M\cdot 20)\)，高斯消元的临时空间为 \(O(20^2)\)。
Пусть \(\mathcal A\) обозначает множество положительных целых чисел, в десятичной записи которых нигде не встречается блок \(ddd\) из трёх одинаковых подряд цифр. Требуется вычислить сходящийся ряд кемпнеровского типа
$$S=\sum_{n\in\mathcal A}\frac{1}{n}.$$
Локальные реализации на C++, Python и Java используют один и тот же метод и выводят \(S \approx 253.6135092068\). Основная трудность состоит не в переборе, а в аккуратном суммировании бесконечного хвоста допустимых чисел.
Та же конечная автоматика, которая используется в коде, даёт и оценку сходимости. Пусть \(a_k\) — число допустимых десятичных строк длины \(k\), если для подсчёта разрешить ведущие нули. Разобьём их на \(u_k\), оканчивающиеся серией длины \(1\), и \(v_k\), оканчивающиеся серией длины \(2\). При добавлении другой цифры получаем \(u_{k+1}=9(u_k+v_k)\); повторить последнюю цифру можно только после серии длины \(1\), поэтому \(v_{k+1}=u_k\). Следовательно,
$$a_{k+1}=9a_k+9a_{k-1}.$$
Доминирующий корень уравнения \(x^2-9x-9=0\) равен
$$\rho=\frac{9+\sqrt{117}}{2}\lt 10.$$
Значит, число допустимых знаменателей длины \(k\) есть \(O(\rho^k)\), а суммарный вклад всех \(k\)-значных членов равен \(O((\rho/10)^k)\). Поскольку \(\rho/10\lt 1\), ряд сходится экспоненциально быстро по длине записи.
Чтобы понять, можно ли приписать очередную цифру, достаточно знать только две вещи: последнюю цифру \(d\in\{0,\dots,9\}\) и текущую длину серии \(r\in\{1,2\}\). Это даёт \(20\) состояний вида \(s=(d,r)\).
Из состояния \((d,1)\) разрешены все десять цифр. Если приписать снова \(d\), получаем состояние \((d,2)\); если приписать \(x\ne d\), переходим в \((x,1)\). Из состояния \((d,2)\) цифра \(d\) запрещена, а каждая другая цифра ведёт в \((x,1)\). Ровно такой граф переходов строит функция build_automaton во всех трёх реализациях.
Зафиксируем состояние \(s\) и обозначим через \(W_s\) множество всех конечных допустимых хвостов, которые можно приписать после \(s\), включая пустой хвост \(\epsilon\). Для \(m\ge 0\) определим
$$H_s^{(m)}=\sum_{w\in W_s}\frac{\operatorname{val}(w)^m}{10^{(m+1)|w|}}.$$
Пустой хвост даёт вклад \(1\) при \(m=0\) и \(0\) при \(m>0\). Если непустой хвост записать как \(w=xu\), где \(x\) — первая добавленная цифра, а \(u\) — оставшийся хвост из следующего состояния \(t\), то
$$\operatorname{val}(xu)=x\cdot 10^{|u|}+\operatorname{val}(u).$$
Применяя биномиальную формулу, получаем
$$H_s^{(m)}=\delta_{m,0}+\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}\sum_{j=0}^{m}\binom{m}{j}x^{m-j}H_t^{(j)}.$$
Слагаемое с \(j=m\) содержит неизвестные того же порядка, поэтому переносится влево:
$$H_s^{(m)}-\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}H_t^{(m)} =\delta_{m,0}+\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}\sum_{j=0}^{m-1}\binom{m}{j}x^{m-j}H_t^{(j)}.$$
Для каждого фиксированного \(m\) это линейная система размера \(20\times20\). Правая часть зависит только от моментов меньшего порядка, поэтому программа решает системы последовательно по \(m\), заранее вычисляя биномиальные коэффициенты и степени цифр, а затем применяя метод Гаусса с частичным выбором главного элемента.
Возьмём допустимый префикс \(p\) и обозначим через \(s\) состояние, которое определяется его последней цифрой и длиной текущей серии. Любое допустимое число, начинающееся с \(p\), имеет вид
$$p\cdot 10^{|w|}+\operatorname{val}(w),\qquad w\in W_s.$$
Полный вклад такого префикса равен
$$R(p,s)=\sum_{w\in W_s}\frac{1}{p\cdot 10^{|w|}+\operatorname{val}(w)}.$$
Так как \(0\le \operatorname{val}(w)\lt 10^{|w|}\), имеем \(\operatorname{val}(w)/(p10^{|w|})\lt 1/p\). В программе используются префиксы длины не меньше двух или трёх цифр, так что этот параметр строго меньше \(1\), и можно разложить в геометрический ряд:
$$\frac{1}{p\cdot 10^{|w|}+\operatorname{val}(w)} =\sum_{m\ge 0}(-1)^m\frac{\operatorname{val}(w)^m}{p^{m+1}10^{(m+1)|w|}}.$$
Суммируя по всем допустимым хвостам, получаем ключевую формулу
$$R(p,s)=\sum_{m\ge 0}(-1)^m\frac{H_s^{(m)}}{p^{m+1}}.$$
Именно её использует estimate_series_value: малые числа суммируются напрямую, а бесконечный хвост группируется по префиксам и оценивается через заранее найденные моменты.
Версия на C++ выполняет две проверки перед выводом ответа. Во-первых, среди чисел \(1\le n\le 1200\) ровно \(20\) содержат три одинаковые подряд цифры. Во-вторых, разбиение одной и той же бесконечной суммы при prefix_digits = 2 и при prefix_digits = 3 даёт результаты, отличающиеся менее чем на \(10^{-15}\). Эти проверки подтверждают корректность автомата и формулы префикс-хвост.
has_three_equal_consecutive напрямую проверяет запрещённый шаблон. build_automaton строит граф из 20 помеченных состояний. solve_moments вычисляет значения \(H_s^{(m)}\) для \(0\le m\le 16\) с высокой точностью: в C++ используется cpp_dec_float_100, в Python Decimal, в Java BigDecimal. Затем estimate_series_value точно суммирует обратные числа ниже \(10^{D-1}\), перебирает допустимые \(D\)-значные префиксы, определяет их конечное состояние и добавляет усечённый знакочередующийся ряд для \(R(p,s)\). Во всех трёх файлах различается только синтаксис.
Пусть \(M\) — максимальный индекс момента; в репозитории используется \(M=16\). Для каждого \(m\) решается плотная система \(20\times20\), поэтому основная алгебраическая стоимость равна \(O(M\cdot 20^3)\). На фазе префиксов проверяется \(9\cdot 10^{D-1}\) кандидатных префиксов длины \(D\), что мало при \(D=3\). Память составляет \(O(M\cdot 20)\) для таблицы моментов и ещё \(O(20^2)\) для рабочего пространства метода Гаусса.
لتكن \(\mathcal A\) مجموعة الأعداد الصحيحة الموجبة التي لا تحتوي كتابتها العشرية في أي موضع على كتلة من الشكل \(ddd\)، أي ثلاث خانات متساوية متتالية. المطلوب هو حساب السلسلة المتقاربة الشبيهة بسلسلة Kempner:
$$S=\sum_{n\in\mathcal A}\frac{1}{n}.$$
البرامج المحلية في C++ وPython وJava تطبق الفكرة نفسها وتنتج \(S \approx 253.6135092068\). لذلك فالمشكلة ليست في العد المباشر، بل في جمع الذيل اللانهائي للأعداد المسموح بها بطريقة مستقرة ودقيقة.
آلة الحالات نفسها المستعملة في الشيفرة تعطي برهاناً عملياً على التقارب. لنرمز بـ \(a_k\) إلى عدد السلاسل العشرية الصحيحة من الطول \(k\) التي لا تحتوي ثلاث خانات متساوية متتالية، مع السماح بالأصفار البادئة لغرض العد فقط. نقسمها إلى \(u_k\) للسلاسل التي تنتهي بطول تكرار \(1\)، و\(v_k\) للسلاسل التي تنتهي بطول تكرار \(2\). عند إضافة رقم مختلف نحصل على \(u_{k+1}=9(u_k+v_k)\)، أما تكرار الرقم نفسه فلا يكون ممكناً إلا إذا كان طول التكرار الحالي \(1\)، لذا \(v_{k+1}=u_k\). ومن ثم
$$a_{k+1}=9a_k+9a_{k-1}.$$
الجذر الغالب للمعادلة \(x^2-9x-9=0\) هو
$$\rho=\frac{9+\sqrt{117}}{2}\lt 10.$$
إذن عدد المقامات المسموح بها ذات \(k\) خانات هو \(O(\rho^k)\)، ومجموع مساهمات جميع الكسور ذات \(k\) خانات يساوي \(O((\rho/10)^k)\). وبما أن \(\rho/10\lt 1\)، فإن السلسلة تتقارب بسرعة أسية بحسب عدد الخانات.
حتى نعرف هل يجوز إلحاق رقم جديد، نحتاج فقط إلى معلومتين: آخر رقم \(d\in\{0,\dots,9\}\)، وطول التكرار الحالي \(r\in\{1,2\}\). وهذا ينتج \(20\) حالة من الشكل \(s=(d,r)\).
من الحالة \((d,1)\) يمكن إضافة أي رقم. إذا أضفنا \(d\) مرة أخرى ننتقل إلى \((d,2)\)، وإذا أضفنا رقماً مختلفاً \(x\ne d\) ننتقل إلى \((x,1)\). أما من الحالة \((d,2)\) فإن الرقم \(d\) يصبح ممنوعاً، وكل رقم آخر يقود إلى \((x,1)\). هذه هي بالضبط البنية التي تبنيها الدالة build_automaton في اللغات الثلاث.
ثبّت حالة \(s\)، ولتكن \(W_s\) مجموعة جميع الذيول المنتهية الصالحة التي يمكن أن تأتي بعد هذه الحالة، مع تضمين الذيل الفارغ \(\epsilon\). لكل \(m\ge 0\) نعرّف
$$H_s^{(m)}=\sum_{w\in W_s}\frac{\operatorname{val}(w)^m}{10^{(m+1)|w|}}.$$
يساهم الذيل الفارغ بالقيمة \(1\) عندما \(m=0\)، وبالقيمة \(0\) عندما \(m>0\). وإذا كتبنا ذيلاً غير فارغ بالشكل \(w=xu\)، حيث \(x\) هو الرقم الأول الملحق و\(u\) هو بقية الذيل المنطلق من الحالة التالية \(t\)، فإن
$$\operatorname{val}(xu)=x\cdot 10^{|u|}+\operatorname{val}(u).$$
وباستخدام مفكوك ذي الحدين نحصل على العلاقة
$$H_s^{(m)}=\delta_{m,0}+\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}\sum_{j=0}^{m}\binom{m}{j}x^{m-j}H_t^{(j)}.$$
الحد الموافق لـ \(j=m\) يحتوي على مجاهيل من الرتبة نفسها، لذلك ننقله إلى الطرف الأيسر:
$$H_s^{(m)}-\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}H_t^{(m)} =\delta_{m,0}+\frac{1}{10^{m+1}}\sum_{(x,t)\in T(s)}\sum_{j=0}^{m-1}\binom{m}{j}x^{m-j}H_t^{(j)}.$$
لكل قيمة ثابتة من \(m\) نحصل إذاً على نظام خطي بحجم \(20\times20\). ولأن الطرف الأيمن يعتمد فقط على عزوم أقل رتبة، فإن الشيفرة تحل هذه الأنظمة بالتتابع من \(m=0\) حتى \(m=16\). وهذا ما تفعله الدالة solve_moments بعد تجهيز معاملات ثنائية الحدين وقوى الأرقام ثم تطبيق حذف Gauss مع محور جزئي.
اختر بادئة صالحة \(p\)، ولتكن \(s\) هي الحالة التي تحددها آخر خانة في هذه البادئة وطول التكرار الحالي فيها. كل عدد مسموح يبدأ بهذه البادئة يمكن كتابته على الصورة
$$p\cdot 10^{|w|}+\operatorname{val}(w),\qquad w\in W_s.$$
ومن ثم يكون مجمل مساهمة هذه البادئة
$$R(p,s)=\sum_{w\in W_s}\frac{1}{p\cdot 10^{|w|}+\operatorname{val}(w)}.$$
وبما أن \(0\le \operatorname{val}(w)\lt 10^{|w|}\)، فإن \(\operatorname{val}(w)/(p10^{|w|})\lt 1/p\). وفي الحساب الفعلي تستعمل الشيفرة بادئات من خانتين أو ثلاث خانات، لذا تكون هذه النسبة أصغر من \(1\) قطعاً، ويمكن استعمال متسلسلة هندسية:
$$\frac{1}{p\cdot 10^{|w|}+\operatorname{val}(w)} =\sum_{m\ge 0}(-1)^m\frac{\operatorname{val}(w)^m}{p^{m+1}10^{(m+1)|w|}}.$$
وبعد الجمع على كل الذيول المسموح بها نحصل على الهوية الأساسية
$$R(p,s)=\sum_{m\ge 0}(-1)^m\frac{H_s^{(m)}}{p^{m+1}}.$$
هذه هي الصيغة التي تعتمد عليها الدالة estimate_series_value: الأعداد الصغيرة تُجمع مباشرة، أما الذيل اللانهائي فيُجمّع بحسب البادئات وتُحسب مساهمته باستعمال العزوم المحسوبة مسبقاً.
نسخة C++ تتحقق من حقيقتين قبل طباعة الناتج النهائي. الأولى أن عدد الأعداد ضمن المجال \(1\le n\le 1200\) التي تحتوي ثلاث خانات متساوية متتالية يساوي تماماً \(20\). والثانية أن تفكيك المجموع نفسه باستخدام prefix_digits = 2 أو باستخدام prefix_digits = 3 يعطي قيمتين يختلفان بأقل من \(10^{-15}\). هاتان النقطتان تؤكدان صحة الآلة وصحة تفكيك البادئة والذيل.
الدالة has_three_equal_consecutive تختبر النمط الممنوع مباشرة. والدالة build_automaton تنشئ مخطط الانتقالات ذي الحالات العشرين. ثم تحسب solve_moments القيم \(H_s^{(m)}\) لكل \(0\le m\le 16\) باستعمال حساب عالي الدقة: cpp_dec_float_100 في C++، وDecimal في Python، وBigDecimal في Java. بعد ذلك تجمع estimate_series_value المقلوبات الأصغر من \(10^{D-1}\) بدقة تامة، ثم تمر على البادئات المسموح بها ذات \(D\) خانات، وتحدد الحالة النهائية لكل بادئة، وتضيف المتسلسلة المتناوبة المقطوعة الخاصة بـ \(R(p,s)\). الفارق بين الملفات الثلاثة لغوي فقط، أما الرياضيات فواحدة.
لتكن \(M\) أكبر رتبة للعزم، وفي هذا المستودع نأخذ \(M=16\). لكل قيمة من \(m\) يجري حل نظام خطي كثيف حجمه \(20\times20\)، ولذلك يكون العبء الجبري المسيطر هو \(O(M\cdot 20^3)\). مرحلة البادئات تمر على \(9\cdot 10^{D-1}\) بادئة مرشحة من طول \(D\)، وهذا عدد صغير جداً عندما \(D=3\). أما الذاكرة فهي \(O(M\cdot 20)\) لتخزين جدول العزوم، إضافة إلى \(O(20^2)\) كمساحة عمل مؤقتة أثناء الحذف.