For a fixed digit \(d\in\{1,\dots,9\}\), let \(f_d(n)\) denote the total number of times \(d\) appears in the decimal expansions of all integers from \(0\) through \(n\). The task is to find every integer \(x\) satisfying
$$f_d(x)=x,$$
then sum all such \(x\) over \(d=1,\dots,9\).
The point \(x=0\) is trivially a fixed point for every nonzero digit, because the decimal expansion of \(0\) contains none of \(1,\dots,9\), but it contributes nothing to the final total. The real difficulty is to locate all positive fixed points without scanning an enormous search range one value at a time.
The solution rests on two ideas. First, \(f_d(n)\) can be evaluated exactly in \(O(\log_{10} n)\) time by summing independent contributions from each decimal position. Second, once \(f_d\) is known to be monotone, large intervals can be discarded using only endpoint values, so the search can proceed recursively on decimal blocks rather than on individual integers.
Let \(\nu_d(m)\) be the number of occurrences of digit \(d\) in the ordinary decimal expansion of the single integer \(m\). Then
$$f_d(n)=\sum_{m=0}^{n}\nu_d(m).$$
This immediately shows that \(f_d\) is nondecreasing, and in fact
$$f_d(n+1)-f_d(n)=\nu_d(n+1).$$
If we also write
$$g_d(n)=f_d(n)-n,$$
then the fixed-point equation is simply \(g_d(n)=0\), but
$$g_d(n+1)-g_d(n)=\nu_d(n+1)-1.$$
That difference can be negative, zero, or positive. So \(g_d\) is not monotone, which is why a direct binary search on \(g_d\) is not valid. The code therefore searches by interval elimination instead of by sign changes.
Fix one decimal position \(p=10^k\). We want the number of integers in \(0,\dots,n\) whose digit in that position equals \(d\). Set
$$N=n+1,\qquad q=\left\lfloor\frac{N}{10p}\right\rfloor,\qquad r=N\bmod(10p).$$
The first \(N\) integers split into \(q\) complete blocks of length \(10p\), plus one incomplete tail of length \(r\). In every full block, the chosen position runs through the digits \(0,\dots,9\), each repeated for exactly \(p\) consecutive numbers, so digit \(d\) contributes exactly \(p\) times per block. The full blocks therefore contribute \(qp\).
Only the tail needs casework. Inside the final block, the numbers whose \(p\)-digit equals \(d\) form a contiguous segment of length \(p\), starting after the first \(dp\) entries of that block. Hence the tail contribution is
$$\min\!\bigl(\max(r-dp,0),\,p\bigr).$$
Summing over all active decimal positions yields the exact formula used by the implementations:
$$f_d(n)=\sum_{p=1,10,100,\dots}\left(\left\lfloor\frac{n+1}{10p}\right\rfloor p+\min\!\bigl(\max((n+1)\bmod(10p)-dp,0),\,p\bigr)\right).$$
No leading-zero correction is needed here, because the problem only asks for digits \(1\) through \(9\). That detail matters: counting zeros would require a different treatment.
The identity \(f_1(12)=5\) is small enough to verify by hand and appears as a natural checkpoint for the method. From \(0\) to \(12\), the digit \(1\) appears in
$$1,\ 10,\ 11,\ 12,$$
with multiplicities \(1,1,2,1\), so the total is 5.
The positional formula reproduces the same count. For the units position \(p=1\),
$$\left\lfloor\frac{13}{10}\right\rfloor\cdot 1+\min(\max(13\bmod 10-1,0),1)=1+1=2.$$
For the tens position \(p=10\),
$$\left\lfloor\frac{13}{100}\right\rfloor\cdot 10+\min(\max(13\bmod 100-10,0),10)=0+3=3.$$
There are no higher active positions, so \(f_1(12)=2+3=5\).
Suppose a fixed point \(x\) lies in an interval \([L,R]\). Since \(f_d\) is nondecreasing,
$$f_d(L)\le f_d(x)=x\le f_d(R).$$
Because \(x\in[L,R]\), we also have
$$L\le x\le R.$$
Combining the two chains gives the necessary conditions
$$f_d(L)\le R,\qquad f_d(R)\ge L.$$
Therefore, if either
$$f_d(R)\lt L\qquad\text{or}\qquad f_d(L)\gt R,$$
then \([L,R]\) cannot contain any solution and may be discarded immediately.
A concrete example is the interval \([30,39]\) for \(d=1\). One finds \(f_1(39)=14\), and \(14\lt 30\), so the entire interval is impossible. The algorithm never needs to test 30, 31, 32, and so on individually.
The search begins with a span \(10^m\) large enough to cover the chosen limit. Any surviving interval of span \(10^m\) is split into ten children of span \(10^{m-1}\). This is not an arbitrary design choice: the counting formula itself is organized around decimal blocks, so each split reveals one more decimal digit of any possible fixed point.
When the span reaches 1, the leaf represents a single integer candidate, and the implementation performs the exact equality test \(f_d(x)=x\). In this way the recursion visits only those decimal boxes that remain compatible with the endpoint bounds.
The C++, Python, and Java implementations all follow the same high-level structure: a fast evaluator for \(f_d(n)\), followed by a recursive search over decimal intervals for each digit \(d=1,\dots,9\).
For any queried endpoint \(n\), the implementation rewrites the inclusive range \(0,\dots,n\) as a half-open interval of length \(n+1\). It then loops through the decimal positions \(1,10,100,\dots\), adds the contribution from complete blocks, adds the tail contribution from the final partial block, and returns the total. Because the loop advances by powers of ten, one evaluation uses only as many iterations as there are decimal digits.
For each digit, the implementation chooses the smallest power of ten covering the search limit and treats it as the root span. At each recursive node it evaluates \(f_d\) at the left and right endpoints, applies the pruning test above, and returns immediately when the interval is impossible. Otherwise it descends into the ten decimal children.
At unit span, the left endpoint is the unique integer candidate represented by that leaf, so the implementation checks the equality exactly and adds the value to the total when it is a fixed point. The C++ implementation also contains small checkpoint verifications, including the hand-checkable fact \(f_1(12)=5\) and a brute-force comparison on a short range; the Python and Java implementations use the same search logic without that extra validation layer.
Let \(U\) be the chosen search limit. Evaluating \(f_d(n)\) requires one pass over the decimal positions, so it takes \(O(\log U)\) time and \(O(1)\) auxiliary memory.
If \(V_d\) interval nodes survive pruning for digit \(d\), then the total time for that digit is \(O(V_d\log U)\), because each visited node performs two endpoint evaluations. The recursion depth is \(O(\log U)\), so the stack usage is also \(O(\log U)\).
In the pessimistic case, pruning could fail often enough that the search approaches a full scan, giving \(V_d=O(U)\) and hence \(O(U\log U)\) time. In practice the endpoint test eliminates most decimal intervals very early, which is why the method is effective without building any large tables.
Für eine feste Ziffer \(d\in\{1,\dots,9\}\) bezeichne \(f_d(n)\) die Gesamtzahl der Vorkommen von \(d\) in den Dezimaldarstellungen aller ganzen Zahlen von \(0\) bis \(n\). Gesucht sind also alle ganzen Zahlen \(x\) mit
$$f_d(x)=x,$$
und anschließend deren Summe über alle \(d=1,\dots,9\).
Der Wert \(x=0\) ist für jede von null verschiedene Ziffer trivial ein Fixpunkt, weil die Dezimaldarstellung von \(0\) keine der Ziffern \(1,\dots,9\) enthält; zur Endsumme trägt er jedoch nichts bei. Die eigentliche Herausforderung besteht darin, alle positiven Fixpunkte zu finden, ohne einen riesigen Bereich naiv vollständig zu durchsuchen.
Die Lösung beruht auf zwei Gedanken. Erstens lässt sich \(f_d(n)\) exakt in \(O(\log_{10} n)\) berechnen, wenn man die Beiträge der einzelnen Dezimalstellen getrennt zählt. Zweitens kann man wegen der Monotonie von \(f_d\) große Intervalle allein über ihre Randwerte ausschließen und muss deshalb nicht Zahl für Zahl testen.
Sei \(\nu_d(m)\) die Anzahl der Vorkommen der Ziffer \(d\) in der gewöhnlichen Dezimaldarstellung der einzelnen Zahl \(m\). Dann gilt
$$f_d(n)=\sum_{m=0}^{n}\nu_d(m).$$
Daraus folgt sofort, dass \(f_d\) monoton nicht fallend ist, und sogar
$$f_d(n+1)-f_d(n)=\nu_d(n+1).$$
Schreibt man zusätzlich
$$g_d(n)=f_d(n)-n,$$
so lautet die Fixpunktgleichung einfach \(g_d(n)=0\), aber
$$g_d(n+1)-g_d(n)=\nu_d(n+1)-1.$$
Dieser Unterschied kann negativ, null oder positiv sein. Deshalb ist \(g_d\) gerade nicht monoton, und eine gewöhnliche binäre Suche auf \(g_d\) wäre unzulässig. Die Implementierungen arbeiten stattdessen mit Intervallausschluss.
Fixiere eine Stelle \(p=10^k\). Gesucht ist die Anzahl der Zahlen in \(0,\dots,n\), deren Ziffer an dieser Stelle gleich \(d\) ist. Setze
$$N=n+1,\qquad q=\left\lfloor\frac{N}{10p}\right\rfloor,\qquad r=N\bmod(10p).$$
Die ersten \(N\) Zahlen zerfallen in \(q\) vollständige Blöcke der Länge \(10p\) und einen unvollständigen Restblock der Länge \(r\). In jedem vollständigen Block läuft die betrachtete Stelle durch \(0,\dots,9\), und jede Ziffer tritt dort genau \(p\)-mal auf. Die vollständigen Blöcke liefern also den Beitrag \(qp\).
Im Restblock liegt der relevante Abschnitt zusammenhängend: Die Zahlen mit Ziffer \(d\) an Stelle \(p\) beginnen nach den ersten \(dp\) Einträgen dieses Blocks und dauern höchstens \(p\) Positionen. Daher ist der Zusatzbeitrag
$$\min\!\bigl(\max(r-dp,0),\,p\bigr).$$
Über alle aktiven Stellen summiert ergibt das genau die Formel, die in den Implementierungen verwendet wird:
$$f_d(n)=\sum_{p=1,10,100,\dots}\left(\left\lfloor\frac{n+1}{10p}\right\rfloor p+\min\!\bigl(\max((n+1)\bmod(10p)-dp,0),\,p\bigr)\right).$$
Eine Korrektur für führende Nullen ist hier nicht nötig, weil die Aufgabe nur die Ziffern \(1\) bis \(9\) verlangt. Für die Ziffer \(0\) sähe die Rechnung anders aus.
Die Identität \(f_1(12)=5\) ist klein genug, um sie von Hand zu prüfen, und zugleich ein gutes Testbeispiel für die Formel. Von \(0\) bis \(12\) erscheint die Ziffer \(1\) in
$$1,\ 10,\ 11,\ 12,$$
mit den Vielfachheiten \(1,1,2,1\), also insgesamt fünfmal.
Die Stellenformel liefert dasselbe Ergebnis. Für die Einerstelle \(p=1\) erhält man
$$\left\lfloor\frac{13}{10}\right\rfloor\cdot 1+\min(\max(13\bmod 10-1,0),1)=1+1=2.$$
Für die Zehnerstelle \(p=10\) ergibt sich
$$\left\lfloor\frac{13}{100}\right\rfloor\cdot 10+\min(\max(13\bmod 100-10,0),10)=0+3=3.$$
Weitere aktive Stellen gibt es nicht, also ist \(f_1(12)=2+3=5\).
Liegt ein Fixpunkt \(x\) in einem Intervall \([L,R]\), so gilt wegen der Monotonie von \(f_d\)
$$f_d(L)\le f_d(x)=x\le f_d(R).$$
Da zugleich \(x\in[L,R]\) gilt, folgt auch
$$L\le x\le R.$$
Zusammen liefert das die notwendigen Bedingungen
$$f_d(L)\le R,\qquad f_d(R)\ge L.$$
Wenn also
$$f_d(R)\lt L\qquad\text{oder}\qquad f_d(L)\gt R,$$
dann kann das Intervall keine Lösung enthalten und wird sofort verworfen.
Ein konkretes Beispiel ist \([30,39]\) für \(d=1\). Man findet \(f_1(39)=14\), und \(14\lt 30\). Damit ist das gesamte Intervall unmöglich; keine Zahl zwischen 30 und 39 muss einzeln überprüft werden.
Die Suche beginnt mit einer Spannweite \(10^m\), die groß genug ist, um die gewählte Obergrenze abzudecken. Jedes überlebende Intervall der Länge \(10^m\) wird in zehn Kinder der Länge \(10^{m-1}\) geteilt. Das passt exakt zur Dezimalstruktur der Zählformel: Jeder Abstieg legt eine weitere Dezimalziffer möglicher Fixpunkte fest.
Sobald die Spannweite 1 erreicht, repräsentiert das Blatt genau einen ganzzahligen Kandidaten, und dann wird die Gleichung \(f_d(x)=x\) direkt geprüft. Die Rekursion besucht also nur diejenigen Dezimalboxen, die mit den Randwertschranken überhaupt noch vereinbar sind.
Die C++-, Python- und Java-Implementierungen folgen alle demselben Grundmuster: zuerst eine schnelle Auswertung von \(f_d(n)\), danach eine rekursive Suche über Dezimalintervalle für jede Ziffer \(d=1,\dots,9\).
Für einen angefragten Randwert \(n\) schreibt die Implementierung den inklusiven Bereich \(0,\dots,n\) als halboffenes Intervall der Länge \(n+1\). Anschließend läuft sie über die Stellen \(1,10,100,\dots\), addiert jeweils den Beitrag der vollständigen Blöcke und den Beitrag des letzten Teilblocks und gibt die Summe zurück. Weil die Schleife immer mit Zehnerpotenzen weitergeht, kostet eine Auswertung nur so viele Schritte wie die Zahl Dezimalstellen besitzt.
Für jede Ziffer wählt die Implementierung die kleinste Zehnerpotenz, die die Suchgrenze überdeckt, und benutzt sie als Wurzelintervall. In jedem Rekursionsknoten werden \(f_d\) am linken und rechten Rand ausgewertet, das obige Abschneidekriterium geprüft und im aussichtslosen Fall sofort zurückgekehrt. Andernfalls steigt der Algorithmus in die zehn Dezimalkinder ab.
Bei Spannweite 1 ist der linke Rand genau der eine ganzzahlige Kandidat dieses Blatts, also prüft die Implementierung die Gleichung exakt und addiert den Wert, falls er ein Fixpunkt ist. Die C++-Version enthält zusätzlich kleine Kontrolltests, darunter die von Hand prüfbare Gleichung \(f_1(12)=5\) und einen Vergleich mit einer Brute-Force-Rechnung auf einem kurzen Bereich; die Python- und Java-Versionen verwenden dieselbe Suchlogik ohne diese zusätzliche Validierungsschicht.
Sei \(U\) die gewählte Suchgrenze. Eine Auswertung von \(f_d(n)\) benötigt einen Durchlauf über die Dezimalstellen und damit \(O(\log U)\) Zeit sowie \(O(1)\) zusätzlichen Speicher.
Wenn für eine Ziffer \(d\) nach dem Abschneiden \(V_d\) Intervallknoten übrig bleiben, dann kostet die gesamte Suche für diese Ziffer \(O(V_d\log U)\), weil jeder besuchte Knoten zwei Randwertauswertungen ausführt. Die Rekursionstiefe ist \(O(\log U)\), also ist auch der Stackbedarf \(O(\log U)\).
Im ungünstigsten Fall könnte das Abschneiden so wenig helfen, dass die Suche beinahe in einen Vollscan übergeht; dann wäre \(V_d=O(U)\) und damit die Zeit \(O(U\log U)\). Praktisch eliminiert der Randwerttest jedoch sehr viele Dezimalintervalle frühzeitig, sodass keine großen Tabellen aufgebaut werden müssen.
Sabit bir \(d\in\{1,\dots,9\}\) rakamı için \(f_d(n)\), \(0\) ile \(n\) arasındaki bütün sayıların onluk yazımlarında \(d\) rakamının toplam kaç kez geçtiğini göstersin. Aranan şey,
$$f_d(x)=x$$
eşitliğini sağlayan tüm \(x\) değerlerini bulmak ve sonra bunları \(d=1,\dots,9\) için toplamaktır.
\(x=0\), sıfır dışındaki her rakam için önemsiz bir sabit noktadır; çünkü \(0\) sayısının yazımında \(1,\dots,9\) rakamları hiç görünmez. Ama toplama katkısı zaten sıfırdır. Asıl zorluk, çok büyük bir aralığı tek tek taramadan bütün pozitif sabit noktaları bulmaktır.
Çözüm iki temel fikir üzerine kurulur. Birincisi, \(f_d(n)\) her basamağın katkısı ayrı ayrı sayılarak \(O(\log_{10} n)\) zamanda tam hesaplanabilir. İkincisi, \(f_d\) monoton olduğundan büyük aralıklar yalnızca uç değerler kullanılarak elenebilir; böylece arama tek tek sayılar üzerinde değil, onluk bloklar üzerinde yapılır.
\(\nu_d(m)\), tek bir \(m\) sayısının normal onluk yazımında \(d\) rakamının kaç kez geçtiğini göstersin. O zaman
$$f_d(n)=\sum_{m=0}^{n}\nu_d(m).$$
Buradan \(f_d\)'nin azalmayan bir fonksiyon olduğu hemen görülür ve hatta
$$f_d(n+1)-f_d(n)=\nu_d(n+1)$$
olur. Şimdi
$$g_d(n)=f_d(n)-n$$
tanımını yaparsak, sabit nokta denklemi yalnızca \(g_d(n)=0\) demektir. Fakat
$$g_d(n+1)-g_d(n)=\nu_d(n+1)-1$$
olduğu için bu fark negatif, sıfır ya da pozitif olabilir. Yani \(g_d\) monoton değildir. Bu yüzden doğrudan ikili arama yapılamaz; program aralık eleme yöntemi kullanır.
Bir \(p=10^k\) basamağını sabitleyelim. Amaç, \(0,\dots,n\) içindeki hangi sayıların bu basamakta \(d\) rakamını taşıdığını saymaktır. Şöyle yazalım:
$$N=n+1,\qquad q=\left\lfloor\frac{N}{10p}\right\rfloor,\qquad r=N\bmod(10p).$$
İlk \(N\) sayı, uzunluğu \(10p\) olan \(q\) tam blok ve uzunluğu \(r\) olan bir son kuyruk blok olarak ayrılır. Her tam blokta ilgili basamak \(0,\dots,9\) değerlerini alır ve her rakam tam \(p\) ardışık sayı boyunca görünür. Dolayısıyla tam blokların katkısı \(qp\) olur.
Kalan kuyrukta ise yalnızca tek bir bitişik parça önemlidir: bu basamağın \(d\) olduğu bölüm, blok içindeki ilk \(dp\) değerden sonra başlar ve en fazla \(p\) adet uzunluğa sahiptir. Bu yüzden kuyruk katkısı
$$\min\!\bigl(\max(r-dp,0),\,p\bigr)$$
şeklindedir. Bütün aktif basamaklar üzerinden toplarsak uygulamaların kullandığı tam formül elde edilir:
$$f_d(n)=\sum_{p=1,10,100,\dots}\left(\left\lfloor\frac{n+1}{10p}\right\rfloor p+\min\!\bigl(\max((n+1)\bmod(10p)-dp,0),\,p\bigr)\right).$$
Burada baştaki sıfırlar için ek bir düzeltme gerekmez; çünkü problem yalnızca \(1\) ile \(9\) arasındaki rakamları soruyor. Eğer \(d=0\) olsaydı formül değişmek zorunda kalırdı.
\(f_1(12)=5\) eşitliği hem elle doğrulanabilir hem de formülün nasıl işlediğini açıkça gösterir. \(0\) ile \(12\) arasında rakam \(1\),
$$1,\ 10,\ 11,\ 12$$
sayılarında görünür; çokluklar sırasıyla \(1,1,2,1\) olduğu için toplam 5 eder.
Basamak formülü de aynı sonucu verir. Birler basamağı \(p=1\) için
$$\left\lfloor\frac{13}{10}\right\rfloor\cdot 1+\min(\max(13\bmod 10-1,0),1)=1+1=2$$
çıkar. Onlar basamağı \(p=10\) için ise
$$\left\lfloor\frac{13}{100}\right\rfloor\cdot 10+\min(\max(13\bmod 100-10,0),10)=0+3=3$$
olur. Daha yüksek aktif basamak yoktur; dolayısıyla \(f_1(12)=2+3=5\).
Bir sabit nokta \(x\), \([L,R]\) aralığında bulunsun. \(f_d\) monoton azalmayan olduğundan
$$f_d(L)\le f_d(x)=x\le f_d(R)$$
yazabiliriz. Öte yandan \(x\in[L,R]\) olduğundan
$$L\le x\le R$$
da geçerlidir. Bu iki zincir birlikte şu gerekli koşulları verir:
$$f_d(L)\le R,\qquad f_d(R)\ge L.$$
O halde eğer
$$f_d(R)\lt L\qquad\text{veya}\qquad f_d(L)\gt R$$
ise bu aralıkta hiç çözüm olamaz ve dal doğrudan kesilir.
Somut bir örnek olarak \(d=1\) için \([30,39]\) aralığını düşünelim. \(f_1(39)=14\) bulunur ve \(14\lt 30\) olduğundan tüm aralık bir anda elenir; 30, 31, 32 gibi değerleri tek tek denemeye gerek kalmaz.
Arama, seçilen üst sınırı örten bir \(10^m\) genişliğiyle başlar. Uzunluğu \(10^m\) olan ve elenmeyen her aralık, uzunluğu \(10^{m-1}\) olan on çocuk aralığa ayrılır. Bu seçim rastgele değildir; sayma formülünün kendisi de onluk bloklarla kurulduğu için her bölme işlemi aday sabit noktanın bir basamağını daha açığa çıkarır.
Genişlik 1'e indiğinde yaprak tek bir tam sayı adayını temsil eder ve program \(f_d(x)=x\) eşitliğini doğrudan kontrol eder. Böylece özyineleme yalnızca uç değer koşullarıyla hâlâ uyumlu kalan onluk kutuları ziyaret eder.
C++, Python ve Java uygulamalarının hepsi aynı üst düzey yapıyı izler: önce \(f_d(n)\) hızlı hesaplanır, sonra her \(d=1,\dots,9\) için onluk aralıklar üzerinde özyinelemeli bir arama yapılır.
Herhangi bir \(n\) değeri için uygulama, kapsayıcı \(0,\dots,n\) aralığını uzunluğu \(n+1\) olan yarı açık bir aralık gibi ele alır. Ardından \(1,10,100,\dots\) basamakları üzerinde döner; tam blok katkısını ve son kısmi bloğun katkısını ekleyerek toplamı üretir. Döngü her seferinde bir sonraki on kuvvetine geçtiği için tek bir değerlendirme yalnızca sayıdaki basamak sayısı kadar adım sürer.
Her rakam için uygulama, arama sınırını örten en küçük on kuvvetini kök genişlik olarak seçer. Her düğümde \(f_d\) sol ve sağ uçta değerlendirilir, yukarıdaki eleme testi uygulanır ve aralık imkansızsa hemen geri dönülür. Aksi halde arama on çocuk aralığa iner.
Genişlik 1 olduğunda sol uç, o yaprağın temsil ettiği tek tam sayı adaydır; bu yüzden uygulama eşitliği tam olarak kontrol eder ve aday gerçekten sabit nokta ise toplamda kullanır. C++ uygulaması ayrıca \(f_1(12)=5\) denetimi ve kısa bir aralıkta kaba kuvvet karşılaştırması gibi küçük doğrulamalar içerir; Python ve Java uygulamaları ise aynı arama mantığını bu ek doğrulama katmanı olmadan uygular.
\(U\) seçilen arama üst sınırı olsun. \(f_d(n)\) hesaplaması, onluk basamaklar üzerinden tek bir geçiş gerektirdiğinden \(O(\log U)\) zamanda ve \(O(1)\) ek bellekte yapılır.
Eğer elemeden sonra rakam \(d\) için \(V_d\) adet aralık düğümü ziyaret ediliyorsa, her düğümde iki uç nokta hesabı yapıldığı için toplam süre \(O(V_d\log U)\) olur. Özyineleme derinliği \(O(\log U)\) olduğundan yığın kullanımı da \(O(\log U)\) düzeyindedir.
En kötü durumda eleme çok az işe yararsa arama neredeyse tam taramaya yaklaşabilir; bu durumda \(V_d=O(U)\) ve zaman da \(O(U\log U)\) olur. Pratikte ise uç nokta testi çok sayıda onluk aralığı erken aşamada yok eder; yöntemin işe yarayan kısmı tam da budur.
Para un dígito fijo \(d\in\{1,\dots,9\}\), sea \(f_d(n)\) el número total de veces que \(d\) aparece en las representaciones decimales de todos los enteros entre \(0\) y \(n\). Hay que encontrar todos los enteros \(x\) tales que
$$f_d(x)=x,$$
y después sumar esos valores para todos los \(d=1,\dots,9\).
El valor \(x=0\) es un punto fijo trivial para cualquier dígito no nulo, porque la escritura decimal de \(0\) no contiene ninguno de los dígitos \(1,\dots,9\), pero no aporta nada a la suma final. La dificultad real consiste en localizar todos los puntos fijos positivos sin recorrer un rango enorme valor por valor.
La solución combina dos ideas. La primera es una fórmula exacta por posiciones decimales que permite evaluar \(f_d(n)\) en \(O(\log_{10} n)\). La segunda es que, como \(f_d\) es monótona, un intervalo grande puede descartarse mirando solo sus extremos; así la búsqueda se hace sobre bloques decimales y no sobre enteros individuales.
Sea \(\nu_d(m)\) el número de apariciones del dígito \(d\) en la representación decimal ordinaria del entero \(m\). Entonces
$$f_d(n)=\sum_{m=0}^{n}\nu_d(m).$$
De aquí se ve enseguida que \(f_d\) es no decreciente, y además
$$f_d(n+1)-f_d(n)=\nu_d(n+1).$$
Si definimos también
$$g_d(n)=f_d(n)-n,$$
la ecuación de punto fijo es simplemente \(g_d(n)=0\), pero
$$g_d(n+1)-g_d(n)=\nu_d(n+1)-1.$$
Esa diferencia puede ser negativa, cero o positiva. Por eso \(g_d\) no es monótona y una búsqueda binaria directa no sirve. El algoritmo usa otro invariante: la eliminación de intervalos mediante cotas en los extremos.
Fijemos una posición decimal \(p=10^k\). Queremos contar cuántos enteros de \(0,\dots,n\) tienen el dígito \(d\) en esa posición. Escribimos
$$N=n+1,\qquad q=\left\lfloor\frac{N}{10p}\right\rfloor,\qquad r=N\bmod(10p).$$
Los primeros \(N\) enteros se descomponen en \(q\) bloques completos de longitud \(10p\) y una cola final de longitud \(r\). En cada bloque completo, la cifra de esa posición recorre \(0,\dots,9\), y cada dígito permanece exactamente \(p\) veces consecutivas. Por tanto, los bloques completos aportan \(qp\).
Solo queda tratar la cola. Dentro del bloque parcial, los números cuyo dígito en la posición \(p\) vale \(d\) forman un tramo contiguo que empieza después de los primeros \(dp\) elementos del bloque y cuya longitud máxima es \(p\). Por ello, la contribución adicional es
$$\min\!\bigl(\max(r-dp,0),\,p\bigr).$$
Sumando sobre todas las posiciones activas obtenemos exactamente la fórmula que usan las implementaciones:
$$f_d(n)=\sum_{p=1,10,100,\dots}\left(\left\lfloor\frac{n+1}{10p}\right\rfloor p+\min\!\bigl(\max((n+1)\bmod(10p)-dp,0),\,p\bigr)\right).$$
Aquí no hace falta corregir ceros a la izquierda, porque el problema solo pide los dígitos \(1\) a \(9\). Para el dígito \(0\), la fórmula tendría que modificarse.
La identidad \(f_1(12)=5\) es un buen ejemplo de comprobación manual. Entre \(0\) y \(12\), el dígito \(1\) aparece en
$$1,\ 10,\ 11,\ 12,$$
con multiplicidades \(1,1,2,1\), así que el total es 5.
La fórmula posicional da lo mismo. Para la unidad \(p=1\),
$$\left\lfloor\frac{13}{10}\right\rfloor\cdot 1+\min(\max(13\bmod 10-1,0),1)=1+1=2.$$
Para la decena \(p=10\),
$$\left\lfloor\frac{13}{100}\right\rfloor\cdot 10+\min(\max(13\bmod 100-10,0),10)=0+3=3.$$
No hay más posiciones activas, luego \(f_1(12)=2+3=5\).
Supongamos que existe un punto fijo \(x\) dentro de un intervalo \([L,R]\). Como \(f_d\) es no decreciente, se cumple
$$f_d(L)\le f_d(x)=x\le f_d(R).$$
Y como además \(x\in[L,R]\), también tenemos
$$L\le x\le R.$$
Juntando ambas cadenas se obtienen las condiciones necesarias
$$f_d(L)\le R,\qquad f_d(R)\ge L.$$
Por lo tanto, si
$$f_d(R)\lt L\qquad\text{o}\qquad f_d(L)\gt R,$$
ese intervalo no puede contener ninguna solución y se descarta inmediatamente.
Un ejemplo concreto es \([30,39]\) para \(d=1\). Se tiene \(f_1(39)=14\), y como \(14\lt 30\), todo el intervalo queda eliminado de una vez; no hace falta revisar 30, 31, 32, etcétera.
La búsqueda comienza con un intervalo de tamaño \(10^m\) suficientemente grande para cubrir el límite elegido. Todo intervalo superviviente de tamaño \(10^m\) se divide en diez hijos de tamaño \(10^{m-1}\). Esto encaja exactamente con la estructura decimal de la fórmula: cada refinamiento fija una cifra más de un posible punto fijo.
Cuando el tamaño llega a 1, la hoja representa un único entero candidato y entonces se comprueba de forma exacta la igualdad \(f_d(x)=x\). La recursión solo visita, por tanto, aquellos bloques decimales que siguen siendo compatibles con las cotas de los extremos.
Las implementaciones en C++, Python y Java siguen el mismo esquema general: primero evaluan \(f_d(n)\) rápidamente en cualquier extremo pedido; después recorren, para cada \(d=1,\dots,9\), un árbol recursivo de intervalos decimales.
Para un valor \(n\), la implementación reescribe el rango inclusivo \(0,\dots,n\) como un intervalo semiabierto de longitud \(n+1\). Luego recorre las posiciones \(1,10,100,\dots\), suma la contribución de los bloques completos y la de la cola parcial, y devuelve el total. Como el bucle avanza por potencias de diez, una evaluación solo requiere tantas iteraciones como cifras tenga \(n\).
Para cada dígito, la implementación toma la menor potencia de diez que cubre el límite de búsqueda y la usa como intervalo raíz. En cada nodo evalúa \(f_d\) en el extremo izquierdo y en el derecho, aplica el criterio de poda anterior y retorna enseguida si el intervalo es imposible. En caso contrario, desciende a los diez hijos decimales.
Cuando el tamaño es 1, el extremo izquierdo es el único entero candidato representado por esa hoja; entonces la implementación comprueba la igualdad exacta y suma el valor si realmente es un punto fijo. La versión en C++ añade además pequeñas verificaciones internas, entre ellas la identidad manual \(f_1(12)=5\) y una comparación con fuerza bruta en un rango corto; las versiones en Python y Java conservan la misma lógica de búsqueda sin esa capa extra de validación.
Sea \(U\) el límite de búsqueda elegido. Una evaluación de \(f_d(n)\) recorre una vez las posiciones decimales, de modo que cuesta \(O(\log U)\) tiempo y \(O(1)\) memoria auxiliar.
Si para un dígito \(d\) sobreviven \(V_d\) nodos tras la poda, entonces el tiempo total para ese dígito es \(O(V_d\log U)\), porque cada nodo visitado realiza dos evaluaciones en los extremos. La profundidad de la recursión es \(O(\log U)\), así que el uso de pila también es \(O(\log U)\).
En el peor caso, la poda podría ser poco eficaz y la búsqueda acercarse a un barrido completo, con \(V_d=O(U)\) y por tanto \(O(U\log U)\) tiempo. En la práctica, la prueba en los extremos elimina la mayoría de los bloques decimales muy pronto, que es precisamente lo que hace útil al método.
对固定数字 \(d\in\{1,\dots,9\}\)，定义 \(f_d(n)\) 为从 \(0\) 到 \(n\) 的所有整数十进制表示中，数字 \(d\) 出现的总次数。题目要求找出所有满足
$$f_d(x)=x$$
的整数 \(x\)，然后再把这些 \(x\) 对所有 \(d=1,\dots,9\) 求和。
\(x=0\) 对每个非零数字来说都是平凡的不动点，因为数字 \(0\) 的十进制写法里根本没有 \(1,\dots,9\) 这些数字；不过它对最终总和没有贡献。真正困难的部分，是在一个非常大的搜索范围里找出全部正的不动点，而不是把每个整数都暴力检查一遍。
解法建立在两个核心观察上。第一，\(f_d(n)\) 可以按十进制位分解，并在 \(O(\log_{10} n)\) 时间内精确计算。第二，虽然不动点方程本身不能直接做普通二分，但 \(f_d\) 的单调性足以给出区间排除条件，于是搜索可以在十进制区间上递归进行，而不是逐点枚举。
记 \(\nu_d(m)\) 为单个整数 \(m\) 的通常十进制表示中，数字 \(d\) 出现的次数。那么
$$f_d(n)=\sum_{m=0}^{n}\nu_d(m).$$
从这个定义立刻可以看出 \(f_d\) 是单调不减的，并且有
$$f_d(n+1)-f_d(n)=\nu_d(n+1).$$
如果再定义
$$g_d(n)=f_d(n)-n,$$
那么不动点条件就是 \(g_d(n)=0\)。但是
$$g_d(n+1)-g_d(n)=\nu_d(n+1)-1$$
既可能为负，也可能为零，还可能为正，所以 \(g_d\) 并不单调。这一点很重要，因为它说明不能对 \(g_d\) 直接使用普通二分搜索；程序真正依赖的是区间端点给出的必要条件。
固定某一位权 \(p=10^k\)。我们要统计在 \(0,\dots,n\) 这些整数里，有多少个数在这一位上恰好等于数字 \(d\)。设
$$N=n+1,\qquad q=\left\lfloor\frac{N}{10p}\right\rfloor,\qquad r=N\bmod(10p).$$
前 \(N\) 个整数可以拆成 \(q\) 个长度为 \(10p\) 的完整块，再加上一个长度为 \(r\) 的尾块。在每个完整块里，这一位会按顺序取 \(0,\dots,9\)，而每个数字恰好连续出现 \(p\) 次，所以数字 \(d\) 在每个完整块中的贡献恰好是 \(p\)，总共贡献 \(qp\)。
剩下只需处理最后的不完整尾块。对这一位来说，数字等于 \(d\) 的那一段是一个连续区间：它从块内前 \(dp\) 个数之后开始，长度最多为 \(p\)。因此尾块贡献正好是
$$\min\!\bigl(\max(r-dp,0),\,p\bigr).$$
把所有有效位权加起来，就得到实现中使用的精确公式：
$$f_d(n)=\sum_{p=1,10,100,\dots}\left(\left\lfloor\frac{n+1}{10p}\right\rfloor p+\min\!\bigl(\max((n+1)\bmod(10p)-dp,0),\,p\bigr)\right).$$
这里不需要对前导零做修正，因为题目只要求数字 \(1\) 到 \(9\)。如果要统计 \(0\)，那就必须额外处理前导零的问题。
\(f_1(12)=5\) 是一个很好的手算例子，也正好展示了位贡献公式的含义。从 \(0\) 到 \(12\) 之间，数字 \(1\) 出现在
$$1,\ 10,\ 11,\ 12$$
这些数里，出现次数分别是 \(1,1,2,1\)，所以总数确实是 5。
用公式计算也完全一致。个位 \(p=1\) 的贡献为
$$\left\lfloor\frac{13}{10}\right\rfloor\cdot 1+\min(\max(13\bmod 10-1,0),1)=1+1=2.$$
十位 \(p=10\) 的贡献为
$$\left\lfloor\frac{13}{100}\right\rfloor\cdot 10+\min(\max(13\bmod 100-10,0),10)=0+3=3.$$
更高位已经没有贡献，因此 \(f_1(12)=2+3=5\)。
假设某个不动点 \(x\) 落在区间 \([L,R]\) 内。由于 \(f_d\) 单调不减，必有
$$f_d(L)\le f_d(x)=x\le f_d(R).$$
同时因为 \(x\in[L,R]\)，又有
$$L\le x\le R.$$
把这两组不等式合并，就得到必要条件
$$f_d(L)\le R,\qquad f_d(R)\ge L.$$
因此一旦出现
$$f_d(R)\lt L\qquad\text{或}\qquad f_d(L)\gt R,$$
就可以断定该区间内不可能存在解，整段区间可以直接丢弃。
例如对 \(d=1\)，区间 \([30,39]\) 就会被立刻排除，因为 \(f_1(39)=14\)，而 \(14\lt 30\)。既然右端点的计数都还到不了 30，那么区间内部任何整数都不可能满足 \(f_1(x)=x\)。
搜索从一个足以覆盖给定上界的 \(10^m\) 区间开始。任何没有被剪掉的 \(10^m\) 大小区间，都会继续细分成 10 个大小为 \(10^{m-1}\) 的子区间。这不是随便选的做法，而是与十进制块结构完全一致：每向下一层，就相当于把候选不动点的下一位数字也纳入约束。
当区间大小降到 1 时，叶子节点对应的就是唯一的整数候选，此时程序再做一次精确检验 \(f_d(x)=x\)。于是整棵递归树只会访问那些仍然满足端点必要条件的十进制盒子。
C++、Python 和 Java 三个实现遵循完全相同的总体结构：先快速计算任意端点处的 \(f_d(n)\)，再对每个 \(d=1,\dots,9\) 递归搜索十进制区间。
对于给定的 \(n\)，实现会把闭区间 \(0,\dots,n\) 改写成长度为 \(n+1\) 的半开区间。随后它沿着 \(1,10,100,\dots\) 这些位权循环，分别累加完整块贡献与尾块贡献，最终得到 \(f_d(n)\)。因为循环每次都乘 10，所以一次计算只需要和十进制位数同阶的迭代次数。
对每个数字，程序先取一个能够覆盖搜索上界的最小十次幂，把它当作根区间。每个递归节点都会在左右端点各算一次 \(f_d\)，应用上面的剪枝条件；如果区间已经不可能包含解，就立即返回。否则就继续递归到 10 个十进制子区间。
当区间大小为 1 时，左端点就是该叶子节点所代表的唯一整数候选，因此程序直接检查等式是否成立，若成立就把该值加入总和。C++ 实现额外带有一些小型校验，包括可以手算的 \(f_1(12)=5\) 以及一个短区间上的暴力对照；Python 与 Java 实现保留相同的搜索逻辑，但没有附带这层额外校验框架。
设搜索上界为 \(U\)。单次计算 \(f_d(n)\) 只需遍历所有十进制位，因此时间复杂度为 \(O(\log U)\)，额外空间复杂度为 \(O(1)\)。
如果对某个数字 \(d\)，剪枝后仍被访问的区间节点数为 \(V_d\)，那么这一数字的总时间就是 \(O(V_d\log U)\)，因为每个节点都要做两次端点计算。递归深度是 \(O(\log U)\)，所以栈空间也是 \(O(\log U)\)。
在最坏情况下，如果剪枝效果很差，搜索可能接近逐点扫描，于是 \(V_d=O(U)\)，时间就变成 \(O(U\log U)\)。但在实际运行中，端点条件会很早删掉大量十进制区间，这正是该方法能够工作的原因。
Для фиксированной цифры \(d\in\{1,\dots,9\}\) обозначим через \(f_d(n)\) общее число появлений цифры \(d\) во всех десятичных записях целых чисел от \(0\) до \(n\). Требуется найти все целые \(x\), для которых
$$f_d(x)=x,$$
а затем просуммировать такие \(x\) по всем \(d=1,\dots,9\).
Значение \(x=0\) является тривиальной неподвижной точкой для любой ненулевой цифры, потому что в десятичной записи числа \(0\) нет цифр \(1,\dots,9\), но в окончательную сумму оно ничего не добавляет. Основная трудность состоит в том, чтобы найти все положительные решения, не перебирая огромный диапазон по одному числу.
Решение опирается на две идеи. Во-первых, \(f_d(n)\) можно вычислять точно за \(O(\log_{10} n)\), суммируя независимые вклады отдельных разрядов. Во-вторых, монотонность \(f_d\) позволяет отсекать большие интервалы по значениям на концах, так что поиск идет по десятичным блокам, а не по отдельным числам.
Пусть \(\nu_d(m)\) означает число вхождений цифры \(d\) в обычной десятичной записи одного числа \(m\). Тогда
$$f_d(n)=\sum_{m=0}^{n}\nu_d(m).$$
Из этого определения сразу видно, что \(f_d\) неубывает, и более того,
$$f_d(n+1)-f_d(n)=\nu_d(n+1).$$
Если ввести
$$g_d(n)=f_d(n)-n,$$
то уравнение неподвижной точки принимает вид \(g_d(n)=0\), но
$$g_d(n+1)-g_d(n)=\nu_d(n+1)-1.$$
Эта разность может быть отрицательной, нулевой или положительной. Значит, \(g_d\) не является монотонной функцией, и обычный двоичный поиск по \(g_d\) здесь неприменим. Поэтому реализация использует не смену знака, а отсечение интервалов.
Зафиксируем разряд \(p=10^k\). Нужно посчитать, сколько чисел из \(0,\dots,n\) имеют цифру \(d\) именно в этом разряде. Обозначим
$$N=n+1,\qquad q=\left\lfloor\frac{N}{10p}\right\rfloor,\qquad r=N\bmod(10p).$$
Первые \(N\) чисел разбиваются на \(q\) полных блоков длины \(10p\) и один неполный хвост длины \(r\). В каждом полном блоке рассматриваемый разряд проходит через \(0,\dots,9\), и каждая цифра удерживается ровно \(p\) подряд идущих значений. Поэтому полные блоки дают вклад \(qp\).
Остается хвост. Внутри последнего блока числа, у которых этот разряд равен \(d\), образуют один непрерывный отрезок: он начинается после первых \(dp\) элементов блока и имеет длину не больше \(p\). Следовательно, дополнительный вклад равен
$$\min\!\bigl(\max(r-dp,0),\,p\bigr).$$
Суммируя по всем активным разрядам, получаем точную формулу, реализованную в программах:
$$f_d(n)=\sum_{p=1,10,100,\dots}\left(\left\lfloor\frac{n+1}{10p}\right\rfloor p+\min\!\bigl(\max((n+1)\bmod(10p)-dp,0),\,p\bigr)\right).$$
Поправка на ведущие нули не нужна, потому что в условии рассматриваются только цифры \(1\) до \(9\). Для цифры \(0\) формула потребовала бы отдельного учета.
Тождество \(f_1(12)=5\) легко проверить вручную и удобно использовать как контрольный пример. От \(0\) до \(12\) цифра \(1\) встречается в числах
$$1,\ 10,\ 11,\ 12,$$
с кратностями \(1,1,2,1\), так что суммарно получаем 5.
Формула по разрядам дает то же самое. Для единиц \(p=1\) имеем
$$\left\lfloor\frac{13}{10}\right\rfloor\cdot 1+\min(\max(13\bmod 10-1,0),1)=1+1=2.$$
Для десятков \(p=10\) получаем
$$\left\lfloor\frac{13}{100}\right\rfloor\cdot 10+\min(\max(13\bmod 100-10,0),10)=0+3=3.$$
Других активных разрядов нет, значит \(f_1(12)=2+3=5\).
Пусть неподвижная точка \(x\) лежит в интервале \([L,R]\). Так как \(f_d\) не убывает, имеем
$$f_d(L)\le f_d(x)=x\le f_d(R).$$
А из условия \(x\in[L,R]\) следует
$$L\le x\le R.$$
Объединяя эти цепочки, получаем необходимые условия
$$f_d(L)\le R,\qquad f_d(R)\ge L.$$
Следовательно, если
$$f_d(R)\lt L\qquad\text{или}\qquad f_d(L)\gt R,$$
то решений внутри интервала быть не может, и его можно отбросить немедленно.
Например, для \(d=1\) интервал \([30,39]\) отсекается сразу: \(f_1(39)=14\), а \(14\lt 30\). Значит, ни одно число между 30 и 39 не может удовлетворять равенству \(f_1(x)=x\).
Поиск начинается с промежутка длины \(10^m\), достаточного для покрытия выбранной верхней границы. Каждый выживший интервал длины \(10^m\) делится на десять дочерних интервалов длины \(10^{m-1}\). Это естественно согласуется с самой десятичной структурой формулы: каждый шаг вниз фиксирует еще одну цифру возможной неподвижной точки.
Когда длина становится равной 1, лист соответствует единственному целому кандидату, и тогда уже выполняется точная проверка \(f_d(x)=x\). В итоге рекурсия посещает только те десятичные блоки, которые еще не противоречат условиям на концах.
Реализации на C++, Python и Java следуют одной и той же общей схеме: сначала быстро вычисляется \(f_d(n)\) на нужных концах интервалов, а затем для каждого \(d=1,\dots,9\) обходится рекурсивное дерево десятичных интервалов.
Для заданного \(n\) программа переписывает включительный диапазон \(0,\dots,n\) как полуинтервал длины \(n+1\). Затем она проходит по разрядам \(1,10,100,\dots\), добавляет вклад полных блоков и вклад последнего частичного блока и возвращает сумму. Поскольку переход идет по степеням десяти, одна такая оценка требует лишь столько шагов, сколько десятичных цифр у числа.
Для каждой цифры берется минимальная степень десяти, покрывающая поисковый предел, и используется как корневой интервал. В каждом узле вычисляются значения \(f_d\) на левом и правом концах, применяется критерий отсечения, и при невозможности интервал отбрасывается сразу. Иначе обход продолжается по десяти дочерним интервалам.
При длине 1 левый конец и есть единственный целый кандидат, представленный этим листом, поэтому программа точно проверяет равенство и прибавляет значение к ответу, если это действительно неподвижная точка. В реализации на C++ дополнительно есть небольшие контрольные проверки, включая вручную проверяемое равенство \(f_1(12)=5\) и сравнение с грубой силой на коротком диапазоне; версии на Python и Java используют ту же поисковую схему без этой дополнительной валидации.
Пусть \(U\) обозначает выбранную верхнюю границу поиска. Одно вычисление \(f_d(n)\) требует прохода по десятичным разрядам, то есть занимает \(O(\log U)\) времени и \(O(1)\) дополнительной памяти.
Если после отсечения для цифры \(d\) остается \(V_d\) посещенных узлов интервалов, то общее время для этой цифры равно \(O(V_d\log U)\), потому что в каждом узле выполняются две оценки на концах. Глубина рекурсии составляет \(O(\log U)\), следовательно, стек также требует \(O(\log U)\) памяти.
В худшем случае отсечение могло бы работать слабо, и поиск приблизился бы к полному перебору, тогда \(V_d=O(U)\), а время стало бы \(O(U\log U)\). На практике проверка концов отбрасывает большинство десятичных интервалов очень рано, поэтому метод оказывается эффективным без каких-либо больших таблиц.
لرقم ثابت \(d\in\{1,\dots,9\}\)، نرمز بـ \(f_d(n)\) إلى العدد الكلي لمرات ظهور الرقم \(d\) في التمثيلات العشرية لجميع الأعداد الصحيحة من \(0\) حتى \(n\). المطلوب هو إيجاد كل عدد صحيح \(x\) يحقق
$$f_d(x)=x,$$
ثم جمع هذه القيم عبر جميع الأرقام \(d=1,\dots,9\).
القيمة \(x=0\) هي نقطة ثابتة بديهية لكل رقم غير صفري، لأن التمثيل العشري للعدد \(0\) لا يحتوي أيًا من الأرقام \(1,\dots,9\)، لكنها لا تضيف شيئًا إلى المجموع النهائي. الصعوبة الحقيقية هي إيجاد جميع النقاط الثابتة الموجبة من غير فحص مدى هائل عددًا بعد عدد.
يقوم الحل على فكرتين مترابطتين. الأولى أن \(f_d(n)\) يمكن حسابها بدقة في \(O(\log_{10} n)\) عبر جمع مساهمات المنازل العشرية واحدةً تلو الأخرى. والثانية أن رتابة \(f_d\) تسمح باستبعاد فترات كبيرة اعتمادًا على قيم الطرفين فقط، وبذلك يتحول البحث من مسح خطي على الأعداد إلى بحث منظم على كتل عشرية.
لنعرّف \(\nu_d(m)\) بأنها عدد مرات ظهور الرقم \(d\) في التمثيل العشري المعتاد للعدد المفرد \(m\). عندئذٍ
$$f_d(n)=\sum_{m=0}^{n}\nu_d(m).$$
من هذا التعريف نرى مباشرةً أن \(f_d\) دالة غير متناقصة، بل وأكثر من ذلك:
$$f_d(n+1)-f_d(n)=\nu_d(n+1).$$
وإذا كتبنا أيضًا
$$g_d(n)=f_d(n)-n,$$
فإن معادلة النقطة الثابتة تصبح ببساطة \(g_d(n)=0\)، لكن
$$g_d(n+1)-g_d(n)=\nu_d(n+1)-1.$$
وهذا الفرق قد يكون سالبًا أو صفرًا أو موجبًا، لذلك فالدالة \(g_d\) ليست رتيبة. ولهذا السبب لا تصلح هنا عملية بحث ثنائي مباشرة على \(g_d\)، ويعتمد الحل بدلًا من ذلك على استبعاد الفترات المستحيلة.
لنثبت منزلة واحدة \(p=10^k\). نريد أن نعرف كم عدد الأعداد في المجال \(0,\dots,n\) التي تساوي فيها هذه المنزلة الرقم \(d\). نضع
$$N=n+1,\qquad q=\left\lfloor\frac{N}{10p}\right\rfloor,\qquad r=N\bmod(10p).$$
الأعداد الأولى وعددها \(N\) تنقسم إلى \(q\) كتل كاملة طول كل منها \(10p\)، بالإضافة إلى ذيل أخير طوله \(r\). في كل كتلة كاملة تمر هذه المنزلة على القيم \(0,\dots,9\)، ويظهر كل رقم فيها خلال \(p\) قيم متتالية بالضبط. لذلك يكون إسهام الكتل الكاملة مساويًا لـ \(qp\).
يبقى الذيل الجزئي فقط. داخل الكتلة الأخيرة، تشكل الأعداد التي تحمل الرقم \(d\) في المنزلة \(p\) قطعة متصلة تبدأ بعد أول \(dp\) عنصر من الكتلة، ولا يزيد طولها على \(p\). ومن ثم فإن مساهمة الذيل تساوي
$$\min\!\bigl(\max(r-dp,0),\,p\bigr).$$
وبجمع ذلك على جميع المنازل الفعالة نحصل على الصيغة الدقيقة التي تستخدمها التطبيقات:
$$f_d(n)=\sum_{p=1,10,100,\dots}\left(\left\lfloor\frac{n+1}{10p}\right\rfloor p+\min\!\bigl(\max((n+1)\bmod(10p)-dp,0),\,p\bigr)\right).$$
ولا حاجة هنا إلى تصحيح خاص بالأصفار البادئة، لأن المسألة لا تطلب إلا الأرقام من \(1\) إلى \(9\). أما لو كنا نعدّ الرقم \(0\)، لاحتجنا إلى معالجة مختلفة.
الهوية \(f_1(12)=5\) صغيرة بما يكفي للتحقق اليدوي، وهي مثال جيد على طريقة الصيغة. من \(0\) إلى \(12\)، يظهر الرقم \(1\) في
$$1,\ 10,\ 11,\ 12,$$
وبالتكرارات \(1,1,2,1\)، فيكون المجموع 5.
وصيغة المنازل تعطي النتيجة نفسها. في منزلة الآحاد \(p=1\) نحصل على
$$\left\lfloor\frac{13}{10}\right\rfloor\cdot 1+\min(\max(13\bmod 10-1,0),1)=1+1=2.$$
وفي منزلة العشرات \(p=10\) نحصل على
$$\left\lfloor\frac{13}{100}\right\rfloor\cdot 10+\min(\max(13\bmod 100-10,0),10)=0+3=3.$$
ولا توجد منازل أعلى فعالة هنا، لذا يكون \(f_1(12)=2+3=5\).
افترض أن هناك نقطة ثابتة \(x\) داخل الفترة \([L,R]\). بما أن \(f_d\) غير متناقصة، فلدينا
$$f_d(L)\le f_d(x)=x\le f_d(R).$$
وبما أن \(x\in[L,R]\)، فلدينا أيضًا
$$L\le x\le R.$$
وبضم السلسلتين نحصل على الشرطين الضروريين
$$f_d(L)\le R,\qquad f_d(R)\ge L.$$
إذن إذا كان \(f_d(R)\lt L\) أو \(f_d(L)\gt R\)،
فلا يمكن أن تحتوي هذه الفترة على أي حل، ويمكن حذفها مباشرة.
مثال واضح: للفترة \([30,39]\) عند \(d=1\) نجد أن \(f_1(39)=14\)، وبما أن \(14\lt 30\)، فإن الفترة كلها مستحيلة. لا حاجة إذن إلى اختبار 30 و31 و32 كلًّا على حدة.
يبدأ البحث من مجال طوله \(10^m\) كبير بما يكفي لتغطية الحد الأعلى المختار. وكل فترة باقية بطول \(10^m\) تُقسَّم إلى عشرة أبناء بطول \(10^{m-1}\). هذا ليس اختيارًا اعتباطيًا، لأن صيغة العد نفسها مبنية على كتل عشرية؛ وكل نزول في الشجرة يحدد منزلة عشرية إضافية للمرشح المحتمل.
وعندما يصبح الطول مساويًا لـ 1، تمثل الورقة عددًا صحيحًا واحدًا فقط، وعندها تُفحص المعادلة \(f_d(x)=x\) فحصًا دقيقًا. وبهذه الطريقة لا تزور العودية إلا الصناديق العشرية التي ما زالت منسجمة مع شروط الطرفين.
تتبع تطبيقات C++ وPython وJava البنية العامة نفسها: أولًا حساب سريع للقيمة \(f_d(n)\) عند أي طرف مطلوب، ثم بحث عودي عبر فترات عشرية لكل رقم \(d=1,\dots,9\).
بالنسبة إلى أي قيمة \(n\)، تعيد الشيفرة كتابة المجال الشامل \(0,\dots,n\) على هيئة فترة نصف مفتوحة طولها \(n+1\). ثم تدور على المنازل \(1,10,100,\dots\)، وتضيف إسهام الكتل الكاملة وإسهام الكتلة الجزئية الأخيرة، ثم تعيد المجموع. وبما أن الحلقة تنتقل بقوى العشرة، فإن كلفة التقييم الواحد تساوي عدد المنازل العشرية تقريبًا.
لكل رقم، تختار الشيفرة أصغر قوة للعشرة تغطي حد البحث وتستعملها كفترة جذرية. في كل عقدة تُحسب \(f_d\) عند الطرفين الأيسر والأيمن، ثم يُطبَّق معيار الاستبعاد السابق، وتعود الدالة فورًا إذا كانت الفترة مستحيلة. وإلا تتابع النزول إلى الأبناء العشرة.
وعندما يكون الطول 1، يكون الطرف الأيسر هو العدد الصحيح الوحيد الذي تمثله تلك الورقة، ولذلك تُفحص المساواة مباشرة، ويُضاف العدد إلى المجموع إذا كان نقطة ثابتة فعلًا. كما تتضمن نسخة C++ اختبارات تحقق صغيرة، منها العلاقة السهلة يدويًا \(f_1(12)=5\) ومقارنة مع brute force على مجال قصير، بينما تحتفظ نسختا Python وJava بمنطق البحث نفسه من دون طبقة التحقق الإضافية.
لنرمز إلى حد البحث المختار بـ \(U\). إن تقييم \(f_d(n)\) يتطلب مرورًا واحدًا على المنازل العشرية، لذلك كلفته الزمنية \(O(\log U)\) ويحتاج إلى \(O(1)\) ذاكرة إضافية.
إذا كان عدد عقد الفترات التي تبقى بعد الاستبعاد للرقم \(d\) هو \(V_d\)، فإن الزمن الكلي لهذا الرقم يساوي \(O(V_d\log U)\)، لأن كل عقدة مزارة تنفذ تقييمين عند الطرفين. وعمق الاستدعاء الذاتي يساوي \(O(\log U)\)، وبالتالي يكون استهلاك المكدس أيضًا \(O(\log U)\).
وفي أسوأ الأحوال قد يكون الاستبعاد ضعيفًا بحيث يقترب البحث من مسح كامل، وعندها يصبح \(V_d=O(U)\) والزمن \(O(U\log U)\). أما عمليًا فإن اختبار الطرفين يحذف معظم الفترات العشرية في وقت مبكر جدًا، ولهذا تكون الطريقة فعالة من غير الحاجة إلى جداول ضخمة.