For a real number \(\theta > 1\), define \(b_1=\theta\) and then iterate
$$a_n=\lfloor b_n\rfloor,\qquad b_{n+1}=a_n\bigl(b_n-a_n+1\bigr).$$
The integer part \(a_1\) becomes the integer part of a decimal number, and every later value \(a_2,a_3,a_4,\ldots\) is written after the decimal point by direct concatenation. If one of these values has several digits, all of those digits are appended.
The goal is to find the fixed point for which this concatenated decimal equals the original \(\theta\), and then report that value rounded to 24 decimal places.
The recurrence generates a deterministic sequence of integers from any starting value \(\theta\). Writing \(d_k\) for the number of decimal digits of \(a_k\) when \(k\ge 2\), the concatenation map can be written as
$$\tau(\theta)=a_1+\sum_{k=2}^{\infty} a_k\,10^{-(d_2+d_3+\cdots+d_k)}.$$
So the problem becomes a fixed-point equation
$$\tau(\theta)=\theta.$$
Write
$$b_n=a_n+\delta_n,\qquad 0\le \delta_n<1.$$
Then the update rule becomes
$$b_{n+1}=a_n(1+\delta_n).$$
Because \(0\le \delta_n<1\), we immediately get the useful bound
$$a_n\le b_{n+1}<2a_n.$$
Taking floors shows that every next block is constrained by
$$a_{n+1}\in\{a_n,a_n+1,\ldots,2a_n-1\}.$$
This explains why the generated blocks grow in a controlled way rather than exploding unpredictably.
The decimal is not formed by ordinary place values of single digits, because the blocks \(a_n\) may have several digits. The exponent in the formula for \(\tau(\theta)\) therefore depends on cumulative digit lengths.
If, for example, the generated blocks begin
$$a_1=2,\quad a_2=3,\quad a_3=5,\quad a_4=8,\quad a_5=13,$$
then the concatenated value begins
$$2.35813\ldots$$
rather than \(2.3+0.05+0.008+\cdots\). The explicit digit-length formula above is the correct way to encode this concatenation mathematically.
Once \(\tau\) is defined, the natural numerical strategy is to iterate
$$\theta_{t+1}=\tau(\theta_t).$$
The implementations start from the practical seed \(2.2\). Repeated application of the concatenation map quickly stabilizes a long leading decimal prefix, and once many guard digits agree, the final 24-digit rounding is determined.
This is the central idea of the solution: instead of solving the fixed-point equation symbolically, it is solved numerically by repeatedly rebuilding the decimal number produced by the recurrence.
In practice we do not need the full infinite decimal expansion of \(\tau(\theta)\). If we stop after collecting \(D\) digits after the decimal point, we obtain a truncated value \(\tau_D(\theta)\).
Because truncating any positive decimal after \(D\) fractional digits changes its value by less than one unit in the next place, we have
$$0\le \tau(\theta)-\tau_D(\theta)<10^{-D}.$$
The implementations use \(D=80\), leaving a margin of 56 extra digits beyond the required 24. That makes the final rounding step numerically safe once the fixed-point iteration has stabilized.
A useful checkpoint is the sample starting value
$$\theta=2.956938891377988.$$
Then
$$b_1=2.956938891377988,\qquad a_1=\lfloor b_1\rfloor=2.$$
The next updates are
$$b_2=2(2.956938891377988-2+1)=3.913877782755976,\qquad a_2=3,$$
$$b_3=3(3.913877782755976-3+1)=5.741633348267928,\qquad a_3=5,$$
$$b_4=5(5.741633348267928-5+1)=8.70816674133964,\qquad a_4=8.$$
Continuing the same recurrence yields
$$a_5=13,\quad a_6=21,\quad a_7=34,\quad a_8=55,\quad a_9=89,\quad a_{10}=144.$$
So the concatenated decimal begins
$$\tau(\theta)=2.3581321345589144\ldots$$
This example is valuable because it shows exactly how multi-digit blocks such as \(13\), \(21\), and \(144\) are appended.
The C++, Python, and Java implementations all follow the same numerical plan. They work with high-precision decimal arithmetic, start from \(2.2\), generate the recurrence, and rebuild the concatenated decimal until 80 fractional digits have been collected. That truncated decimal becomes the next iterate.
The C++ and Java implementations perform this fixed-point iteration directly for 30 rounds and then round the final value to 24 decimal places. The Python entry point delegates to the same C++ computation, so its mathematical behavior is identical to the C++ version rather than being a separate algorithm.
Let \(P\) be the working number of fractional digits, \(K\) the number of generated blocks needed to reach that precision in one evaluation of \(\tau\), and \(I\) the number of fixed-point iterations. One evaluation performs \(K\) recurrence updates with \(P\)-digit decimal arithmetic and appends about \(P\) output characters overall, so a reasonable asymptotic description is \(O(IKP)\) time and \(O(P)\) memory. In the concrete implementations here, \(P=80\) and \(I=30\), so the computation is effectively constant-time for this single Project Euler instance.
Für eine reelle Zahl \(\theta > 1\) setzt man \(b_1=\theta\) und iteriert dann
$$a_n=\lfloor b_n\rfloor,\qquad b_{n+1}=a_n\bigl(b_n-a_n+1\bigr).$$
Der ganzzahlige Teil \(a_1\) wird zum ganzzahligen Teil einer Dezimalzahl, und alle späteren Werte \(a_2,a_3,a_4,\ldots\) werden ohne Trennzeichen hinter dem Dezimalpunkt aneinandergeschrieben. Hat ein Wert mehrere Ziffern, werden alle diese Ziffern übernommen.
Gesucht ist der Fixpunkt, bei dem diese konkatenierte Dezimalzahl wieder genau \(\theta\) ergibt; ausgegeben werden soll das Resultat auf 24 Nachkommastellen gerundet.
Die Rekursion erzeugt aus jedem Startwert \(\theta\) eine deterministische Folge ganzer Zahlen. Bezeichnet \(d_k\) die Anzahl der Dezimalziffern von \(a_k\) für \(k\ge 2\), dann lässt sich die Konkatenationsabbildung schreiben als
$$\tau(\theta)=a_1+\sum_{k=2}^{\infty} a_k\,10^{-(d_2+d_3+\cdots+d_k)}.$$
Damit wird die Aufgabe zur Fixpunktgleichung
$$\tau(\theta)=\theta.$$
Schreibe
$$b_n=a_n+\delta_n,\qquad 0\le \delta_n<1.$$
Dann wird die Update-Regel zu
$$b_{n+1}=a_n(1+\delta_n).$$
Aus \(0\le \delta_n<1\) folgt sofort die nützliche Abschätzung
$$a_n\le b_{n+1}<2a_n.$$
Nach dem Abrunden erhält man daher
$$a_{n+1}\in\{a_n,a_n+1,\ldots,2a_n-1\}.$$
Das erklärt, warum die erzeugten Blöcke zwar wachsen, aber nicht unkontrolliert springen.
Die Dezimalzahl entsteht nicht aus einzelnen Ziffern mit gewöhnlichen Stellenwerten, weil die Blöcke \(a_n\) mehrere Ziffern haben können. Deshalb hängt der Exponent in der Formel für \(\tau(\theta)\) von den kumulierten Ziffernlängen ab.
Beginnen die erzeugten Blöcke beispielsweise mit
$$a_1=2,\quad a_2=3,\quad a_3=5,\quad a_4=8,\quad a_5=13,$$
dann beginnt die Konkatenation mit
$$2.35813\ldots$$
und nicht mit einer Summe wie \(2.3+0.05+0.008+\cdots\). Genau deshalb ist die explizite Formel mit den Ziffernlängen mathematisch korrekt.
Ist \(\tau\) einmal definiert, liegt die numerische Strategie nahe:
$$\theta_{t+1}=\tau(\theta_t).$$
Die Implementierungen starten mit dem praktischen Anfangswert \(2.2\). Durch wiederholtes Anwenden der Konkatenationsabbildung stabilisiert sich ein langer führender Dezimalpräfix sehr schnell; sobald genügend Schutzstellen übereinstimmen, ist auch die Rundung auf 24 Stellen festgelegt.
Der Kern der Lösung besteht also darin, die Fixpunktgleichung nicht symbolisch, sondern durch wiederholten Neuaufbau der von der Rekursion erzeugten Dezimalzahl numerisch zu lösen.
In der Praxis braucht man die unendliche Dezimalentwicklung von \(\tau(\theta)\) nicht vollständig. Stoppt man nach \(D\) Nachkommastellen, erhält man einen abgeschnittenen Wert \(\tau_D(\theta)\).
Da das Abschneiden einer positiven Dezimalzahl nach \(D\) Stellen den Wert um weniger als eine Einheit der nächsten Stelle verändert, gilt
$$0\le \tau(\theta)-\tau_D(\theta)<10^{-D}.$$
Die Implementierungen verwenden \(D=80\) und besitzen damit 56 Schutzstellen mehr als für die geforderten 24 Nachkommastellen nötig sind. Sobald die Iteration stabil ist, ist die Schlussrundung also numerisch sicher.
Ein nützlicher Kontrollwert ist
$$\theta=2.956938891377988.$$
Dann gilt
$$b_1=2.956938891377988,\qquad a_1=\lfloor b_1\rfloor=2.$$
Die nächsten Schritte sind
$$b_2=2(2.956938891377988-2+1)=3.913877782755976,\qquad a_2=3,$$
$$b_3=3(3.913877782755976-3+1)=5.741633348267928,\qquad a_3=5,$$
$$b_4=5(5.741633348267928-5+1)=8.70816674133964,\qquad a_4=8.$$
Setzt man die Rekursion fort, erhält man
$$a_5=13,\quad a_6=21,\quad a_7=34,\quad a_8=55,\quad a_9=89,\quad a_{10}=144.$$
Die konkatenierte Dezimalzahl beginnt also mit
$$\tau(\theta)=2.3581321345589144\ldots$$
Dieses Beispiel zeigt besonders deutlich, wie mehrstellige Blöcke wie \(13\), \(21\) und \(144\) angehängt werden.
Die C++-, Python- und Java-Implementierungen folgen demselben numerischen Plan. Sie arbeiten mit hochpräziser Dezimalarithmetik, starten bei \(2.2\), erzeugen die Rekursion und bauen die konkatenierte Dezimalzahl neu auf, bis 80 Nachkommastellen gesammelt wurden. Diese abgeschnittene Dezimalzahl wird dann zum nächsten Iterationswert.
Die C++- und Java-Implementierungen führen diese Fixpunktiteration direkt 30 Runden lang aus und runden erst danach auf 24 Nachkommastellen. Der Python-Einstieg delegiert dieselbe C++-Berechnung, sodass sein mathematisches Verhalten mit der C++-Version identisch ist und keinen separaten Algorithmus darstellt.
Sei \(P\) die Arbeitspräzision in Nachkommastellen, \(K\) die Zahl erzeugter Blöcke pro Auswertung von \(\tau\) und \(I\) die Zahl der Fixpunktiterationen. Eine Auswertung benötigt \(K\) Rekursionsschritte mit \(P\)-stelliger Dezimalarithmetik und erzeugt insgesamt ungefähr \(P\) Ausgabestellen. Eine passende asymptotische Beschreibung ist daher \(O(IKP)\) Zeit und \(O(P)\) Speicher. In den konkreten Implementierungen gilt hier \(P=80\) und \(I=30\), also ist die Laufzeit für diese einzelne Project-Euler-Aufgabe praktisch konstant.
Bir \(\theta > 1\) reel sayısı için önce \(b_1=\theta\) alınır ve ardından
$$a_n=\lfloor b_n\rfloor,\qquad b_{n+1}=a_n\bigl(b_n-a_n+1\bigr)$$
özyinelemesi uygulanır. \(a_1\) değeri oluşacak ondalık sayının tam kısmı olur; \(a_2,a_3,a_4,\ldots\) değerleri ise hiçbir ayraç kullanılmadan ondalık noktadan sonra art arda yazılır. Bir terim birden fazla basamaklıysa, o terimin bütün basamakları eklenir.
Aranan şey, bu şekilde elde edilen ondalık sayının yeniden \(\theta\) olduğu sabit noktadır. Sonuç 24 ondalık basamağa yuvarlanmış olarak istenir.
Bu özyineleme, her başlangıç değeri \(\theta\) için deterministik bir tam sayı dizisi üretir. \(k\ge 2\) için \(a_k\)'nın ondalık basamak sayısını \(d_k\) ile gösterirsek, birleştirme operatörü
$$\tau(\theta)=a_1+\sum_{k=2}^{\infty} a_k\,10^{-(d_2+d_3+\cdots+d_k)}$$
şeklinde yazılır. Böylece problem
$$\tau(\theta)=\theta$$
sabit nokta denklemine dönüşür.
Şunu yazalım:
$$b_n=a_n+\delta_n,\qquad 0\le \delta_n<1.$$
Böylece güncelleme kuralı
$$b_{n+1}=a_n(1+\delta_n)$$
olur. \(0\le \delta_n<1\) olduğu için hemen şu sınır gelir:
$$a_n\le b_{n+1}<2a_n.$$
Taban alma işleminden sonra
$$a_{n+1}\in\{a_n,a_n+1,\ldots,2a_n-1\}$$
elde edilir. Bu sonuç önemlidir; üretilen bloklar büyür ama gelişigüzel sıçramaz.
Oluşan ondalık sayı, tek tek rakamların klasik basamak değerleriyle kurulmaz; çünkü \(a_n\) blokları birden fazla basamaklı olabilir. Bu nedenle \(\tau(\theta)\) formülündeki üsler, biriken basamak sayılarından oluşur.
Örneğin bloklar
$$a_1=2,\quad a_2=3,\quad a_3=5,\quad a_4=8,\quad a_5=13$$
ile başlıyorsa birleşik sayı
$$2.35813\ldots$$
şeklinde başlar; bu ifade \(2.3+0.05+0.008+\cdots\) değildir. Doğru matematiksel tanım ancak toplam basamak uzunluklarını kullanan formülle verilir.
\(\tau\) tanımlandıktan sonra doğal sayısal strateji
$$\theta_{t+1}=\tau(\theta_t)$$
iterasyonudur. Uygulamalar pratik başlangıç değeri olarak \(2.2\) kullanır. Birleştirme operatörü tekrar tekrar uygulandığında uzun bir ön ek hızla kararlı hale gelir; yeterli sayıda koruma basamağı aynı kaldığında 24 basamaklık son yuvarlama da belirlenmiş olur.
Dolayısıyla çözümün özü, sabit nokta denklemini sembolik olarak çözmek değil, özyinelemenin ürettiği ondalık sayıyı tekrar tekrar inşa ederek sayısal olarak dengeye getirmektir.
Pratikte \(\tau(\theta)\)'nın sonsuz ondalık açılımının tamamına gerek yoktur. Ondalık noktadan sonra \(D\) basamak toplandığında, kesilmiş değer \(\tau_D(\theta)\) elde edilir.
Pozitif bir ondalık sayı \(D\) basamakta kesildiğinde hata bir sonraki basamağın bir biriminden küçüktür; dolayısıyla
$$0\le \tau(\theta)-\tau_D(\theta)<10^{-D}$$
geçerlidir. Uygulamalar \(D=80\) kullanır; yani istenen 24 basamağın üstünde 56 koruma basamağı vardır. İterasyon kararlı hale geldiğinde son yuvarlama güvenlidir.
Yararlı bir kontrol örneği şudur:
$$\theta=2.956938891377988.$$
Buradan
$$b_1=2.956938891377988,\qquad a_1=\lfloor b_1\rfloor=2$$
elde edilir. Sonraki adımlar ise
$$b_2=2(2.956938891377988-2+1)=3.913877782755976,\qquad a_2=3,$$
$$b_3=3(3.913877782755976-3+1)=5.741633348267928,\qquad a_3=5,$$
$$b_4=5(5.741633348267928-5+1)=8.70816674133964,\qquad a_4=8.$$
Aynı özyineleme sürdürüldüğünde
$$a_5=13,\quad a_6=21,\quad a_7=34,\quad a_8=55,\quad a_9=89,\quad a_{10}=144$$
elde edilir. Bu yüzden birleşik ondalık sayı
$$\tau(\theta)=2.3581321345589144\ldots$$
şeklinde başlar. Bu örnek, \(13\), \(21\) ve \(144\) gibi çok basamaklı blokların nasıl eklendiğini açıkça gösterir.
C++, Python ve Java uygulamaları aynı sayısal planı izler. Yüksek hassasiyetli ondalık aritmetik kullanırlar, \(2.2\) ile başlarlar, özyinelemeyi üretirler ve 80 kesir basamağı toplanana kadar birleşik ondalık sayıyı yeniden kurarlar. Elde edilen kesilmiş ondalık değer bir sonraki iterasyon girdisi olur.
C++ ve Java uygulamaları bu sabit nokta iterasyonunu doğrudan 30 tur uygular, ardından sonucu 24 ondalık basamağa yuvarlar. Python girişi ise aynı C++ hesabını çağırır; dolayısıyla matematiksel davranışı C++ sürümüyle aynıdır, ayrı bir algoritma değildir.
\(P\) çalışma hassasiyetini, \(K\) bir \(\tau\) değerlendirmesinde gereken blok sayısını ve \(I\) sabit nokta iterasyon sayısını göstersin. Bir değerlendirme, \(P\) basamaklı ondalık aritmetikle \(K\) özyineleme adımı yapar ve toplamda yaklaşık \(P\) karakterlik çıktı üretir. Bu nedenle uygun bir asimptotik özet \(O(IKP)\) zaman ve \(O(P)\) bellek kullanımıdır. Buradaki somut uygulamalarda \(P=80\) ve \(I=30\) olduğundan, bu tek Project Euler problemi için çalışma süresi pratikte sabittir.
Para un número real \(\theta > 1\), se define \(b_1=\theta\) y luego se itera
$$a_n=\lfloor b_n\rfloor,\qquad b_{n+1}=a_n\bigl(b_n-a_n+1\bigr).$$
El valor \(a_1\) pasa a ser la parte entera de un número decimal, y los valores posteriores \(a_2,a_3,a_4,\ldots\) se escriben uno detrás de otro después del punto decimal. Si alguno tiene varias cifras, se añaden todas esas cifras.
La tarea consiste en encontrar el punto fijo para el cual ese decimal concatenado vuelve a coincidir con \(\theta\), y dar la respuesta redondeada a 24 cifras decimales.
La recurrencia produce una sucesión determinista de enteros a partir de cualquier valor inicial \(\theta\). Si \(d_k\) es el número de cifras decimales de \(a_k\) para \(k\ge 2\), el operador de concatenación puede escribirse como
$$\tau(\theta)=a_1+\sum_{k=2}^{\infty} a_k\,10^{-(d_2+d_3+\cdots+d_k)}.$$
Por lo tanto, el problema queda reformulado como la ecuación de punto fijo
$$\tau(\theta)=\theta.$$
Escribimos
$$b_n=a_n+\delta_n,\qquad 0\le \delta_n<1.$$
Entonces la actualización se convierte en
$$b_{n+1}=a_n(1+\delta_n).$$
Como \(0\le \delta_n<1\), se obtiene inmediatamente
$$a_n\le b_{n+1}<2a_n.$$
Al tomar partes enteras resulta
$$a_{n+1}\in\{a_n,a_n+1,\ldots,2a_n-1\}.$$
Esto muestra que los bloques generados crecen de forma controlada y no de manera caótica.
El decimal no se construye con valores posicionales ordinarios de cifras sueltas, porque los bloques \(a_n\) pueden tener varias cifras. Por eso el exponente en la fórmula de \(\tau(\theta)\) depende de la suma acumulada de longitudes decimales.
Si, por ejemplo, los bloques iniciales son
$$a_1=2,\quad a_2=3,\quad a_3=5,\quad a_4=8,\quad a_5=13,$$
el decimal concatenado empieza como
$$2.35813\ldots$$
y no como una suma del tipo \(2.3+0.05+0.008+\cdots\). La fórmula con longitudes de bloque es la forma correcta de describir la concatenación.
Una vez definido \(\tau\), la estrategia numérica natural es iterar
$$\theta_{t+1}=\tau(\theta_t).$$
Las implementaciones comienzan con la semilla práctica \(2.2\). Al aplicar repetidamente el operador de concatenación, un prefijo decimal largo se estabiliza con rapidez; cuando suficientes cifras de guarda coinciden, el redondeo final a 24 posiciones ya queda fijado.
La esencia de la solución es, por tanto, resolver la ecuación de punto fijo numéricamente reconstruyendo una y otra vez el decimal producido por la recurrencia.
En la práctica no hace falta construir toda la expansión infinita de \(\tau(\theta)\). Si se detiene el proceso tras obtener \(D\) cifras después del punto decimal, se obtiene un valor truncado \(\tau_D(\theta)\).
Como al truncar un decimal positivo tras \(D\) cifras fraccionarias se comete un error menor que una unidad en la siguiente posición, se cumple
$$0\le \tau(\theta)-\tau_D(\theta)<10^{-D}.$$
Las implementaciones usan \(D=80\), es decir, 56 cifras de seguridad más allá de las 24 pedidas. Con esa reserva, el redondeo final es seguro una vez estabilizada la iteración.
Un control útil es el valor
$$\theta=2.956938891377988.$$
Entonces
$$b_1=2.956938891377988,\qquad a_1=\lfloor b_1\rfloor=2.$$
Los siguientes pasos son
$$b_2=2(2.956938891377988-2+1)=3.913877782755976,\qquad a_2=3,$$
$$b_3=3(3.913877782755976-3+1)=5.741633348267928,\qquad a_3=5,$$
$$b_4=5(5.741633348267928-5+1)=8.70816674133964,\qquad a_4=8.$$
Al continuar con la misma recurrencia se obtiene
$$a_5=13,\quad a_6=21,\quad a_7=34,\quad a_8=55,\quad a_9=89,\quad a_{10}=144.$$
Por eso el decimal concatenado comienza como
$$\tau(\theta)=2.3581321345589144\ldots$$
Este ejemplo deja claro cómo se incorporan bloques de varias cifras como \(13\), \(21\) y \(144\).
Las implementaciones en C++, Python y Java siguen el mismo plan numérico. Trabajan con aritmética decimal de alta precisión, parten de \(2.2\), generan la recurrencia y reconstruyen el decimal concatenado hasta reunir 80 cifras fraccionarias. Ese decimal truncado se usa como siguiente iterado.
Las versiones en C++ y Java ejecutan directamente 30 rondas de esta iteración de punto fijo y solo después redondean a 24 cifras decimales. La entrada de Python delega en el mismo cálculo de C++, de modo que su comportamiento matemático coincide con el de la versión en C++ y no representa un algoritmo distinto.
Sea \(P\) el número de cifras fraccionarias de trabajo, \(K\) el número de bloques generados en una evaluación de \(\tau\) y \(I\) el número de iteraciones de punto fijo. Cada evaluación realiza \(K\) actualizaciones de la recurrencia con aritmética decimal de \(P\) cifras y produce en total unas \(P\) cifras de salida. Una descripción asintótica razonable es \(O(IKP)\) en tiempo y \(O(P)\) en memoria. En las implementaciones concretas de este problema, \(P=80\) e \(I=30\), así que el coste real es prácticamente constante.
对任意实数 \(\theta > 1\)，先定义 \(b_1=\theta\)，然后按如下递推：
$$a_n=\lfloor b_n\rfloor,\qquad b_{n+1}=a_n\bigl(b_n-a_n+1\bigr).$$
\(a_1\) 作为最终十进制数的整数部分，而后面的 \(a_2,a_3,a_4,\ldots\) 则直接顺次拼接到小数点后面。如果某一项本身是多位数，那么它的所有数字都会完整拼进去。
题目要求找到这样一个不动点：由这套递推生成并拼接出的十进制数，恰好又等于原来的 \(\theta\)。最后把该值四舍五入到 24 位小数。
这组递推从任意起始值 \(\theta\) 出发都会生成一个确定的整数序列。记 \(k\ge 2\) 时 \(a_k\) 的十进制位数为 \(d_k\)，那么拼接算子可以写成
$$\tau(\theta)=a_1+\sum_{k=2}^{\infty} a_k\,10^{-(d_2+d_3+\cdots+d_k)}.$$
于是原问题就变成了求解不动点方程
$$\tau(\theta)=\theta.$$
把 \(b_n\) 写成整数部分加小数部分：
$$b_n=a_n+\delta_n,\qquad 0\le \delta_n<1.$$
代回递推式后得到
$$b_{n+1}=a_n(1+\delta_n).$$
因为 \(0\le \delta_n<1\)，所以立刻有
$$a_n\le b_{n+1}<2a_n.$$
再取整便得到
$$a_{n+1}\in\{a_n,a_n+1,\ldots,2a_n-1\}.$$
这说明每一步生成的新整数块虽然会增长，但增长范围是受控的，不会出现完全无规律的跳跃。这个观察非常重要，因为后续的十进制拼接正是由这些整数块组成的。
这里的十进制数不是把单个数字按普通位权相加得到的，因为 \(a_n\) 可能是 \(13\)、\(144\) 这样的多位整数。因此，某一项贡献到十进制展开中的位置，取决于前面所有块一共占了多少位。
如果前几项是
$$a_1=2,\quad a_2=3,\quad a_3=5,\quad a_4=8,\quad a_5=13,$$
那么拼接后的结果开头是
$$2.35813\ldots$$
而不是 \(2.3+0.05+0.008+\cdots\)。正因为如此，\(\tau(\theta)\) 的定义必须显式使用累计位数 \(d_2+d_3+\cdots+d_k\)，这也是上面那条公式的含义。
既然已经得到了算子 \(\tau\)，最自然的做法就是反复应用它：
$$\theta_{t+1}=\tau(\theta_t).$$
实现中从 \(2.2\) 这个实用初值开始。随后每做一次迭代，就根据当前的 \(\theta_t\) 重新生成整数组块，再把这些块拼成新的十进制数作为 \(\theta_{t+1}\)。实验上可以看到，前面的很长一段十进制前缀会很快稳定下来；一旦稳定的位数明显超过题目要求的 24 位，那么最终四舍五入的结果也就固定了。
换句话说，程序并不是先推导一个闭式表达式，而是直接把“由 \(\theta\) 生成十进制，再令它等于 \(\theta\)”这件事做成不动点迭代。
真正计算时没有必要把 \(\tau(\theta)\) 的无限小数完全展开。只要在小数点后收集到 \(D\) 位，就可以得到一个截断版本 \(\tau_D(\theta)\)。
由于正十进制数在第 \(D\) 位后直接截断，误差一定小于下一位的一个单位，因此有
$$0\le \tau(\theta)-\tau_D(\theta)<10^{-D}.$$
实现里使用的是 \(D=80\)。题目只要求 24 位小数，所以这里额外保留了 56 位保护位。只要迭代已经稳定到这个深度，最终把结果四舍五入到 24 位就是安全的。
有一个很好的检验样例：
$$\theta=2.956938891377988.$$
首先
$$b_1=2.956938891377988,\qquad a_1=\lfloor b_1\rfloor=2.$$
接下来几步分别是
$$b_2=2(2.956938891377988-2+1)=3.913877782755976,\qquad a_2=3,$$
$$b_3=3(3.913877782755976-3+1)=5.741633348267928,\qquad a_3=5,$$
$$b_4=5(5.741633348267928-5+1)=8.70816674133964,\qquad a_4=8.$$
继续递推下去会得到
$$a_5=13,\quad a_6=21,\quad a_7=34,\quad a_8=55,\quad a_9=89,\quad a_{10}=144.$$
因此拼接出来的小数开头是
$$\tau(\theta)=2.3581321345589144\ldots$$
这个例子非常直观，因为它清楚地展示了多位块 \(13\)、\(21\)、\(144\) 是如何被完整拼接进十进制展开中的。
C++、Python 和 Java 三个实现遵循同一套数值思路。它们使用高精度十进制运算，从 \(2.2\) 出发，不断生成递推序列，并把得到的整数块重新拼成一个新的十进制数，直到收集满 80 位小数。这个截断后的十进制数就作为下一轮迭代的输入。
C++ 与 Java 版本直接执行 30 轮这样的不动点更新，然后再把最终结果四舍五入到 24 位小数。Python 入口则复用了同一份 C++ 计算核心，所以它在数学上与 C++ 版本完全一致，并不是另一套独立算法。
设工作小数位数为 \(P\)，一次 \(\tau\) 计算中为了凑满这些位数而需要生成的整数组块个数为 \(K\)，固定点迭代轮数为 \(I\)。一次迭代需要做 \(K\) 次递推更新，并在 \(P\) 位精度下进行高精度十进制运算，同时总共拼接出大约 \(P\) 个字符。因此一个合理的渐近描述是时间复杂度 \(O(IKP)\)，空间复杂度 \(O(P)\)。在当前实现里，\(P=80\)、\(I=30\) 都是固定常数，所以对这道题来说运行代价实际上近似常数。
Для вещественного числа \(\theta > 1\) задается \(b_1=\theta\), после чего выполняется рекурсия
$$a_n=\lfloor b_n\rfloor,\qquad b_{n+1}=a_n\bigl(b_n-a_n+1\bigr).$$
Число \(a_1\) становится целой частью десятичной записи, а значения \(a_2,a_3,a_4,\ldots\) последовательно приписываются после десятичной точки. Если очередной блок многозначный, в запись попадают все его цифры.
Нужно найти такую неподвижную точку, при которой получившееся десятичное число снова равно \(\theta\), и затем округлить результат до 24 знаков после запятой.
Рекурсия порождает из каждого стартового значения \(\theta\) вполне определенную последовательность целых чисел. Обозначим через \(d_k\) количество десятичных цифр в \(a_k\) при \(k\ge 2\). Тогда оператор конкатенации можно записать так:
$$\tau(\theta)=a_1+\sum_{k=2}^{\infty} a_k\,10^{-(d_2+d_3+\cdots+d_k)}.$$
Тем самым исходная задача превращается в уравнение на неподвижную точку
$$\tau(\theta)=\theta.$$
Представим \(b_n\) в виде
$$b_n=a_n+\delta_n,\qquad 0\le \delta_n<1.$$
Тогда правило обновления принимает вид
$$b_{n+1}=a_n(1+\delta_n).$$
Из условия \(0\le \delta_n<1\) немедленно следует оценка
$$a_n\le b_{n+1}<2a_n.$$
После взятия целой части получаем
$$a_{n+1}\in\{a_n,a_n+1,\ldots,2a_n-1\}.$$
Это объясняет, почему последовательность блоков растет управляемо и не делает произвольных скачков.
Здесь нельзя использовать обычную позиционную интерпретацию отдельных цифр, потому что блоки \(a_n\) могут быть многозначными. Поэтому положение очередного блока в десятичной записи определяется суммарной длиной всех предыдущих блоков.
Если, например, начало последовательности таково:
$$a_1=2,\quad a_2=3,\quad a_3=5,\quad a_4=8,\quad a_5=13,$$
то конкатенация начинается как
$$2.35813\ldots$$
а не как сумма вида \(2.3+0.05+0.008+\cdots\). Именно поэтому формула для \(\tau(\theta)\) должна явно учитывать длины блоков.
После определения оператора \(\tau\) естественно использовать итерационную схему
$$\theta_{t+1}=\tau(\theta_t).$$
В реализации в качестве практического начального значения берется \(2.2\). При повторном применении оператора длинный ведущий десятичный префикс быстро стабилизируется; когда совпадает достаточно много защитных цифр, окончательное округление до 24 знаков уже однозначно определено.
Иными словами, решение строится не через символическое замыкание, а через многократное пересобирание десятичного числа, которое сама рекурсия и порождает.
На практике бесконечное десятичное разложение \(\tau(\theta)\) целиком не нужно. Если остановиться после \(D\) цифр после запятой, получим усеченный вариант \(\tau_D(\theta)\).
Поскольку усечение положительного десятичного числа после \(D\) дробных цифр меняет его менее чем на единицу следующего разряда, имеем
$$0\le \tau(\theta)-\tau_D(\theta)<10^{-D}.$$
В реализациях используется \(D=80\), то есть имеется запас в 56 цифр сверх требуемых 24. Поэтому после стабилизации итераций финальное округление оказывается надежным.
Полезная контрольная точка:
$$\theta=2.956938891377988.$$
Сначала получаем
$$b_1=2.956938891377988,\qquad a_1=\lfloor b_1\rfloor=2.$$
Дальнейшие шаги таковы:
$$b_2=2(2.956938891377988-2+1)=3.913877782755976,\qquad a_2=3,$$
$$b_3=3(3.913877782755976-3+1)=5.741633348267928,\qquad a_3=5,$$
$$b_4=5(5.741633348267928-5+1)=8.70816674133964,\qquad a_4=8.$$
Если продолжить рекурсию, выйдет
$$a_5=13,\quad a_6=21,\quad a_7=34,\quad a_8=55,\quad a_9=89,\quad a_{10}=144.$$
Следовательно, десятичная конкатенация начинается так:
$$\tau(\theta)=2.3581321345589144\ldots$$
Этот пример особенно полезен тем, что наглядно показывает, как в десятичную запись целиком вставляются многозначные блоки \(13\), \(21\) и \(144\).
Реализации на C++, Python и Java следуют одному и тому же численному плану. Они используют высокоточную десятичную арифметику, стартуют с \(2.2\), порождают рекурсию и заново собирают десятичную конкатенацию, пока не накопят 80 цифр после запятой. Полученное усеченное число становится следующим приближением.
Версии на C++ и Java напрямую выполняют 30 раундов такой итерации неподвижной точки, а затем округляют результат до 24 знаков после запятой. Python-вход использует тот же вычислительный механизм на C++, поэтому математически ведет себя так же, как версия на C++, а не как отдельный независимый алгоритм.
Пусть \(P\) обозначает рабочее число дробных цифр, \(K\) — число сгенерированных блоков в одной оценке \(\tau\), а \(I\) — число итераций неподвижной точки. Одна оценка требует \(K\) рекуррентных обновлений с десятичной арифметикой точности \(P\) и в сумме формирует примерно \(P\) символов вывода. Поэтому разумная асимптотическая оценка имеет вид \(O(IKP)\) по времени и \(O(P)\) по памяти. В текущих реализациях \(P=80\) и \(I=30\), так что для данной задачи Project Euler реальная стоимость вычисления практически постоянна.
لأي عدد حقيقي \(\theta > 1\)، نعرّف أولاً \(b_1=\theta\)، ثم نطبّق العلاقة التكرارية
$$a_n=\lfloor b_n\rfloor,\qquad b_{n+1}=a_n\bigl(b_n-a_n+1\bigr).$$
تصير القيمة \(a_1\) هي الجزء الصحيح من عدد عشري، ثم تُكتب القيم اللاحقة \(a_2,a_3,a_4,\ldots\) متتابعة بعد الفاصلة العشرية من دون فواصل. وإذا كانت إحدى هذه القيم مكوّنة من أكثر من خانة، فإن جميع خاناتها تُلحق كما هي.
المطلوب هو إيجاد نقطة التثبيت التي يكون عندها هذا العدد العشري الناتج من الدمج مساوياً مرة أخرى لـ \(\theta\)، ثم إعطاء النتيجة مقربة إلى 24 خانة عشرية.
هذه العلاقة التكرارية تولّد من كل قيمة ابتدائية \(\theta\) متتالية محددة من الأعداد الصحيحة. إذا رمزنا بعدد الخانات العشرية في \(a_k\) عندما \(k\ge 2\) بالرمز \(d_k\)، فإن مؤثر الدمج يمكن كتابته على الصورة
$$\tau(\theta)=a_1+\sum_{k=2}^{\infty} a_k\,10^{-(d_2+d_3+\cdots+d_k)}.$$
وهكذا تتحول المسألة إلى معادلة نقطة تثبيت:
$$\tau(\theta)=\theta.$$
نكتب
$$b_n=a_n+\delta_n,\qquad 0\le \delta_n<1.$$
فتصبح قاعدة التحديث
$$b_{n+1}=a_n(1+\delta_n).$$
ومن الشرط \(0\le \delta_n<1\) نستنتج مباشرة أن
$$a_n\le b_{n+1}<2a_n.$$
وبأخذ الجزء الصحيح نحصل على
$$a_{n+1}\in\{a_n,a_n+1,\ldots,2a_n-1\}.$$
وهذا يوضح أن الكتل الصحيحة الناتجة تنمو بطريقة مضبوطة، لا بعشوائية كاملة.
العدد العشري هنا لا يتكون من أرقام منفردة ذات أوزان موضعية عادية، لأن الكتل \(a_n\) قد تكون متعددة الخانات. لذلك فإن موضع كل كتلة في التمثيل العشري يعتمد على مجموع أطوال الكتل السابقة.
فإذا بدأت الكتل مثلاً بالشكل
$$a_1=2,\quad a_2=3,\quad a_3=5,\quad a_4=8,\quad a_5=13,$$
فإن العدد الناتج يبدأ هكذا
$$2.35813\ldots$$
وليس على صورة مجموع من نوع \(2.3+0.05+0.008+\cdots\). ولهذا السبب يجب أن يعتمد التعريف الصحيح لـ \(\tau(\theta)\) على أطوال الكتل المتراكمة.
بعد تعريف \(\tau\)، تصبح الاستراتيجية العددية الطبيعية هي التكرار
$$\theta_{t+1}=\tau(\theta_t).$$
تبدأ التطبيقات من القيمة العملية \(2.2\). ومع التكرار المتتابع لمؤثر الدمج يستقر بادئ عشري طويل بسرعة؛ وحين تتطابق خانات حماية كافية، تصبح عملية التقريب النهائية إلى 24 خانة محددة بشكل ثابت.
وبالتالي فجوهر الحل ليس استخراج صيغة مغلقة، بل حل معادلة نقطة التثبيت عددياً عبر إعادة بناء العدد العشري الذي تولّده العلاقة التكرارية مرة بعد مرة.
عملياً لا نحتاج إلى التوسع العشري اللانهائي الكامل لـ \(\tau(\theta)\). إذا توقفنا بعد جمع \(D\) خانات بعد الفاصلة، حصلنا على نسخة مقطوعة نرمز لها بـ \(\tau_D(\theta)\).
وبما أن قطع عدد عشري موجب بعد \(D\) خانات يغيّر القيمة بأقل من وحدة في المنزلة التالية، فإن
$$0\le \tau(\theta)-\tau_D(\theta)<10^{-D}.$$
التطبيقات تستخدم \(D=80\)، أي إن هناك 56 خانة حماية إضافية فوق الخانات الأربع والعشرين المطلوبة. ولهذا يكون التقريب النهائي آمناً بعد استقرار التكرار.
هناك مثال فحص مفيد هو
$$\theta=2.956938891377988.$$
عندئذٍ
$$b_1=2.956938891377988,\qquad a_1=\lfloor b_1\rfloor=2.$$
والخطوات التالية هي
$$b_2=2(2.956938891377988-2+1)=3.913877782755976,\qquad a_2=3,$$
$$b_3=3(3.913877782755976-3+1)=5.741633348267928,\qquad a_3=5,$$
$$b_4=5(5.741633348267928-5+1)=8.70816674133964,\qquad a_4=8.$$
وبمتابعة العلاقة نفسها نحصل على
$$a_5=13,\quad a_6=21,\quad a_7=34,\quad a_8=55,\quad a_9=89,\quad a_{10}=144.$$
إذن يبدأ العدد العشري المدموج على الصورة
$$\tau(\theta)=2.3581321345589144\ldots$$
وهذا المثال يبين بوضوح كيف تُضاف الكتل متعددة الخانات مثل \(13\) و\(21\) و\(144\) كاملة داخل التمثيل العشري.
تتبع تطبيقات C++ وPython وJava الخطة العددية نفسها. فهي تستخدم حساباً عشرياً عالي الدقة، وتبدأ من \(2.2\)، ثم تولّد العلاقة التكرارية وتعيد بناء العدد العشري المدموج حتى تجمع 80 خانة كسرية. بعد ذلك تصبح هذه القيمة المقطوعة هي التقريب التالي.
نسختا C++ وJava تنفذان 30 دورة مباشرة من تكرار نقطة التثبيت ثم تقربان النتيجة النهائية إلى 24 خانة عشرية. أما مدخل Python فيعتمد على نفس حساب C++، ولذلك فإن سلوكه الرياضي مطابق لنسخة C++ وليس خوارزمية مستقلة مختلفة.
لنرمز بعدد الخانات الكسرية العاملة بـ \(P\)، وبعدد الكتل المتولدة في تقييم واحد لـ \(\tau\) بـ \(K\)، وبعدد دورات تكرار نقطة التثبيت بـ \(I\). يحتاج كل تقييم إلى \(K\) تحديثات من العلاقة التكرارية مع حساب عشري بدقة \(P\) خانات، كما ينتج في المجمل نحو \(P\) محرفاً في الخرج. لذلك فإن وصفاً تقاربياً مناسباً هو \(O(IKP)\) زمنياً و\(O(P)\) من حيث الذاكرة. وفي التطبيق الفعلي هنا تكون \(P=80\) و\(I=30\)، لذا يصبح زمن التنفيذ عملياً ثابتاً لهذه المسألة الواحدة.