For every \(d\)-digit integer \(n\), the problem applies a rounded square-root iteration starting from a digit-based initial guess \(x_0\). We must count how many iteration steps are needed until the estimate stops changing, then average that count over all \(d\)-digit numbers.
If we write the current estimate as \(x\), the next estimate is defined by
$$c(n,x)=\left\lceil\frac{n}{x}\right\rceil,\qquad y(n,x)=\left\lfloor\frac{x+c(n,x)}{2}\right\rfloor.$$
The process stops when \(y(n,x)=x\). The brute-force approach would repeat this for every \(n\) separately, but for \(d=14\) there are \(9\cdot 10^{13}\) inputs, so the code instead groups numbers into intervals that share the same next iterate.
The map
$$x\longmapsto \left\lfloor\frac{x+\left\lceil n/x\right\rceil}{2}\right\rfloor$$
is an integer version of Heron's method / Newton's method for \(\sqrt{n}\). The real Newton step would use \(n/x\); here that quotient is first rounded upward by the ceiling function and then averaged with the current guess.
For a fixed \(n\), define the iteration count recursively by
$$\tau(n,x)= \begin{cases} 1,& y(n,x)=x,\\ 1+\tau(n,y(n,x)),& y(n,x)\ne x. \end{cases}$$
The leading \(1\) means that the current application of the update rule always counts as one step.
The stopping condition is
$$\left\lfloor\frac{x+\left\lceil n/x\right\rceil}{2}\right\rfloor=x.$$
Because \(x+\lceil n/x\rceil\) is an integer, this is equivalent to
$$2x\le x+\left\lceil\frac{n}{x}\right\rceil \le 2x+1,$$
hence
$$x\le \left\lceil\frac{n}{x}\right\rceil \le x+1.$$
Converting this back to inequalities in \(n\) gives the exact stabilization band
$$x(x-1) < n \le x(x+1).$$
So all integers in
$$[x(x-1)+1,\;x(x+1)]$$
stop immediately when the current estimate is \(x\). The code exploits this implicitly: whenever the next iterate equals the current one, recursion stops on that subinterval.
The initial estimate depends only on the digit length \(d\):
$$x_0= \begin{cases} 2\cdot 10^{(d-1)/2},& d\text{ odd},\\ 7\cdot 10^{(d-2)/2},& d\text{ even}. \end{cases}$$
This is natural because the square roots of \(d\)-digit numbers all lie in one decimal magnitude band.
If \(d=2k+1\) is odd, then
$$10^k \le \sqrt{n} < \sqrt{10}\,10^k,$$
so \(2\cdot 10^k\) is a reasonable central first guess.
If \(d=2k\) is even, then
$$\sqrt{10}\,10^{k-1} \le \sqrt{n} < 10^k,$$
and \(7\cdot 10^{k-1}\) lies comfortably inside that range.
Instead of processing one number \(n\) at a time, the code processes an entire interval \([L,H]\) that currently shares the same estimate \(x\). Define
$$T([L,H],x)=\sum_{n=L}^{H}\tau(n,x).$$
Every number contributes at least one step for the current update, so
$$T([L,H],x)=|[L,H]|+\sum_{n=L}^{H}\mathbf{1}_{y(n,x)\ne x}\,\tau(n,y(n,x)).$$
If we group together all \(n\) that have the same next value \(y\), we obtain the interval recursion
$$T([L,H],x)=|[L,H]|+\sum_{y\ne x}T(I_y,y),$$
where \(I_y\subseteq[L,H]\) is the set of numbers whose next iterate is exactly \(y\).
The quantity
$$c(n,x)=\left\lceil\frac{n}{x}\right\rceil$$
is piecewise constant in \(n\). For a fixed integer \(c\), the condition \(\lceil n/x\rceil=c\) is equivalent to
$$ (c-1)x < n \le cx,$$
so over integers the interval is
$$[(c-1)x+1,\;cx].$$
Within such a block the next iterate is constant, because
$$y=\left\lfloor\frac{x+c}{2}\right\rfloor.$$
Conversely, for a fixed next value \(y\), the floor identity
$$\left\lfloor\frac{x+c}{2}\right\rfloor=y$$
means that \(x+c\) can only be \(2y\) or \(2y+1\). Therefore the possible \(c\)-values are
$$c=2y-x\qquad\text{or}\qquad c=2y-x+1.$$
This is exactly why the code uses
$$cl=2y-x,\qquad ch=cl+1.$$
After intersecting these with the actual range \(c_{\min}\le c\le c_{\max}\), it converts them back to an integer subinterval in \(n\).
For \(d=2\), the initial guess is \(x_0=7\), and the full domain is \([10,99]\).
Here
$$c_{\min}=\left\lceil\frac{10}{7}\right\rceil=2,\qquad c_{\max}=\left\lceil\frac{99}{7}\right\rceil=15.$$
The interval partitions by next iterate as follows:
$$[10,14]\to 4,\qquad [15,28]\to 5,\qquad [29,42]\to 6,$$
$$[43,56]\to 7,\qquad [57,70]\to 8,\qquad [71,84]\to 9,$$
$$[85,98]\to 10,\qquad [99,99]\to 11.$$
The middle block \([43,56]\) is already stable because it is exactly the band
$$7\cdot 6 < n \le 7\cdot 8,$$
that is, \(42 < n \le 56\).
For \(n=10\) with initial guess \(x_0=7\), the sequence is
$$7\to 4\to 3\to 3,$$
so the iteration count is \(3\).
For \(n=24\), the sequence is
$$7\to 5\to 5,$$
so the count is \(2\).
For \(n=99\), the sequence is
$$7\to 11\to 10\to 10,$$
so the count is again \(3\).
These examples show that the iterate is not necessarily monotone in \(x\); what matters is that the interval recursion reproduces the exact same branches as the original per-number process.
The C++ file contains a checkpoint for 5-digit numbers:
$$A_5=3.2102888889\ldots$$
More precisely, the code asserts that the average lies strictly between
$$3.2102888888 \quad\text{and}\quad 3.2102888890.$$
This is a useful sanity check before computing the 14-digit case.
The helper ceil_div computes \(\lceil a/b\rceil\). The recursive routine total_iterations(lo, hi, x) returns \(T([lo,hi],x)\): it first adds the interval size \((hi-lo+1)\) for the current step, then computes the possible next values \(y\), derives the corresponding \(n\)-subinterval for each \(y\), and recurses only when \(y\ne x\). The wrapper average_iterations_for_digits(d) builds the \(d\)-digit domain, chooses the correct \(x_0\), and divides the total by the number of \(d\)-digit inputs, namely
$$9\cdot 10^{d-1}.$$
The naive method would inspect every one of the \(9\cdot 10^{d-1}\) integers separately. The interval method instead visits only the subintervals induced by the map \(n\mapsto y(n,x)\). Each recursive call partitions its interval into a small number of child intervals, and those children are disjoint. So the runtime is governed by the number of distinct interval/estimate pairs that actually occur, which is dramatically smaller than the size of the full input range.
Memory usage is just the recursion stack, because no large tables are stored.
Für jede \(d\)-stellige Zahl \(n\) wird eine gerundete Wurzeliteration mit einem nur von \(d\) abhängigen Startwert \(x_0\) ausgeführt. Gesucht ist die mittlere Anzahl an Schritten, bis sich der Schätzwert nicht mehr ändert.
Mit aktuellem Schätzwert \(x\) lautet die Abbildung
$$c(n,x)=\left\lceil\frac{n}{x}\right\rceil,\qquad y(n,x)=\left\lfloor\frac{x+c(n,x)}{2}\right\rfloor.$$
Der Prozess endet, sobald \(y(n,x)=x\). Ein naiver Ansatz würde dies für jedes \(n\) einzeln simulieren; der Code fasst stattdessen ganze Intervalle zusammen, die denselben nächsten Schätzwert besitzen.
Die Abbildung
$$x\longmapsto \left\lfloor\frac{x+\left\lceil n/x\right\rceil}{2}\right\rfloor$$
ist eine ganzzahlige Variante des Heron-/Newton-Verfahrens für \(\sqrt{n}\). Statt des reellen Quotienten \(n/x\) wird zuerst nach oben gerundet und dann mit dem aktuellen Wert gemittelt.
Für festes \(n\) definiert man die Schrittzahl rekursiv durch
$$\tau(n,x)= \begin{cases} 1,& y(n,x)=x,\\ 1+\tau(n,y(n,x)),& y(n,x)\ne x. \end{cases}$$
Die führende \(1\) zählt den aktuellen Update-Schritt immer mit.
Die Stoppbedingung ist
$$\left\lfloor\frac{x+\left\lceil n/x\right\rceil}{2}\right\rfloor=x.$$
Da \(x+\lceil n/x\rceil\) ganzzahlig ist, ist das äquivalent zu
$$2x\le x+\left\lceil\frac{n}{x}\right\rceil \le 2x+1,$$
also zu
$$x\le \left\lceil\frac{n}{x}\right\rceil \le x+1.$$
Zurück in \(n\) übersetzt erhält man das exakte Stabilitätsband
$$x(x-1) < n \le x(x+1).$$
Alle ganzen Zahlen in
$$[x(x-1)+1,\;x(x+1)]$$
stoppen also sofort, wenn der aktuelle Schätzwert \(x\) ist. Genau das nutzt der Code: Für Teilintervalle mit \(y=x\) wird nicht weiter rekursiert.
Der Startwert hängt nur von \(d\) ab:
$$x_0= \begin{cases} 2\cdot 10^{(d-1)/2},& d\text{ ungerade},\\ 7\cdot 10^{(d-2)/2},& d\text{ gerade}. \end{cases}$$
Das ist plausibel, weil alle Quadratwurzeln \(d\)-stelliger Zahlen in einem festen Dezimalband liegen.
Für \(d=2k+1\) gilt
$$10^k \le \sqrt{n} < \sqrt{10}\,10^k,$$
also ist \(2\cdot 10^k\) ein sinnvoller mittlerer Startwert.
Für \(d=2k\) gilt
$$\sqrt{10}\,10^{k-1} \le \sqrt{n} < 10^k,$$
und \(7\cdot 10^{k-1}\) liegt bequem in diesem Bereich.
Statt jede Zahl einzeln zu behandeln, bearbeitet der Code ein ganzes Intervall \([L,H]\), das aktuell denselben Schätzwert \(x\) besitzt. Definiere
$$T([L,H],x)=\sum_{n=L}^{H}\tau(n,x).$$
Jede Zahl trägt für den aktuellen Schritt mindestens \(1\) bei, also
$$T([L,H],x)=|[L,H]|+\sum_{n=L}^{H}\mathbf{1}_{y(n,x)\ne x}\,\tau(n,y(n,x)).$$
Fasst man alle \(n\) mit demselben nächsten Wert \(y\) zusammen, entsteht die Intervallrekursion
$$T([L,H],x)=|[L,H]|+\sum_{y\ne x}T(I_y,y),$$
wobei \(I_y\subseteq [L,H]\) die Menge aller Zahlen ist, die im nächsten Schritt nach \(y\) gehen.
Die Größe
$$c(n,x)=\left\lceil\frac{n}{x}\right\rceil$$
ist in \(n\) stückweise konstant. Für festes \(c\) ist \(\lceil n/x\rceil=c\) äquivalent zu
$$ (c-1)x < n \le cx,$$
also im ganzzahligen Fall zu
$$[(c-1)x+1,\;cx].$$
Auf einem solchen Block ist auch der nächste Schätzwert konstant, denn
$$y=\left\lfloor\frac{x+c}{2}\right\rfloor.$$
Umgekehrt bedeutet für festes \(y\) die Gleichung
$$\left\lfloor\frac{x+c}{2}\right\rfloor=y,$$
dass \(x+c\) nur \(2y\) oder \(2y+1\) sein kann. Also sind die möglichen \(c\)-Werte
$$c=2y-x\qquad\text{oder}\qquad c=2y-x+1.$$
Genau deshalb verwendet der Code
$$cl=2y-x,\qquad ch=cl+1.$$
Nach dem Schnitt mit dem tatsächlichen Bereich \(c_{\min}\le c\le c_{\max}\) wird daraus wieder das passende \(n\)-Teilintervall.
Für \(d=2\) ist der Startwert \(x_0=7\), und der Gesamtraum ist \([10,99]\).
Hier gilt
$$c_{\min}=\left\lceil\frac{10}{7}\right\rceil=2,\qquad c_{\max}=\left\lceil\frac{99}{7}\right\rceil=15.$$
Das Intervall zerfällt nach dem nächsten Wert in:
$$[10,14]\to 4,\qquad [15,28]\to 5,\qquad [29,42]\to 6,$$
$$[43,56]\to 7,\qquad [57,70]\to 8,\qquad [71,84]\to 9,$$
$$[85,98]\to 10,\qquad [99,99]\to 11.$$
Der mittlere Block \([43,56]\) ist bereits stabil, denn er ist genau das Band
$$7\cdot 6 < n \le 7\cdot 8,$$
also \(42 < n \le 56\).
Für \(n=10\) mit Startwert \(7\) ist die Folge
$$7\to 4\to 3\to 3,$$
also beträgt die Schrittzahl \(3\).
Für \(n=24\) erhält man
$$7\to 5\to 5,$$
also \(2\) Schritte.
Für \(n=99\) ist die Folge
$$7\to 11\to 10\to 10,$$
also wieder \(3\) Schritte.
Diese Beispiele zeigen, dass die Iteration in \(x\) nicht monoton sein muss; entscheidend ist nur, dass die Intervallrekursion exakt dieselben Verzweigungen wie die Einzeliteration reproduziert.
Die C++-Datei enthält einen Checkpoint für 5-stellige Zahlen:
$$A_5=3.2102888889\ldots$$
Genauer wird geprüft, dass der Mittelwert strikt zwischen
$$3.2102888888 \quad\text{und}\quad 3.2102888890$$
liegt. Das ist ein nützlicher Test, bevor der 14-stellige Fall berechnet wird.
Die Hilfsfunktion ceil_div berechnet \(\lceil a/b\rceil\). Die rekursive Routine total_iterations(lo, hi, x) liefert \(T([lo,hi],x)\): Zuerst addiert sie die Intervallgröße \((hi-lo+1)\) für den aktuellen Schritt, bestimmt dann alle möglichen nächsten Werte \(y\), konstruiert für jedes \(y\) das passende \(n\)-Teilintervall und rekursiert nur dann weiter, wenn \(y\ne x\). Die Hülle average_iterations_for_digits(d) baut den \(d\)-stelligen Bereich auf, wählt \(x_0\) und teilt durch die Anzahl der \(d\)-stelligen Zahlen, also
$$9\cdot 10^{d-1}.$$
Der naive Ansatz müsste alle \(9\cdot 10^{d-1}\) Zahlen separat untersuchen. Die Intervallmethode besucht stattdessen nur die Teilintervalle, die durch die Abbildung \(n\mapsto y(n,x)\) tatsächlich entstehen. Jeder rekursive Aufruf zerlegt sein Intervall in wenige disjunkte Kinder. Die Laufzeit wird daher von der Zahl der tatsächlich auftretenden Intervall/Schätzwert-Paare bestimmt und ist dramatisch kleiner als beim Vollscan.
Der Speicherbedarf besteht nur aus dem Rekursionsstack; große Tabellen werden nicht benötigt.
Her \(d\) basamaklı \(n\) sayısı için problemde tanımlanan yuvarlanmış karekök iterasyonu, yalnızca \(d\)'ye bağlı bir başlangıç tahmini \(x_0\) ile başlatılır. Amaç, tahmin artık değişmeyene kadar kaç adım geçtiğini saymak ve bu sayıyı tüm \(d\) basamaklı sayılar üzerinde ortalamaktır.
Mevcut tahmin \(x\) iken bir sonraki tahmin
$$c(n,x)=\left\lceil\frac{n}{x}\right\rceil,\qquad y(n,x)=\left\lfloor\frac{x+c(n,x)}{2}\right\rfloor$$
ile tanımlanır. Süreç \(y(n,x)=x\) olduğunda durur. Her \(n\) için bunu ayrı ayrı çalıştırmak imkansız derecede pahalı olduğundan, kod aynı sonraki değere giden sayıları aralıklar halinde topluca işler.
Şu dönüşüm
$$x\longmapsto \left\lfloor\frac{x+\left\lceil n/x\right\rceil}{2}\right\rfloor$$
\(\sqrt{n}\) için Heron / Newton yönteminin tamsayılı bir sürümüdür. Reel Newton adımındaki \(n/x\) burada önce tavana yuvarlanır, sonra mevcut tahminle ortalanır.
Sabit bir \(n\) için adım sayısını
$$\tau(n,x)= \begin{cases} 1,& y(n,x)=x,\\ 1+\tau(n,y(n,x)),& y(n,x)\ne x \end{cases}$$
şeklinde tanımlayabiliriz. Baştaki \(1\), mevcut güncellemenin her zaman bir adım sayıldığını ifade eder.
Durma koşulu
$$\left\lfloor\frac{x+\left\lceil n/x\right\rceil}{2}\right\rfloor=x$$
olduğuna göre ve \(x+\lceil n/x\rceil\) bir tamsayı olduğundan bu koşul
$$2x\le x+\left\lceil\frac{n}{x}\right\rceil \le 2x+1$$
ile, yani
$$x\le \left\lceil\frac{n}{x}\right\rceil \le x+1$$
ile eşdeğerdir. Bunu doğrudan \(n\) cinsinden yazarsak tam sabitlenme bandını elde ederiz:
$$x(x-1) < n \le x(x+1).$$
Yani
$$[x(x-1)+1,\;x(x+1)]$$
aralığındaki tüm tamsayılar, mevcut tahmin \(x\) iken bir sonraki adımda artık değişmez. Kod bunu dolaylı olarak kullanır: bir alt aralık için \(y=x\) çıkarsa o dalda özyineleme durur.
Başlangıç tahmini yalnızca \(d\)'ye bağlıdır:
$$x_0= \begin{cases} 2\cdot 10^{(d-1)/2},& d\text{ tek},\\ 7\cdot 10^{(d-2)/2},& d\text{ çift}. \end{cases}$$
Bunun nedeni, \(d\) basamaklı sayıların kareköklerinin tek bir onluk büyüklük bandında yer almasıdır.
Eğer \(d=2k+1\) ise
$$10^k \le \sqrt{n} < \sqrt{10}\,10^k,$$
dolayısıyla \(2\cdot 10^k\) doğal bir ilk tahmindir.
Eğer \(d=2k\) ise
$$\sqrt{10}\,10^{k-1} \le \sqrt{n} < 10^k,$$
ve \(7\cdot 10^{k-1}\) bu aralığın içinde rahat bir merkez tahmindir.
Kod sayıları tek tek değil, mevcut tahmini aynı olan bir \([L,H]\) aralığı üzerinde topluca işler. Şöyle tanımlayalım:
$$T([L,H],x)=\sum_{n=L}^{H}\tau(n,x).$$
Her sayı mevcut güncelleme için en az bir adım verdiğinden
$$T([L,H],x)=|[L,H]|+\sum_{n=L}^{H}\mathbf{1}_{y(n,x)\ne x}\,\tau(n,y(n,x))$$
olur. Aynı sonraki değere giden sayıları gruplayınca aralık özyinelemesi çıkar:
$$T([L,H],x)=|[L,H]|+\sum_{y\ne x}T(I_y,y),$$
burada \(I_y\subseteq[L,H]\), bir sonraki adımda tam olarak \(y\)'ye giden sayılardır.
$$c(n,x)=\left\lceil\frac{n}{x}\right\rceil$$ \(n\)'ye göre parça parça sabittir. Sabit bir \(c\) için \(\lceil n/x\rceil=c\) koşulu
$$ (c-1)x < n \le cx$$
ile eşdeğerdir; tamsayı aralığı olarak bu
$$[(c-1)x+1,\;cx]$$
demektir. Bu blok içinde bir sonraki tahmin de sabittir, çünkü
$$y=\left\lfloor\frac{x+c}{2}\right\rfloor.$$
Ters yönden bakarsak, sabit bir \(y\) için
$$\left\lfloor\frac{x+c}{2}\right\rfloor=y$$
eşitliği \(x+c\)'nin yalnızca \(2y\) veya \(2y+1\) olabileceğini söyler. Bu yüzden mümkün \(c\) değerleri
$$c=2y-x\qquad\text{veya}\qquad c=2y-x+1$$
olur. Koddaki
$$cl=2y-x,\qquad ch=cl+1$$
satırlarının sebebi tam olarak budur. Sonra bunlar gerçek \(c_{\min}\) ve \(c_{\max}\) aralığıyla kesiştirilip tekrar uygun \(n\)-aralığına çevrilir.
\(d=2\) için başlangıç tahmini \(x_0=7\), tüm aralık ise \([10,99]\)'dur.
Burada
$$c_{\min}=\left\lceil\frac{10}{7}\right\rceil=2,\qquad c_{\max}=\left\lceil\frac{99}{7}\right\rceil=15$$
olur. Buna göre aralık şu şekilde bölünür:
$$[10,14]\to 4,\qquad [15,28]\to 5,\qquad [29,42]\to 6,$$
$$[43,56]\to 7,\qquad [57,70]\to 8,\qquad [71,84]\to 9,$$
$$[85,98]\to 10,\qquad [99,99]\to 11.$$
Ortadaki \([43,56]\) bloğu zaten sabittir; çünkü bu blok tam olarak
$$7\cdot 6 < n \le 7\cdot 8,$$
yani \(42 < n \le 56\) bandıdır.
\(n=10\) için başlangıç \(7\) ile dizi
$$7\to 4\to 3\to 3$$
olur; dolayısıyla adım sayısı \(3\)'tür.
\(n=24\) için
$$7\to 5\to 5$$
elde edilir; yani \(2\) adım gerekir.
\(n=99\) için ise
$$7\to 11\to 10\to 10$$
olur; yine \(3\) adım vardır.
Bu örnekler, iterasyonun \(x\) bakımından her zaman tek yönlü olmadığını gösterir. Önemli olan, aralık özyinelemesinin tek tek simülasyonla aynı dallanmayı tam olarak üretmesidir.
C++ dosyasında 5 basamaklı sayılar için bir kontrol vardır:
$$A_5=3.2102888889\ldots$$
Daha kesin olarak, ortalamanın şu aralıkta olduğu doğrulanır:
$$3.2102888888 \quad\text{ile}\quad 3.2102888890.$$
Bu, 14 basamaklı asıl hesap öncesinde iyi bir sağlamlık testidir.
ceil_div fonksiyonu \(\lceil a/b\rceil\) hesaplar. Özyinelemeli total_iterations(lo, hi, x) fonksiyonu \(T([lo,hi],x)\) değerini döndürür: önce \((hi-lo+1)\) kadar mevcut adım katkısını ekler, sonra mümkün tüm \(y\) değerlerini bulur, her \(y\) için ilgili \(n\)-alt aralığını kurar ve yalnızca \(y\ne x\) ise özyinelemeye devam eder. Dış sarmalayıcı average_iterations_for_digits(d) ise \(d\) basamaklı aralığı kurar, doğru \(x_0\)'ı seçer ve sonucu
$$9\cdot 10^{d-1}$$
sayısına böler.
Naif yöntem \(9\cdot 10^{d-1}\) sayının her birini ayrı ayrı işlerdi. Aralık yöntemi ise yalnızca \(n\mapsto y(n,x)\) dönüşümünün gerçekten ürettiği alt aralıkları ziyaret eder. Her özyinelemeli çağrı aralığını az sayıda ayrık çocuğa böler. Bu yüzden çalışma süresi, ortaya çıkan gerçek aralık/tahmin durumlarının sayısına bağlıdır ve tüm giriş uzayını tek tek taramaktan çok daha küçüktür.
Bellek kullanımı yalnızca özyineleme yığını kadardır; büyük bir tablo tutulmaz.
Para cada entero \(n\) de \(d\) cifras, el problema aplica una iteración redondeada de raíz cuadrada a partir de una estimación inicial \(x_0\) que depende solo de \(d\). Debemos contar cuántos pasos hacen falta hasta que la estimación deje de cambiar y promediar ese valor sobre todos los números de \(d\) cifras.
Con estimación actual \(x\), el siguiente valor es
$$c(n,x)=\left\lceil\frac{n}{x}\right\rceil,\qquad y(n,x)=\left\lfloor\frac{x+c(n,x)}{2}\right\rfloor.$$
El proceso termina cuando \(y(n,x)=x\). En lugar de simular todos los \(n\) por separado, el código agrupa en intervalos los números que comparten el mismo siguiente valor.
La transformación
$$x\longmapsto \left\lfloor\frac{x+\left\lceil n/x\right\rceil}{2}\right\rfloor$$
es una versión entera del método de Herón / Newton para \(\sqrt{n}\). En vez de usar el cociente real \(n/x\), primero se redondea hacia arriba y luego se promedia con la estimación actual.
Para \(n\) fijo, definimos el número de iteraciones mediante
$$\tau(n,x)= \begin{cases} 1,& y(n,x)=x,\\ 1+\tau(n,y(n,x)),& y(n,x)\ne x. \end{cases}$$
Ese \(1\) inicial significa que el paso actual siempre cuenta.
La condición de parada
$$\left\lfloor\frac{x+\left\lceil n/x\right\rceil}{2}\right\rfloor=x$$
equivale a
$$2x\le x+\left\lceil\frac{n}{x}\right\rceil \le 2x+1,$$
y por tanto a
$$x\le \left\lceil\frac{n}{x}\right\rceil \le x+1.$$
Traducido a \(n\), esto da la banda exacta
$$x(x-1) < n \le x(x+1).$$
Por consiguiente, todos los enteros en
$$[x(x-1)+1,\;x(x+1)]$$
ya son estables cuando la estimación actual es \(x\).
El valor inicial viene dado por
$$x_0= \begin{cases} 2\cdot 10^{(d-1)/2},& d\text{ impar},\\ 7\cdot 10^{(d-2)/2},& d\text{ par}. \end{cases}$$
Esto tiene sentido porque las raíces cuadradas de los números de \(d\) cifras viven en una banda decimal concreta.
Si \(d=2k+1\), entonces
$$10^k \le \sqrt{n} < \sqrt{10}\,10^k,$$
y \(2\cdot 10^k\) es una estimación central razonable.
Si \(d=2k\), entonces
$$\sqrt{10}\,10^{k-1} \le \sqrt{n} < 10^k,$$
y \(7\cdot 10^{k-1}\) cae cómodamente dentro de ese intervalo.
En lugar de trabajar con un único \(n\), el código procesa un intervalo completo \([L,H]\) que comparte la misma estimación actual \(x\). Definimos
$$T([L,H],x)=\sum_{n=L}^{H}\tau(n,x).$$
Cada número aporta al menos una iteración por la actualización actual, así que
$$T([L,H],x)=|[L,H]|+\sum_{n=L}^{H}\mathbf{1}_{y(n,x)\ne x}\,\tau(n,y(n,x)).$$
Agrupando por el mismo siguiente valor \(y\), se obtiene
$$T([L,H],x)=|[L,H]|+\sum_{y\ne x}T(I_y,y),$$
donde \(I_y\subseteq[L,H]\) es el subconjunto que pasa a \(y\) en el siguiente paso.
La cantidad
$$c(n,x)=\left\lceil\frac{n}{x}\right\rceil$$
es constante por tramos. Para un \(c\) fijo, la condición \(\lceil n/x\rceil=c\) equivale a
$$ (c-1)x < n \le cx,$$
es decir, sobre enteros, al intervalo
$$[(c-1)x+1,\;cx].$$
En ese bloque, el siguiente valor es constante porque
$$y=\left\lfloor\frac{x+c}{2}\right\rfloor.$$
Si fijamos \(y\), entonces
$$\left\lfloor\frac{x+c}{2}\right\rfloor=y$$
implica que \(x+c\) solo puede ser \(2y\) o \(2y+1\). Por eso los únicos valores posibles de \(c\) son
$$c=2y-x\qquad\text{o}\qquad c=2y-x+1.$$
Para \(d=2\), se toma \(x_0=7\) y el dominio completo es \([10,99]\).
Aquí
$$c_{\min}=\left\lceil\frac{10}{7}\right\rceil=2,\qquad c_{\max}=\left\lceil\frac{99}{7}\right\rceil=15.$$
La partición por siguiente valor es
$$[10,14]\to 4,\qquad [15,28]\to 5,\qquad [29,42]\to 6,$$
$$[43,56]\to 7,\qquad [57,70]\to 8,\qquad [71,84]\to 9,$$
$$[85,98]\to 10,\qquad [99,99]\to 11.$$
El bloque \([43,56]\) ya es estable, porque coincide exactamente con la banda
$$7\cdot 6 < n \le 7\cdot 8.$$
Para \(n=10\), la secuencia es
$$7\to 4\to 3\to 3,$$
así que el número de iteraciones es \(3\).
Para \(n=24\), se obtiene
$$7\to 5\to 5,$$
y por tanto hay \(2\) iteraciones.
Para \(n=99\), la secuencia es
$$7\to 11\to 10\to 10,$$
de nuevo con \(3\) pasos.
El archivo C++ incluye una comprobación para números de 5 cifras:
$$A_5=3.2102888889\ldots$$
En concreto, se verifica que el promedio está estrictamente entre
$$3.2102888888 \quad\text{y}\quad 3.2102888890.$$
La función auxiliar ceil_div calcula \(\lceil a/b\rceil\). La rutina recursiva total_iterations(lo, hi, x) devuelve \(T([lo,hi],x)\): suma primero el tamaño del intervalo por el paso actual, luego determina los posibles valores siguientes \(y\), construye para cada uno el subintervalo correspondiente de \(n\), y solo recurre cuando \(y\ne x\). La función average_iterations_for_digits(d) genera el dominio de \(d\) cifras, escoge \(x_0\) y divide entre
$$9\cdot 10^{d-1}.$$
El método ingenuo inspeccionaría los \(9\cdot 10^{d-1}\) valores de \(n\) uno por uno. El método por intervalos visita solo los subintervalos realmente generados por la aplicación \(n\mapsto y(n,x)\). Cada llamada recursiva divide su intervalo en pocos hijos disjuntos, así que el coste depende del número real de pares intervalo/estimación que aparecen, mucho menor que el tamaño del rango completo.
对每一个 \(d\) 位整数 \(n\)，题目都会从一个只依赖于位数 \(d\) 的初始猜测 \(x_0\) 出发，执行“取整版平方根迭代”。我们要统计这个迭代在估计值不再变化之前一共执行了多少步，并对所有 \(d\) 位数取平均。
当前估计为 \(x\) 时，下一步定义为
$$c(n,x)=\left\lceil\frac{n}{x}\right\rceil,\qquad y(n,x)=\left\lfloor\frac{x+c(n,x)}{2}\right\rfloor.$$
当 \(y(n,x)=x\) 时过程停止。暴力方法会对每个 \(n\) 单独模拟，但代码真正做的是把“下一步相同”的 \(n\) 整体打包成区间来处理。
映射
$$x\longmapsto \left\lfloor\frac{x+\left\lceil n/x\right\rceil}{2}\right\rfloor$$
是 \(\sqrt{n}\) 的 Heron / Newton 方法的整数化版本。真实的 Newton 步会用到 \(n/x\)；这里先把它向上取整，再与当前估计做平均。
对固定的 \(n\)，可以把步数递归地定义为
$$\tau(n,x)= \begin{cases} 1,& y(n,x)=x,\\ 1+\tau(n,y(n,x)),& y(n,x)\ne x. \end{cases}$$
前面的 \(1\) 表示当前这次更新永远算作一步。
停止条件
$$\left\lfloor\frac{x+\left\lceil n/x\right\rceil}{2}\right\rfloor=x$$
由于 \(x+\lceil n/x\rceil\) 是整数，等价于
$$2x\le x+\left\lceil\frac{n}{x}\right\rceil \le 2x+1,$$
也就是
$$x\le \left\lceil\frac{n}{x}\right\rceil \le x+1.$$
把它改写成关于 \(n\) 的条件，可得精确稳定带
$$x(x-1) < n \le x(x+1).$$
因此，对当前估计 \(x\) 来说，所有位于
$$[x(x-1)+1,\;x(x+1)]$$
中的整数都会在这一步后立刻稳定下来。
初始猜测只由 \(d\) 决定：
$$x_0= \begin{cases} 2\cdot 10^{(d-1)/2},& d\text{ 为奇数},\\ 7\cdot 10^{(d-2)/2},& d\text{ 为偶数}. \end{cases}$$
这是合理的，因为所有 \(d\) 位数的平方根都落在同一个数量级区间中。
若 \(d=2k+1\)，则
$$10^k \le \sqrt{n} < \sqrt{10}\,10^k,$$
所以 \(2\cdot 10^k\) 是自然的中心估计。
若 \(d=2k\)，则
$$\sqrt{10}\,10^{k-1} \le \sqrt{n} < 10^k,$$
而 \(7\cdot 10^{k-1}\) 很舒服地落在这个范围里。
代码并不是一次处理一个 \(n\)，而是处理一个当前估计都相同的区间 \([L,H]\)。定义
$$T([L,H],x)=\sum_{n=L}^{H}\tau(n,x).$$
因为区间中的每个数在当前层至少贡献一步，所以
$$T([L,H],x)=|[L,H]|+\sum_{n=L}^{H}\mathbf{1}_{y(n,x)\ne x}\,\tau(n,y(n,x)).$$
把下一步相同的 \(n\) 合并起来，就得到区间递归
$$T([L,H],x)=|[L,H]|+\sum_{y\ne x}T(I_y,y),$$
其中 \(I_y\subseteq[L,H]\) 表示下一步恰好变成 \(y\) 的那一段数。
量
$$c(n,x)=\left\lceil\frac{n}{x}\right\rceil$$
关于 \(n\) 是分段常值的。对固定的整数 \(c\)，条件 \(\lceil n/x\rceil=c\) 等价于
$$ (c-1)x < n \le cx,$$
在整数范围内就是
$$[(c-1)x+1,\;cx].$$
在这一整段上，下一次迭代值都是常数，因为
$$y=\left\lfloor\frac{x+c}{2}\right\rfloor.$$
反过来，若固定 \(y\)，则
$$\left\lfloor\frac{x+c}{2}\right\rfloor=y$$
意味着 \(x+c\) 只能等于 \(2y\) 或 \(2y+1\)。所以可能的 \(c\) 只有两个：
$$c=2y-x\qquad\text{或}\qquad c=2y-x+1.$$
这正是代码里
$$cl=2y-x,\qquad ch=cl+1$$
的来源。
当 \(d=2\) 时，初始值 \(x_0=7\)，整个定义域是 \([10,99]\)。
这时
$$c_{\min}=\left\lceil\frac{10}{7}\right\rceil=2,\qquad c_{\max}=\left\lceil\frac{99}{7}\right\rceil=15.$$
按下一步值划分后得到
$$[10,14]\to 4,\qquad [15,28]\to 5,\qquad [29,42]\to 6,$$
$$[43,56]\to 7,\qquad [57,70]\to 8,\qquad [71,84]\to 9,$$
$$[85,98]\to 10,\qquad [99,99]\to 11.$$
其中 \([43,56]\) 已经稳定，因为它正好就是
$$7\cdot 6 < n \le 7\cdot 8$$
这条稳定带。
对 \(n=10\)，序列为
$$7\to 4\to 3\to 3,$$
所以共 \(3\) 步。
对 \(n=24\)，序列为
$$7\to 5\to 5,$$
所以共 \(2\) 步。
对 \(n=99\)，序列为
$$7\to 11\to 10\to 10,$$
仍然是 \(3\) 步。
这说明迭代值 \(x\) 本身不一定单调，但区间递归与逐个模拟的分支完全一致。
C++ 文件中包含一个对 5 位数平均值的检查：
$$A_5=3.2102888889\ldots$$
更准确地说，代码断言该平均值严格落在
$$3.2102888888 \quad\text{和}\quad 3.2102888890$$
之间。
ceil_div 用来计算 \(\lceil a/b\rceil\)。递归函数 total_iterations(lo, hi, x) 返回 \(T([lo,hi],x)\)：先把区间长度 \((hi-lo+1)\) 作为当前层贡献加入，然后枚举所有可能的下一值 \(y\)，构造对应的 \(n\) 子区间，并仅在 \(y\ne x\) 时继续递归。外层函数 average_iterations_for_digits(d) 负责生成 \(d\) 位数区间、选择 \(x_0\)，并最后除以
$$9\cdot 10^{d-1}.$$
朴素方法需要对 \(9\cdot 10^{d-1}\) 个整数逐一模拟。区间方法只访问由映射 \(n\mapsto y(n,x)\) 实际产生的那些子区间。每个递归调用只会把当前区间拆成少数几个互不重叠的子区间，因此实际复杂度由真实出现的“区间 + 当前估计”状态数决定，远小于暴力法。
Для каждого \(d\)-значного числа \(n\) задача запускает округлённую итерацию для квадратного корня, начиная с начального приближения \(x_0\), зависящего только от числа цифр. Нужно посчитать, сколько шагов требуется до стабилизации, а затем усреднить это значение по всем \(d\)-значным числам.
При текущем приближении \(x\) следующий шаг задаётся формулами
$$c(n,x)=\left\lceil\frac{n}{x}\right\rceil,\qquad y(n,x)=\left\lfloor\frac{x+c(n,x)}{2}\right\rfloor.$$
Процесс останавливается, когда \(y(n,x)=x\). Вместо покомпонентной симуляции код объединяет числа в интервалы, для которых следующий шаг одинаков.
Преобразование
$$x\longmapsto \left\lfloor\frac{x+\left\lceil n/x\right\rceil}{2}\right\rfloor$$
является целочисленной версией метода Герона / Ньютона для \(\sqrt{n}\). В обычном методе используется вещественное \(n/x\); здесь оно сначала округляется вверх, а затем усредняется с текущим значением.
Для фиксированного \(n\) число шагов можно задать рекурсивно:
$$\tau(n,x)= \begin{cases} 1,& y(n,x)=x,\\ 1+\tau(n,y(n,x)),& y(n,x)\ne x. \end{cases}$$
Первая единица означает, что текущее применение правила всегда считается одним шагом.
Условие остановки
$$\left\lfloor\frac{x+\left\lceil n/x\right\rceil}{2}\right\rfloor=x$$
эквивалентно
$$2x\le x+\left\lceil\frac{n}{x}\right\rceil \le 2x+1,$$
то есть
$$x\le \left\lceil\frac{n}{x}\right\rceil \le x+1.$$
Переписывая это через \(n\), получаем точную полосу стабилизации:
$$x(x-1) < n \le x(x+1).$$
Следовательно, все целые числа из интервала
$$[x(x-1)+1,\;x(x+1)]$$
уже стабилизируются при текущем \(x\).
Стартовое значение зависит только от \(d\):
$$x_0= \begin{cases} 2\cdot 10^{(d-1)/2},& d\text{ нечётно},\\ 7\cdot 10^{(d-2)/2},& d\text{ чётно}. \end{cases}$$
Это естественно, потому что квадратные корни всех \(d\)-значных чисел лежат в одной десятичной полосе.
Если \(d=2k+1\), то
$$10^k \le \sqrt{n} < \sqrt{10}\,10^k,$$
поэтому \(2\cdot 10^k\) — разумная центральная оценка.
Если \(d=2k\), то
$$\sqrt{10}\,10^{k-1} \le \sqrt{n} < 10^k,$$
и \(7\cdot 10^{k-1}\) хорошо попадает внутрь этого диапазона.
Код работает не с одним числом, а с целым интервалом \([L,H]\), у которого текущее приближение одинаково и равно \(x\). Введём
$$T([L,H],x)=\sum_{n=L}^{H}\tau(n,x).$$
Каждое число вносит хотя бы один шаг на текущем уровне, поэтому
$$T([L,H],x)=|[L,H]|+\sum_{n=L}^{H}\mathbf{1}_{y(n,x)\ne x}\,\tau(n,y(n,x)).$$
Если сгруппировать числа с одинаковым следующим значением \(y\), получаем рекурсию по интервалам:
$$T([L,H],x)=|[L,H]|+\sum_{y\ne x}T(I_y,y),$$
где \(I_y\subseteq [L,H]\) — множество чисел, переходящих на следующем шаге в \(y\).
Величина
$$c(n,x)=\left\lceil\frac{n}{x}\right\rceil$$
постоянна на кусках по \(n\). Для фиксированного \(c\) условие \(\lceil n/x\rceil=c\) равносильно
$$ (c-1)x < n \le cx,$$
то есть на целых числах даёт интервал
$$[(c-1)x+1,\;cx].$$
На этом блоке следующий шаг тоже постоянен, поскольку
$$y=\left\lfloor\frac{x+c}{2}\right\rfloor.$$
Если зафиксировать \(y\), то равенство
$$\left\lfloor\frac{x+c}{2}\right\rfloor=y$$
означает, что \(x+c\) может быть только \(2y\) или \(2y+1\). Поэтому возможны лишь два значения \(c\):
$$c=2y-x\qquad\text{или}\qquad c=2y-x+1.$$
При \(d=2\) берётся \(x_0=7\), а полный диапазон равен \([10,99]\).
Здесь
$$c_{\min}=\left\lceil\frac{10}{7}\right\rceil=2,\qquad c_{\max}=\left\lceil\frac{99}{7}\right\rceil=15.$$
Разбиение по следующему значению выглядит так:
$$[10,14]\to 4,\qquad [15,28]\to 5,\qquad [29,42]\to 6,$$
$$[43,56]\to 7,\qquad [57,70]\to 8,\qquad [71,84]\to 9,$$
$$[85,98]\to 10,\qquad [99,99]\to 11.$$
Блок \([43,56]\) уже стабилен, поскольку это в точности полоса
$$7\cdot 6 < n \le 7\cdot 8.$$
Для \(n=10\) получаем последовательность
$$7\to 4\to 3\to 3,$$
то есть \(3\) шага.
Для \(n=24\) имеем
$$7\to 5\to 5,$$
то есть \(2\) шага.
Для \(n=99\) последовательность
$$7\to 11\to 10\to 10$$
снова даёт \(3\) шага.
В C++-файле есть checkpoint для 5-значного случая:
$$A_5=3.2102888889\ldots$$
Точнее, код проверяет, что среднее значение строго лежит между
$$3.2102888888 \quad\text{и}\quad 3.2102888890.$$
Вспомогательная функция ceil_div вычисляет \(\lceil a/b\rceil\). Рекурсивная процедура total_iterations(lo, hi, x) возвращает \(T([lo,hi],x)\): сначала она добавляет размер интервала \((hi-lo+1)\) как вклад текущего шага, затем перебирает все возможные следующие значения \(y\), строит соответствующий подынтервал по \(n\) и рекурсивно идёт дальше только если \(y\ne x\). Обёртка average_iterations_for_digits(d) строит диапазон \(d\)-значных чисел, выбирает \(x_0\) и делит итог на
$$9\cdot 10^{d-1}.$$
Наивный подход обрабатывал бы все \(9\cdot 10^{d-1}\) чисел по отдельности. Интервальный подход посещает только те подынтервалы, которые реально возникают под действием отображения \(n\mapsto y(n,x)\). Каждый рекурсивный вызов делит интервал на небольшое число непересекающихся потомков, поэтому время определяется числом реально возникших пар «интервал + текущее приближение», а не полным размером входного диапазона.
لكل عدد صحيح \(n\) مكوَّن من \(d\) خانات، تطبق المسألة تكرارًا مقربًا للجذر التربيعي يبدأ من تخمين ابتدائي \(x_0\) يعتمد فقط على عدد الخانات \(d\). المطلوب هو عدد الخطوات اللازمة حتى يتوقف التخمين عن التغير، ثم أخذ المتوسط على جميع الأعداد ذات \(d\) خانات.
إذا كان التخمين الحالي هو \(x\)، فإن التخمين التالي يُعطى بـ
$$c(n,x)=\left\lceil\frac{n}{x}\right\rceil,\qquad y(n,x)=\left\lfloor\frac{x+c(n,x)}{2}\right\rfloor.$$
تتوقف العملية عندما \(y(n,x)=x\). وبدل تشغيل هذه العملية على كل \(n\) منفردًا، يجمع الكود الأعداد في مجالات لها القيمة التالية نفسها.
التحويل
$$x\longmapsto \left\lfloor\frac{x+\left\lceil n/x\right\rceil}{2}\right\rfloor$$
هو نسخة صحيحة من طريقة Heron / Newton لحساب \(\sqrt{n}\). ففي الطريقة الحقيقية نستعمل \(n/x\)، أما هنا فيتم أولًا تقريب هذا الكسر إلى الأعلى ثم يؤخذ متوسطه مع التخمين الحالي.
ولعدد ثابت \(n\)، يمكن تعريف عدد الخطوات على الصورة
$$\tau(n,x)= \begin{cases} 1,& y(n,x)=x,\\ 1+\tau(n,y(n,x)),& y(n,x)\ne x. \end{cases}$$
والعدد \(1\) في البداية يعني أن تطبيق التحديث الحالي يُحسب دائمًا كخطوة واحدة.
شرط التوقف
$$\left\lfloor\frac{x+\left\lceil n/x\right\rceil}{2}\right\rfloor=x$$
يكافئ
$$2x\le x+\left\lceil\frac{n}{x}\right\rceil \le 2x+1,$$
أي
$$x\le \left\lceil\frac{n}{x}\right\rceil \le x+1.$$
وبإعادة كتابة ذلك بدلالة \(n\)، نحصل على مجال الثبات الدقيق:
$$x(x-1) < n \le x(x+1).$$
إذن جميع الأعداد الصحيحة في المجال
$$[x(x-1)+1,\;x(x+1)]$$
تتوقف مباشرة عندما يكون التخمين الحالي هو \(x\).
قيمة البداية تعتمد فقط على \(d\):
$$x_0= \begin{cases} 2\cdot 10^{(d-1)/2},& d\text{ فردي},\\ 7\cdot 10^{(d-2)/2},& d\text{ زوجي}. \end{cases}$$
وهذا منطقي لأن الجذور التربيعية لجميع الأعداد ذات \(d\) خانات تقع داخل حزمة عشرية واحدة.
إذا كان \(d=2k+1\)، فإن
$$10^k \le \sqrt{n} < \sqrt{10}\,10^k,$$
ومن ثم يكون \(2\cdot 10^k\) تخمينًا أوليًا طبيعيًا.
أما إذا كان \(d=2k\)، فإن
$$\sqrt{10}\,10^{k-1} \le \sqrt{n} < 10^k,$$
ويكون \(7\cdot 10^{k-1}\) داخل هذا المجال بشكل مريح.
بدلًا من معالجة كل عدد بمفرده، يعالج الكود مجالًا كاملًا \([L,H]\) يشترك في التخمين الحالي نفسه \(x\). نعرّف
$$T([L,H],x)=\sum_{n=L}^{H}\tau(n,x).$$
وبما أن كل عدد يضيف خطوة واحدة على الأقل عند المستوى الحالي، فإن
$$T([L,H],x)=|[L,H]|+\sum_{n=L}^{H}\mathbf{1}_{y(n,x)\ne x}\,\tau(n,y(n,x)).$$
وعند تجميع الأعداد التي تعطي القيمة التالية نفسها \(y\)، نحصل على العلاقة
$$T([L,H],x)=|[L,H]|+\sum_{y\ne x}T(I_y,y),$$
حيث \(I_y\subseteq[L,H]\) هو المجال الفرعي الذي ينتقل في الخطوة التالية إلى \(y\).
القيمة
$$c(n,x)=\left\lceil\frac{n}{x}\right\rceil$$
ثابتة على مقاطع من \(n\). فإذا ثبتت قيمة صحيحة \(c\)، فإن الشرط \(\lceil n/x\rceil=c\) يكافئ
$$ (c-1)x < n \le cx,$$
أي على الأعداد الصحيحة
$$[(c-1)x+1,\;cx].$$
وعلى هذا الجزء تكون القيمة التالية ثابتة أيضًا، لأن
$$y=\left\lfloor\frac{x+c}{2}\right\rfloor.$$
وبالعكس، إذا ثبتت قيمة \(y\)، فإن
$$\left\lfloor\frac{x+c}{2}\right\rfloor=y$$
تعني أن \(x+c\) لا يمكن إلا أن يكون \(2y\) أو \(2y+1\). لذلك فإن القيم الممكنة لـ \(c\) هي فقط
$$c=2y-x\qquad\text{أو}\qquad c=2y-x+1.$$
عندما \(d=2\)، تكون قيمة البداية \(x_0=7\)، والمجال الكامل هو \([10,99]\).
عندها
$$c_{\min}=\left\lceil\frac{10}{7}\right\rceil=2,\qquad c_{\max}=\left\lceil\frac{99}{7}\right\rceil=15.$$
وينقسم المجال حسب القيمة التالية إلى:
$$[10,14]\to 4,\qquad [15,28]\to 5,\qquad [29,42]\to 6,$$
$$[43,56]\to 7,\qquad [57,70]\to 8,\qquad [71,84]\to 9,$$
$$[85,98]\to 10,\qquad [99,99]\to 11.$$
والمجال الأوسط \([43,56]\) ثابت أصلًا لأنه يطابق تمامًا الشريط
$$7\cdot 6 < n \le 7\cdot 8.$$
إذا كان \(n=10\)، فإن السلسلة هي
$$7\to 4\to 3\to 3,$$
إذًا عدد الخطوات \(3\).
أما إذا كان \(n=24\)، فإن السلسلة هي
$$7\to 5\to 5,$$
وبالتالي عدد الخطوات \(2\).
ولـ \(n=99\) نحصل على
$$7\to 11\to 10\to 10,$$
أي \(3\) خطوات من جديد.
يحتوي ملف C++ على نقطة تحقق للحالة ذات الخمس خانات:
$$A_5=3.2102888889\ldots$$
وبصورة أدق، يتحقق الكود من أن المتوسط يقع بين
$$3.2102888888 \quad\text{و}\quad 3.2102888890.$$
الدالة المساعدة ceil_div تحسب \(\lceil a/b\rceil\). أما الدالة العودية total_iterations(lo, hi, x) فتعيد القيمة \(T([lo,hi],x)\): فهي تضيف أولًا حجم المجال \((hi-lo+1)\) باعتباره مساهمة الخطوة الحالية، ثم تحسب القيم التالية الممكنة \(y\)، وتبني لكل منها المجال الفرعي الموافق من \(n\)، ثم تتابع عوديًا فقط إذا كان \(y\ne x\). والدالة average_iterations_for_digits(d) تبني مجال الأعداد ذات \(d\) خانات، وتختار \(x_0\)، ثم تقسم على
$$9\cdot 10^{d-1}.$$
الطريقة الساذجة ستعالج كل واحد من الأعداد \(9\cdot 10^{d-1}\) على حدة. أما طريقة المجالات فتزور فقط المجالات الفرعية التي تنشأ فعليًا من التطبيق \(n\mapsto y(n,x)\). كل استدعاء عودي يقسم المجال إلى عدد صغير من الأبناء المتباينين، لذلك يتحدد الزمن بعدد أزواج «المجال + التخمين الحالي» التي تظهر فعلًا، وهو أصغر بكثير من الحجم الكامل للمدخلات.