Champernowne's constant in base 10 is \(C_{10}=0.1234567891011121314\ldots\), obtained by concatenating the positive integers in order. If \(d(n)\) denotes the \(n\)-th digit after the decimal point, the problem asks for the product
$$d(1)\,d(10)\,d(100)\,d(1000)\,d(10000)\,d(100000)\,d(1000000).$$
The central issue is an indexing problem inside an infinite decimal string. We only need seven specific digits, so the question is how to reach those digits cleanly and efficiently.
The implementations use a left-to-right scan of the decimal expansion of \(1,2,3,\ldots\). That choice is mathematically justified because the requested positions are sparse, ordered, and small enough that the scan ends quickly. The natural framework is to organize the concatenation by digit length.
All \(k\)-digit integers form one contiguous block inside Champernowne's constant. There are \(9\cdot 10^{k-1}\) such integers, and each contributes \(k\) digits, so the block contributes
$$B_k=9k\cdot 10^{k-1}$$
digits in total. The first values are
$$B_1=9,\qquad B_2=180,\qquad B_3=2700,\qquad B_4=36000,\qquad B_5=450000.$$
If we define the cumulative total
$$S_m=\sum_{k=1}^{m} B_k,$$
then \(S_m\) counts all digits contributed by integers with at most \(m\) digits. In particular,
$$S_5=9+180+2700+36000+450000=488889.$$
So the position \(10^6\) lies in the 6-digit block rather than deep inside the sequence.
The only positions that matter are the powers of ten
$$T_p=10^p \qquad (p=0,1,\dots,6).$$
These checkpoints are strictly increasing. That means a single forward pass is enough: once the scan has consumed the first \(q\) digits of the concatenation, every checkpoint at most \(q\) has already been resolved, and every larger checkpoint still lies ahead. No backtracking and no random access are needed.
If the scan has processed all integers from \(1\) through some \(d\)-digit integer \(n\), then the number of emitted digits is
$$L(n)=\sum_{k=1}^{d-1} 9k\cdot 10^{k-1}+d\bigl(n-10^{d-1}+1\bigr).$$
The code does not evaluate this formula directly, but it explains why the streaming method is small-scale. Since \(S_5=488889\), we still need
$$10^6-S_5=511111$$
digits from the 6-digit block. Because each 6-digit number contributes 6 digits, the scan needs
$$\left\lceil \frac{511111}{6} \right\rceil = 85186$$
six-digit integers, ending at \(100000+85186-1=185185\). So even the largest requested digit appears after scanning only up to 185185.
The built-in checkpoint used by the implementations asks for the product at positions \(1\), \(10\), and \(100\).
For \(d(1)\), the answer is immediately \(1\). For \(d(10)\), the first 9 digits come from \(1\) through \(9\), so the 10th digit is the first digit of \(10\), again \(1\).
For \(d(100)\), remove the first 9 digits. The target is now the 91st digit inside the 2-digit block. Since each 2-digit number contributes 2 digits,
$$\left\lfloor \frac{91-1}{2} \right\rfloor = 45$$
shows that we are in the \(46\)-th two-digit number, namely \(10+45=55\). The position inside that number is
$$(91-1)\bmod 2=0,$$
so the desired digit is the first digit of \(55\), which is \(5\). Therefore
$$d(1)\,d(10)\,d(100)=1\cdot 1\cdot 5=5,$$
exactly matching the small verification case used by the implementations.
The C++, Python, and Java implementations all use the same streaming strategy. They never build the whole million-digit prefix as one string. Instead, they walk through the integers in order, expose their decimal digits one by one, and update a tiny amount of state.
The implementation first constructs the finite target list \(1,10,100,\dots,10^m\), with the default choice \(m=6\). While building that list, it guards against overflow before multiplying by 10, so the target positions always remain valid for the host integer type.
Next, the program iterates through the positive integers \(1,2,3,\ldots\). Each integer is converted to its decimal form, and its digits are processed from left to right. One running counter records the current position in Champernowne's constant, and another index marks the next unresolved checkpoint.
The key invariant is this: after processing the integers up to \(n\), the position counter equals \(L(n)\), the total number of digits emitted so far. Therefore, whenever the counter lands on the next checkpoint, the current digit is exactly the required value \(d(10^p)\), and it can be multiplied into the accumulated product immediately.
Because the checkpoints are sorted, the scan stops as soon as the digit at the largest requested position has been consumed. For the Project Euler instance this is the digit at position \(10^6\). Nothing beyond that point can affect the answer, so the computation ends at once.
Before returning the final product, each implementation can verify two small cases. The first asks for positions up to \(10^2\) and must return \(5\). The second asks only for position \(10^0\) and must return \(1\). These tests validate the target generation, the streaming logic, and the multiplicative accumulation together.
If the largest requested checkpoint is \(10^m\), the algorithm processes exactly \(10^m\) emitted digits, so the running time is \(O(10^m)\). In the actual problem, \(m=6\), which means one million digit visits and a scan only up to the integer \(185185\).
The extra memory usage is \(O(m)\) for the checkpoint list, plus the decimal representation of the current integer. For the default input this is effectively constant space. The important practical point is that the code streams digits on demand instead of storing the entire concatenated prefix.
Champernownes Konstante zur Basis 10 ist \(C_{10}=0.1234567891011121314\ldots\), also die Verkettung aller positiven ganzen Zahlen in aufsteigender Reihenfolge. Wenn \(d(n)\) die \(n\)-te Ziffer nach dem Dezimalpunkt bezeichnet, soll das Produkt
$$d(1)\,d(10)\,d(100)\,d(1000)\,d(10000)\,d(100000)\,d(1000000)$$
berechnet werden. Der Kern des Problems ist also kein schwieriges Multiplizieren, sondern das gezielte Auffinden weniger ausgewahlter Ziffern in einer unendlichen Dezimalfolge.
Die Implementierungen lesen die Ziffernfolge von links nach rechts, indem sie die Dezimaldarstellungen von \(1,2,3,\ldots\) nacheinander durchlaufen. Warum das funktioniert und warum es schnell genug ist, sieht man am besten an der Blockstruktur nach Ziffernlangen.
Alle \(k\)-stelligen Zahlen bilden in der Verkettung einen zusammenhangenden Block. Es gibt \(9\cdot 10^{k-1}\) solche Zahlen, und jede davon liefert \(k\) Ziffern. Also tragt dieser Block insgesamt
$$B_k=9k\cdot 10^{k-1}$$
Ziffern bei. Die ersten Werte sind
$$B_1=9,\qquad B_2=180,\qquad B_3=2700,\qquad B_4=36000,\qquad B_5=450000.$$
Mit der kumulierten Summe
$$S_m=\sum_{k=1}^{m} B_k$$
erhalt man die gesamte Ziffernzahl aller Zahlen mit hochstens \(m\) Stellen. Insbesondere gilt
$$S_5=9+180+2700+36000+450000=488889.$$
Damit liegt die Position \(10^6\) bereits im Block der 6-stelligen Zahlen.
Benotigt werden nur die Stellen
$$T_p=10^p \qquad (p=0,1,\dots,6).$$
Diese Zielpositionen sind streng aufsteigend. Deshalb reicht ein einziger Vorwartsdurchlauf: Sobald die ersten \(q\) Ziffern der Verkettung verarbeitet sind, sind alle Zielpositionen \(\le q\) endgultig bestimmt, und alle groBeren liegen noch vor uns. Weder Rucksprunge noch zufalliger Zugriff sind notig.
Wenn alle Zahlen von \(1\) bis zu einer \(d\)-stelligen Zahl \(n\) verarbeitet wurden, dann ist die bisher ausgegebene Ziffernzahl
$$L(n)=\sum_{k=1}^{d-1} 9k\cdot 10^{k-1}+d\bigl(n-10^{d-1}+1\bigr).$$
Diese Formel wird im Code nicht direkt ausgewertet, erklart aber den kleinen Suchraum. Da \(S_5=488889\) ist, fehlen bis zur millionsten Stelle noch
$$10^6-S_5=511111$$
Ziffern aus dem 6-stelligen Block. Jede 6-stellige Zahl liefert 6 Ziffern, also werden
$$\left\lceil \frac{511111}{6} \right\rceil = 85186$$
solche Zahlen benotigt. Der Durchlauf endet also bereits bei \(100000+85186-1=185185\).
Die kleinen Selbsttests der Implementierungen verwenden die Positionen \(1\), \(10\) und \(100\).
Fur \(d(1)\) ist die Antwort sofort \(1\). Fur \(d(10)\) kommen die ersten 9 Ziffern von \(1\) bis \(9\), also ist die 10. Ziffer die erste Ziffer von \(10\), ebenfalls \(1\).
Bei \(d(100)\) ziehen wir zunachst die 9 Ziffern des einstelligen Blocks ab. Es bleibt die 91. Ziffer im zweistelligen Block. Da jede zweistellige Zahl 2 Ziffern beisteuert, zeigt
$$\left\lfloor \frac{91-1}{2} \right\rfloor = 45$$
dass wir uns in der \(46\)-ten zweistelligen Zahl befinden, also in \(10+45=55\). Die Position innerhalb dieser Zahl ist
$$(91-1)\bmod 2=0,$$
also wird die erste Ziffer von \(55\) benotigt, namlich \(5\). Damit erhalt man
$$d(1)\,d(10)\,d(100)=1\cdot 1\cdot 5=5,$$
genau den Kontrollwert der Implementierungen.
Die C++-, Python- und Java-Implementierungen folgen derselben Streaming-Idee. Sie bauen das millionenstellige Prafix nicht als eine groBe Zeichenkette auf, sondern laufen nacheinander durch die positiven ganzen Zahlen und verarbeiten deren Dezimalziffern sofort.
Zuerst wird die endliche Liste \(1,10,100,\dots,10^m\) aufgebaut; standardmaBig ist \(m=6\). Beim fortgesetzten Multiplizieren mit 10 pruft die Implementierung jeweils vorab, ob ein Uberlauf droht.
Danach werden die Zahlen \(1,2,3,\ldots\) der Reihe nach in Dezimalschreibweise betrachtet. Ein laufender Zahler merkt sich, an welcher globalen Position der Verkettung man sich gerade befindet. Ein zweiter Zeiger markiert die nachste noch offene Zielposition.
Die zentrale Invariante lautet: Nach der Verarbeitung aller Zahlen bis \(n\) ist der Positionszahler gleich \(L(n)\), also genau der Anzahl bereits ausgegebener Ziffern. Landet der Zahler auf der nachsten Zielposition, dann ist die aktuell betrachtete Ziffer genau das gesuchte \(d(10^p)\) und wird sofort in das Produkt ubernommen.
Weil die Zielpositionen sortiert sind, kann der Durchlauf sofort enden, sobald die groBte benotigte Stelle erreicht wurde. Fur die eigentliche Aufgabe ist das die Stelle \(10^6\). Alles dahinter ware fur das Ergebnis irrelevant.
Vor der Ausgabe konnen die Implementierungen zwei kleine Tests ausfuhren. Bis \(10^2\) muss das Produkt \(5\) sein, und bis \(10^0\) muss es \(1\) sein. Diese beiden Falle prufen Zielerzeugung, Ziffernstream und Produktspeicherung in einem Zug.
Ist die groBte abgefragte Zielposition \(10^m\), dann verarbeitet der Algorithmus genau \(10^m\) ausgegebene Ziffern. Die Laufzeit ist also \(O(10^m)\). Im Project-Euler-Fall mit \(m=6\) bedeutet das genau eine Million Ziffern und einen Durchlauf nur bis zur Zahl \(185185\).
Der zusatzliche Speicherbedarf ist \(O(m)\) fur die Liste der Zielpositionen plus die Dezimaldarstellung der gerade bearbeiteten Zahl. Fur die Standardaufgabe ist das praktisch konstanter Speicher. Entscheidend ist, dass die Ziffern on demand gestreamt und nicht als volles Prafix gespeichert werden.
10 tabanındaki Champernowne sabiti \(C_{10}=0.1234567891011121314\ldots\) biçimindedir; yani pozitif tam sayılar sırayla yan yana yazılır. \(d(n)\) ondalık noktadan sonraki \(n\). basamağı göstersin. İstenen çarpım
$$d(1)\,d(10)\,d(100)\,d(1000)\,d(10000)\,d(100000)\,d(1000000)$$
değeridir. Asıl mesele son çarpma işlemi değil, sonsuz bir basamak dizisi içinden yalnızca yedi özel konumu doğru biçimde yakalamaktır.
Uygulamalar \(1,2,3,\ldots\) sayılarının ondalık yazımlarını soldan sağa tarar. Bu seçim rastgele değildir. Hedef konumlar seyrek, sıralı ve yeterince küçüktür; bu yüzden akış halinde ilerlemek hem matematiksel olarak doğal hem de pratik olarak yeterlidir. Bunu görmek için diziyi basamak sayısına göre bloklara ayırmak gerekir.
Tüm \(k\) basamaklı sayılar tek bir blok oluşturur. Böyle sayıların sayısı \(9\cdot 10^{k-1}\) olduğundan, bu blok toplam
$$B_k=9k\cdot 10^{k-1}$$
basamak üretir. İlk birkaç değer
$$B_1=9,\qquad B_2=180,\qquad B_3=2700,\qquad B_4=36000,\qquad B_5=450000$$
şeklindedir. Kümülatif toplamı
$$S_m=\sum_{k=1}^{m} B_k$$
olarak yazarsak, \(S_m\) en çok \(m\) basamaklı sayıların ürettiği toplam basamak sayısını verir. Özellikle
$$S_5=9+180+2700+36000+450000=488889.$$
Dolayısıyla \(10^6\). konum, beklenenden çok daha geç değil, 6 basamaklı sayılar bloğunun içindedir.
İlgilendiğimiz tek konumlar
$$T_p=10^p \qquad (p=0,1,\dots,6)$$
değerleridir. Bu hedefler artan sırada olduğu için tek yönlü bir tarama yeterlidir. Akışın ilk \(q\) basamağı işlendiğinde, \(q\)'ya eşit ya da ondan küçük bütün hedefler kesinleşmiş olur; daha büyük hedefler ise hâlâ ileridedir. Bu nedenle geri dönmeye, rasgele erişime ya da uzun bir dize saklamaya gerek yoktur.
Tarama \(n\) adlı \(d\) basamaklı sayıya kadar gelmişse, o ana kadar üretilen basamak sayısı
$$L(n)=\sum_{k=1}^{d-1} 9k\cdot 10^{k-1}+d\bigl(n-10^{d-1}+1\bigr)$$
olur. Kod bu formülü doğrudan kullanmaz; yine de yöntemin neden küçük ölçekte kaldığını açıklar. Çünkü \(S_5=488889\) olduğundan, milyonuncu basamağa ulaşmak için 6 basamaklı bloktan hâlâ
$$10^6-S_5=511111$$
basamak gereklidir. Her 6 basamaklı sayı 6 basamak verdiği için gereken sayı adedi
$$\left\lceil \frac{511111}{6} \right\rceil = 85186$$
olur. Bu da taramanın \(100000+85186-1=185185\) sayısında biteceği anlamına gelir.
Uygulamaların kullandığı küçük doğrulama, \(1\), \(10\) ve \(100\) konumlarındaki basamakların çarpımıdır.
\(d(1)=1\) açıktır. \(d(10)\) için ilk 9 basamak \(1\) ile \(9\) arasından gelir; dolayısıyla 10. basamak, \(10\) sayısının ilk basamağı olan \(1\)'dir.
\(d(100)\) için önce tek basamaklı bloktaki 9 basamağı çıkarırız. Geriye iki basamaklı blok içinde 91. basamak kalır. Her iki basamaklı sayı 2 basamak verdiği için
$$\left\lfloor \frac{91-1}{2} \right\rfloor = 45$$
sonucu, hedefin \(46\). iki basamaklı sayı olan \(10+45=55\) içinde olduğunu söyler. Sayı içindeki ofset
$$(91-1)\bmod 2=0$$
olduğundan, aranan basamak \(55\)'in ilk basamağıdır; yani \(5\). Böylece
$$d(1)\,d(10)\,d(100)=1\cdot 1\cdot 5=5$$
elde edilir. Bu da uygulamalardaki kontrol sonucuyla tam olarak aynıdır.
C++, Python ve Java uygulamalarının üçü de aynı akış yaklaşımını kullanır. Milyon basamaklık ön eki tek bir dize olarak oluşturmazlar. Bunun yerine pozitif tam sayıları sırayla gezer, her sayının ondalık basamaklarını üretir ve gereken küçük durumu güncellerler.
Önce sonlu hedef listesi \(1,10,100,\dots,10^m\) oluşturulur; varsayılan seçim \(m=6\)'dır. Liste kurulurken 10 ile çarpma öncesinde taşma kontrolü yapılır. Böylece hedef konumlar kullanılan tam sayı tipinin dışına sessizce çıkmaz.
Daha sonra \(1,2,3,\ldots\) sayıları sırayla işlenir. Her sayı ondalık yazıya çevrilir ve basamakları soldan sağa okunur. Bir sayaç, Champernowne dizisindeki mevcut küresel konumu tutar. Ayrı bir gösterge ise henüz çözülmemiş bir sonraki hedefi işaret eder.
Temel invariant şudur: \(1\)'den \(n\)'e kadar olan sayılar işlendiğinde sayaç tam olarak \(L(n)\) değerine eşittir. Bu nedenle sayaç bir sonraki hedefe ulaştığı anda eldeki basamak tam olarak gereken \(d(10^p)\) değeridir ve çarpıma hemen dahil edilir.
Hedefler sıralı olduğundan, en büyük istenen konumdaki basamak işlenir işlenmez tarama sona erer. Bu problemde o sınır \(10^6\)'dır. O noktadan sonrası sonuca hiçbir katkı yapmaz.
Son ürün döndürülmeden önce her uygulama iki küçük örneği doğrulayabilir. \(10^2\)'ye kadar olan hedefler için sonuç \(5\) olmalıdır; yalnızca \(10^0\) istenirken sonuç \(1\) olmalıdır. Bu iki test hedef üretimini, akış mantığını ve çarpım güncellemesini birlikte sınar.
En büyük hedef \(10^m\) ise algoritma tam olarak \(10^m\) adet üretilmiş basamağı işler. Dolayısıyla çalışma süresi \(O(10^m)\) olur. Gerçek Project Euler örneğinde \(m=6\) olduğu için bu, bir milyon basamak ziyareti ve yalnızca \(185185\) sayısına kadar tarama anlamına gelir.
Ek bellek kullanımı hedef listesi için \(O(m)\), ayrıca o anda işlenen sayının ondalık gösterimi kadardır. Varsayılan örnekte bu pratikte sabit bellektir. Kritik nokta, tüm birleşik dizenin saklanmaması; basamakların ihtiyaç duyuldukça akış halinde üretilmesidir.
La constante de Champernowne en base 10 es \(C_{10}=0.1234567891011121314\ldots\), obtenida al concatenar los enteros positivos en orden. Si \(d(n)\) denota el \(n\)-esimo digito despues del punto decimal, hay que calcular el producto
$$d(1)\,d(10)\,d(100)\,d(1000)\,d(10000)\,d(100000)\,d(1000000).$$
La dificultad real no esta en multiplicar siete cifras, sino en localizar con precision esas siete posiciones dentro de una expansion decimal infinita.
Las implementaciones recorren de izquierda a derecha los digitos producidos por \(1,2,3,\ldots\). Esa estrategia funciona porque las posiciones pedidas son pocas, estan ordenadas y aparecen relativamente pronto. Para entenderlo, conviene descomponer la concatenacion por bloques de longitud fija.
Todos los enteros de \(k\) digitos forman un bloque contiguo. Hay \(9\cdot 10^{k-1}\) numeros de ese tipo y cada uno aporta \(k\) digitos, asi que el bloque contribuye
$$B_k=9k\cdot 10^{k-1}$$
digitos en total. Los primeros bloques aportan
$$B_1=9,\qquad B_2=180,\qquad B_3=2700,\qquad B_4=36000,\qquad B_5=450000.$$
Si definimos
$$S_m=\sum_{k=1}^{m} B_k,$$
entonces \(S_m\) es la cantidad total de digitos generados por todos los enteros de hasta \(m\) cifras. En particular,
$$S_5=9+180+2700+36000+450000=488889.$$
Por tanto, la posicion \(10^6\) cae dentro del bloque de numeros de 6 digitos.
Solo interesan las posiciones
$$T_p=10^p \qquad (p=0,1,\dots,6).$$
Como estos puntos de control estan estrictamente ordenados, basta un solo recorrido hacia adelante. Una vez procesados los primeros \(q\) digitos de la concatenacion, todos los objetivos \(\le q\) ya quedaron resueltos y todos los mayores siguen por delante. No hace falta volver atras ni acceder a la cadena de forma aleatoria.
Si el recorrido ya ha procesado todos los enteros desde \(1\) hasta un entero \(n\) de \(d\) digitos, entonces el numero de digitos emitidos es
$$L(n)=\sum_{k=1}^{d-1} 9k\cdot 10^{k-1}+d\bigl(n-10^{d-1}+1\bigr).$$
El codigo no evalua esta formula explicitamente, pero ella explica por que el barrido es tan pequeno. Como \(S_5=488889\), aun faltan
$$10^6-S_5=511111$$
digitos dentro del bloque de 6 cifras para alcanzar la posicion millon. Cada numero de 6 cifras aporta 6 digitos, asi que se necesitan
$$\left\lceil \frac{511111}{6} \right\rceil = 85186$$
numeros de ese bloque, y el recorrido termina en \(100000+85186-1=185185\).
La comprobacion pequena incluida en las implementaciones usa las posiciones \(1\), \(10\) y \(100\).
Para \(d(1)\), el valor es \(1\). Para \(d(10)\), los primeros 9 digitos vienen de \(1\) a \(9\), asi que el decimo digito es el primero de \(10\), de nuevo \(1\).
Para \(d(100)\), quitamos primero las 9 cifras del bloque de una cifra. Queda la posicion 91 dentro del bloque de dos cifras. Como cada numero de dos cifras aporta 2 digitos,
$$\left\lfloor \frac{91-1}{2} \right\rfloor = 45$$
indica que estamos en el numero de dos cifras numero 46, es decir \(10+45=55\). El desplazamiento dentro de \(55\) es
$$(91-1)\bmod 2=0,$$
por lo que el digito buscado es el primero de \(55\), o sea \(5\). En consecuencia,
$$d(1)\,d(10)\,d(100)=1\cdot 1\cdot 5=5,$$
que coincide exactamente con la verificacion pequena usada por las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma estrategia de flujo. No construyen el prefijo completo de un millon de digitos como una sola cadena. En cambio, recorren los enteros positivos en orden, exponen sus digitos decimales uno por uno y mantienen solo un estado minimo.
Primero se construye la lista finita \(1,10,100,\dots,10^m\), donde el valor por defecto es \(m=6\). Mientras esa lista se genera, la implementacion comprueba que multiplicar por 10 no provoque desbordamiento silencioso.
Despues, el programa recorre \(1,2,3,\ldots\). Cada entero se convierte a decimal y sus digitos se procesan de izquierda a derecha. Un contador mantiene la posicion global actual dentro de la constante de Champernowne, y otro indice apunta al siguiente objetivo aun no alcanzado.
La invariante principal es sencilla: despues de procesar todos los enteros hasta \(n\), el contador vale \(L(n)\), es decir, el numero total de digitos emitidos hasta ese momento. Por eso, cuando el contador coincide con el siguiente punto de control, el digito actual es exactamente el valor requerido \(d(10^p)\), y se multiplica de inmediato al producto acumulado.
Como los objetivos estan ordenados, el recorrido puede terminar en cuanto se consume el digito de la posicion mas grande solicitada. En el problema original, eso ocurre en la posicion \(10^6\). Ningun digito posterior puede cambiar la respuesta.
Antes de devolver el resultado final, cada implementacion puede verificar dos casos pequenos. Pedir objetivos solo hasta \(10^2\) debe producir \(5\), y pedir solo \(10^0\) debe producir \(1\). Esas dos pruebas validan de una sola vez la generacion de objetivos, la logica del flujo y la acumulacion multiplicativa.
Si el objetivo mas grande es \(10^m\), el algoritmo procesa exactamente \(10^m\) digitos emitidos, de modo que su tiempo es \(O(10^m)\). En la instancia de Project Euler, \(m=6\), lo que significa un millon de visitas de digitos y un recorrido solo hasta el entero \(185185\).
La memoria extra es \(O(m)\) para la lista de objetivos, mas la representacion decimal del entero actual. Para la entrada real eso es, en la practica, espacio constante. El punto importante es que el codigo transmite los digitos sobre la marcha en lugar de guardar todo el prefijo concatenado.
10 进制下的 Champernowne 常数是 \(C_{10}=0.1234567891011121314\ldots\)， 也就是把所有正整数按顺序直接拼接起来得到的小数。记小数点后的第 \(n\) 位为 \(d(n)\)，题目要求计算
$$d(1)\,d(10)\,d(100)\,d(1000)\,d(10000)\,d(100000)\,d(1000000)$$
真正的难点不是最后那次乘法，而是如何在一个无限长的十进制串中，准确而高效地取出这七个特定位置上的数字。
三份实现都采用同一种思路：按顺序扫描 \(1,2,3,\ldots\) 的十进制展开，在扫描位置碰到目标下标时就把当前数字乘进答案。这种做法之所以成立，是因为目标位置很稀疏，而且按从小到大的顺序出现。为了说明这一点，先把拼接后的数字流按位数分块。
所有 \(k\) 位正整数会在常数的十进制展开中形成一个连续块。这样的整数共有 \(9\cdot 10^{k-1}\) 个，每个整数贡献 \(k\) 个数字，因此这一块总共贡献
$$B_k=9k\cdot 10^{k-1}$$
个数字。前几块分别是
$$B_1=9,\qquad B_2=180,\qquad B_3=2700,\qquad B_4=36000,\qquad B_5=450000$$
若定义累计长度
$$S_m=\sum_{k=1}^{m} B_k,$$
那么 \(S_m\) 就表示所有位数不超过 \(m\) 的整数一共贡献了多少个数字。特别地，
$$S_5=9+180+2700+36000+450000=488889$$
这说明第 \(10^6\) 位其实已经落在 6 位数区间里，而不是要一直扫到非常大的整数。
题目只关心幂次为 10 的那些位置：
$$T_p=10^p \qquad (p=0,1,\dots,6)$$
这些位置严格递增，所以一次从左到右的扫描就足够了。假设当前已经读完拼接串的前 \(q\) 个数字，那么所有不超过 \(q\) 的目标位置都已经确定，而所有大于 \(q\) 的目标位置还没有到来。于是算法完全不需要回退，也不需要随机访问之前的数字。
如果扫描已经处理完从 \(1\) 到某个 \(d\) 位整数 \(n\) 的所有数字，那么已经输出的数字总数是
$$L(n)=\sum_{k=1}^{d-1} 9k\cdot 10^{k-1}+d\bigl(n-10^{d-1}+1\bigr)$$
实现本身并不会直接计算这个公式，但它能解释为什么顺序扫描已经足够快。因为 \(S_5=488889\)，所以到达第 \(10^6\) 位之前，在 6 位数区间中还需要
$$10^6-S_5=511111$$
个数字。每个 6 位数贡献 6 个数字，因此需要的 6 位数个数是
$$\left\lceil \frac{511111}{6} \right\rceil = 85186$$
也就是说，扫描最多只会走到 \(100000+85186-1=185185\)。这就是代码可以直接顺扫而不必设计更复杂随机定位公式的根本原因。
实现里的小型自检，正是要求位置 \(1\)、\(10\)、\(100\) 上数字的乘积。
\(d(1)=1\) 显然成立。对 \(d(10)\) 来说，前 9 个数字全部来自 \(1\) 到 \(9\)，因此第 10 个数字就是 \(10\) 的第一位，也仍然是 \(1\)。
再看 \(d(100)\)。先去掉 1 位数块的 9 个数字后，目标变成 2 位数块中的第 91 个数字。由于每个 2 位数贡献 2 个数字，
$$\left\lfloor \frac{91-1}{2} \right\rfloor = 45$$
说明目标落在第 46 个 2 位数里，也就是 \(10+45=55\)。在这个数内部的位置是
$$(91-1)\bmod 2=0$$
所以取的是 \(55\) 的第一位，即 \(5\)。于是
$$d(1)\,d(10)\,d(100)=1\cdot 1\cdot 5=5$$
这与三份实现中的检查结果完全一致。
C++、Python 和 Java 的实现都采用同一个流式算法。它们不会先构造一个长达一百万位的大字符串，而是逐个处理正整数，把当前整数的十进制表示拆成字符后立刻使用。
程序首先生成有限目标列表 \(1,10,100,\dots,10^m\)，默认取 \(m=6\)。在不断乘以 10 的过程中，实现会先检查是否存在整数溢出的风险，因此目标列表始终保持有效。
接下来，程序依次处理 \(1,2,3,\ldots\)。每遇到一个整数，就把它转换为十进制表示，并按从左到右的顺序处理每一位。一个计数器记录当前已经走到 Champernowne 常数的第几位，另一个索引指向下一个尚未命中的目标位置。
最关键的不变量是：当 \(1\) 到 \(n\) 的所有整数都处理完成后，位置计数器恰好等于 \(L(n)\)，也就是到此为止总共输出了多少个数字。因此，只要计数器刚好落在下一个目标位置上，当前正在看的那一位就一定是所需的 \(d(10^p)\)，可以立即乘入答案。
因为目标位置已经排好序，所以一旦最大目标位置上的数字被读取，算法就可以立刻结束。对原题而言，这个位置就是 \(10^6\)。后面的所有数字都不可能再影响结果。
在输出最终乘积之前，实现还可以先验证两个很小的例子。若只取到 \(10^2\)，结果必须是 \(5\)；若只取到 \(10^0\)，结果必须是 \(1\)。这两个检查同时覆盖了目标生成、数字流推进以及乘积累积三个核心部分。
若最大目标位置是 \(10^m\)，那么算法恰好处理 \(10^m\) 个已经输出的数字，因此时间复杂度是 \(O(10^m)\)。在本题中 \(m=6\)，也就是恰好访问一百万个数字，并且只需要扫描到整数 \(185185\)。
额外空间复杂度为 \(O(m)\)，用于保存目标列表，外加当前整数的十进制表示。在实际输入下，这几乎就是常数空间。真正重要的是：代码从头到尾都在流式处理数字，而不是保存完整的拼接前缀。
Константа Чамперноуна в десятичной записи имеет вид \(C_{10}=0.1234567891011121314\ldots\): после запятой подряд записаны все положительные целые числа. Если \(d(n)\) обозначает \(n\)-ю цифру после запятой, требуется вычислить произведение
$$d(1)\,d(10)\,d(100)\,d(1000)\,d(10000)\,d(100000)\,d(1000000).$$
Трудность здесь не в самом умножении, а в том, чтобы точно извлечь несколько специальных цифр из бесконечной конкатенации.
Все реализации идут слева направо по десятичной записи чисел \(1,2,3,\ldots\). Такая стратегия оправдана тем, что нужные позиции редки, упорядочены и достигаются довольно быстро. Чтобы это увидеть, удобно разбить запись по блокам одинаковой длины.
Все \(k\)-значные числа образуют один сплошной блок в записи константы. Таких чисел \(9\cdot 10^{k-1}\), и каждое дает \(k\) цифр. Значит, блок дает
$$B_k=9k\cdot 10^{k-1}$$
цифр. Для первых блоков получаем
$$B_1=9,\qquad B_2=180,\qquad B_3=2700,\qquad B_4=36000,\qquad B_5=450000.$$
Если ввести накопленную сумму
$$S_m=\sum_{k=1}^{m} B_k,$$
то \(S_m\) будет количеством цифр, порожденных всеми числами с не более чем \(m\) цифрами. В частности,
$$S_5=9+180+2700+36000+450000=488889.$$
Отсюда видно, что позиция \(10^6\) лежит уже в блоке шестизначных чисел.
Нас интересуют только позиции
$$T_p=10^p \qquad (p=0,1,\dots,6).$$
Они строго возрастают, поэтому достаточно одного линейного прохода. После обработки первых \(q\) цифр все цели \(\le q\) уже закрыты, а все большие цели еще впереди. Поэтому не нужен ни возврат назад, ни произвольный доступ к ранее просмотренным цифрам.
Если просмотрены все числа от \(1\) до некоторого \(d\)-значного числа \(n\), то общее число уже выданных цифр равно
$$L(n)=\sum_{k=1}^{d-1} 9k\cdot 10^{k-1}+d\bigl(n-10^{d-1}+1\bigr).$$
Код эту формулу не вычисляет напрямую, но она объясняет размер перебора. Поскольку \(S_5=488889\), до миллионной позиции не хватает еще
$$10^6-S_5=511111$$
цифр из блока шестизначных чисел. Каждое шестизначное число дает 6 цифр, значит, нужно
$$\left\lceil \frac{511111}{6} \right\rceil = 85186$$
таких чисел. Следовательно, проход заканчивается уже на числе \(100000+85186-1=185185\).
Маленькая проверка в реализациях использует позиции \(1\), \(10\) и \(100\).
Для \(d(1)\) ответ сразу равен \(1\). Для \(d(10)\) первые 9 цифр приходятся на числа от \(1\) до \(9\), так что 10-я цифра - это первая цифра числа \(10\), снова \(1\).
Для \(d(100)\) сначала убираем 9 цифр одноразрядного блока. Остается 91-я цифра внутри двухразрядного блока. Так как каждое двухразрядное число дает 2 цифры,
$$\left\lfloor \frac{91-1}{2} \right\rfloor = 45$$
означает, что нужная цифра находится в 46-м двухразрядном числе, то есть в \(10+45=55\). Смещение внутри этого числа равно
$$(91-1)\bmod 2=0,$$
поэтому нужна первая цифра числа \(55\), то есть \(5\). Значит,
$$d(1)\,d(10)\,d(100)=1\cdot 1\cdot 5=5,$$
и это в точности тот контрольный результат, который используют реализации.
Реализации на C++, Python и Java используют один и тот же потоковый подход. Они не строят весь префикс длины в миллион цифр как одну большую строку. Вместо этого они последовательно перебирают положительные целые числа и сразу обрабатывают цифры их десятичной записи.
Сначала строится конечный список позиций \(1,10,100,\dots,10^m\), где по умолчанию \(m=6\). При каждом умножении на 10 выполняется проверка на переполнение, чтобы список целей оставался корректным.
Затем программа идет по числам \(1,2,3,\ldots\). Каждое число переводится в десятичную форму, и его цифры читаются слева направо. Один счетчик хранит текущую глобальную позицию внутри константы Чамперноуна, а второй указатель помнит следующую еще не достигнутую цель.
Главный инвариант таков: после обработки всех чисел до \(n\) счетчик равен \(L(n)\), то есть общему количеству уже выданных цифр. Поэтому, как только счетчик попадает на следующую цель, текущая цифра и есть требуемое значение \(d(10^p)\), которое сразу умножается в ответ.
Так как цели отсортированы, проход можно завершить сразу после чтения цифры на самой большой нужной позиции. В исходной задаче это позиция \(10^6\). Все последующие цифры уже никак не влияют на результат.
Перед возвратом окончательного произведения каждая реализация может проверить два маленьких примера. Для целей до \(10^2\) ответ должен быть \(5\), а для единственной цели \(10^0\) ответ должен быть \(1\). Эти проверки одновременно тестируют генерацию целей, продвижение по потоку цифр и накопление произведения.
Если наибольшая запрошенная позиция равна \(10^m\), алгоритм обрабатывает ровно \(10^m\) выданных цифр, так что время работы равно \(O(10^m)\). В задаче Project Euler это \(m=6\), то есть ровно один миллион просмотренных цифр и проход только до числа \(185185\).
Дополнительная память составляет \(O(m)\) для списка целей плюс десятичная запись текущего числа. Для реального входа это фактически константная память. Ключевой практический момент в том, что цифры обрабатываются потоково и не сохраняется весь конкатенированный префикс.
ثابت تشامبرناون في الأساس العشري هو \(C_{10}=0.1234567891011121314\ldots\)، أي الناتج من كتابة جميع الأعداد الصحيحة الموجبة واحدًا بعد الآخر. إذا رمزنا إلى الرقم الواقع في الموضع \(n\) بعد الفاصلة العشرية بالرمز \(d(n)\)، فالمطلوب هو حساب حاصل الضرب
$$d(1)\,d(10)\,d(100)\,d(1000)\,d(10000)\,d(100000)\,d(1000000).$$
المسألة الحقيقية ليست في الضرب نفسه، بل في استخراج هذه الأرقام السبعة من سلسلة عشرية لا نهائية بطريقة دقيقة وفعالة.
التطبيقات الثلاثة تسير على النهج نفسه: نمر على الأعداد \(1,2,3,\ldots\) بالترتيب، ونفحص أرقامها العشرية من اليسار إلى اليمين، وكلما وصلنا إلى موضع مستهدف نضرب الرقم الحالي في الناتج. هذا النهج مناسب هنا لأن المواضع المطلوبة قليلة، ومرتبة تصاعديًا، ويمكن الوصول إليها بعد مسح قصير نسبيًا. لفهم ذلك بوضوح، من الأفضل تقسيم السلسلة إلى كتل بحسب عدد الخانات.
كل الأعداد ذات \(k\) خانات تشكل كتلة متجاورة داخل ثابت تشامبرناون. وعدد هذه الأعداد هو \(9\cdot 10^{k-1}\)، وكل عدد منها يساهم بـ \(k\) أرقام، ولذلك يكون مجموع ما تضيفه هذه الكتلة هو
$$B_k=9k\cdot 10^{k-1}.$$
وبالنسبة إلى أولى الكتل نحصل على
$$B_1=9,\qquad B_2=180,\qquad B_3=2700,\qquad B_4=36000,\qquad B_5=450000.$$
إذا عرفنا المجموع التراكمي
$$S_m=\sum_{k=1}^{m} B_k,$$
فإن \(S_m\) يعطي عدد الأرقام الناتجة من جميع الأعداد التي لا يزيد عدد خاناتها على \(m\). وعلى وجه الخصوص،
$$S_5=9+180+2700+36000+450000=488889.$$
وهذا يعني أن الموضع \(10^6\) يقع داخل كتلة الأعداد ذات 6 خانات، وليس بعيدًا جدًا داخل المتتالية.
المواضع الوحيدة التي تهمنا هي قوى العدد 10:
$$T_p=10^p \qquad (p=0,1,\dots,6).$$
هذه المواضع مرتبة تصاعديًا ترتيبًا صارمًا، ولذلك يكفي مرور واحد إلى الأمام. فإذا كنا قد عالجنا أول \(q\) أرقام من السلسلة، فإن كل هدف \(\le q\) قد حُسم نهائيًا، وكل هدف أكبر ما زال أمامنا. لهذا لا نحتاج إلى الرجوع إلى الخلف أو إلى تخزين سلسلة طويلة كاملة.
إذا وصل المسح إلى عدد \(n\) ذي \(d\) خانات، فإن عدد الأرقام التي خرجت حتى تلك اللحظة يساوي
$$L(n)=\sum_{k=1}^{d-1} 9k\cdot 10^{k-1}+d\bigl(n-10^{d-1}+1\bigr).$$
الشيفرة لا تحسب هذه الصيغة مباشرة، لكنها تشرح لماذا يكون المسح المباشر كافيًا. بما أن \(S_5=488889\)، فنحن ما زلنا بحاجة إلى
$$10^6-S_5=511111$$
رقمًا من كتلة الأعداد ذات 6 خانات حتى نصل إلى الموضع المليون. وكل عدد من هذه الأعداد يعطي 6 أرقام، لذا نحتاج إلى
$$\left\lceil \frac{511111}{6} \right\rceil = 85186$$
عددًا من تلك الكتلة. وبالتالي ينتهي المسح عند العدد \(100000+85186-1=185185\) فقط.
الفحص الصغير الموجود في التطبيقات يستخدم المواضع \(1\) و\(10\) و\(100\).
لدينا مباشرة \(d(1)=1\). أما \(d(10)\)، فالأرقام التسعة الأولى تأتي من \(1\) إلى \(9\)، ولذلك يكون الرقم العاشر هو أول رقم في \(10\)، أي \(1\) أيضًا.
وبالنسبة إلى \(d(100)\)، نحذف أولًا 9 أرقام الكتلة ذات الخانة الواحدة. يتبقى الموضع 91 داخل كتلة الأعداد ذات الخانتين. وبما أن كل عدد من هذه الأعداد يضيف رقمين، فإن
$$\left\lfloor \frac{91-1}{2} \right\rfloor = 45$$
يدل على أن الرقم المطلوب يقع داخل العدد ذي الخانتين رقم 46، أي \(10+45=55\). أما الإزاحة داخل هذا العدد فهي
$$(91-1)\bmod 2=0$$
أي أننا نأخذ الخانة الأولى من \(55\)، وهي \(5\). إذن
$$d(1)\,d(10)\,d(100)=1\cdot 1\cdot 5=5$$
وهذا يطابق تمامًا قيمة التحقق الصغيرة المستخدمة في جميع التطبيقات.
تطبيقات C++ وPython وJava كلها تستخدم خوارزمية تدفقية واحدة. فهي لا تبني البادئة الكاملة ذات المليون رقم كسلسلة واحدة، بل تمر على الأعداد الصحيحة الموجبة بالترتيب وتتعامل مع الأرقام العشرية لحظة ظهورها.
تبدأ الشيفرة ببناء القائمة النهائية \(1,10,100,\dots,10^m\)، حيث تكون القيمة الافتراضية \(m=6\). وخلال بناء هذه القائمة تُجرى حماية من تجاوز السعة قبل كل عملية ضرب في 10، حتى لا تنتج مواضع غير صالحة.
بعد ذلك يمر البرنامج على \(1,2,3,\ldots\). كل عدد يُحوَّل إلى تمثيله العشري، ثم تُفحص أرقامه من اليسار إلى اليمين. يوجد عداد يحتفظ بالموضع العالمي الحالي داخل ثابت تشامبرناون، كما يوجد مؤشر آخر يحدد الهدف التالي الذي لم يُحسم بعد.
الثابت الأساسي هنا هو التالي: بعد معالجة جميع الأعداد حتى \(n\)، يكون العداد مساويًا تمامًا لـ \(L(n)\)، أي لعدد الأرقام التي خرجت حتى الآن. لذلك، عندما يساوي العداد الهدف التالي، يكون الرقم الحالي هو بالضبط القيمة المطلوبة \(d(10^p)\)، ويمكن ضربه مباشرة في الناتج التراكمي.
بما أن الأهداف مرتبة، فإن المسح يتوقف مباشرة بعد قراءة الرقم الواقع عند أكبر موضع مطلوب. في المسألة الأصلية هذا الموضع هو \(10^6\). وكل ما يأتي بعده لا يمكن أن يغير الجواب.
قبل إرجاع الناتج النهائي، تستطيع كل نسخة من الشيفرة أن تتحقق من مثالين صغيرين. إذا طلبنا الأهداف حتى \(10^2\) فقط، فيجب أن يكون الناتج \(5\). وإذا طلبنا \(10^0\) فقط، فيجب أن يكون الناتج \(1\). هذان الاختباران يفحصان معًا توليد الأهداف، ومنطق المسح، وتجميع حاصل الضرب.
إذا كان أكبر هدف مطلوب هو \(10^m\)، فإن الخوارزمية تعالج بالضبط \(10^m\) رقمًا من السلسلة الناتجة، ومن ثم يكون زمن التنفيذ \(O(10^m)\). وفي مسألة Project Euler لدينا \(m=6\)، أي مليون زيارة للأرقام فقط، مع مسح لا يتجاوز العدد \(185185\).
استهلاك الذاكرة الإضافي هو \(O(m)\) لقائمة الأهداف، إضافة إلى التمثيل العشري للعدد الجاري معالجته. وبالنسبة إلى الإدخال الفعلي فهذا يُعد عمليًا ذاكرة ثابتة. النقطة العملية المهمة هي أن الشيفرة تبث الأرقام عند الحاجة بدلًا من تخزين البادئة المجمعة كاملة.