The regular continued fraction of Euler's number is
$$e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, \dots].$$
The task is to take the 100th convergent of this continued fraction, extract its numerator, and compute the sum of that numerator's decimal digits. The first convergent is \(2/1\), so the requested object is the rational number obtained after processing coefficients \(a_0\) through \(a_{99}\).
This is an exact arithmetic problem, not a floating-point approximation problem. Once the coefficient pattern of the continued fraction is known, the numerator and denominator of each convergent follow from a short integer recurrence.
Write the convergents as
$$K_n = [a_0; a_1, a_2, \dots, a_n] = \frac{p_n}{q_n}.$$
For this problem we need the digit sum of \(p_{99}\), because \(K_{99}\) is the 100th convergent.
The continued fraction coefficients are not arbitrary. They follow the explicit pattern
$$a_0 = 2,$$
and for every integer \(m \ge 1\),
$$a_{3m-2} = 1, \qquad a_{3m-1} = 2m, \qquad a_{3m} = 1.$$
Equivalently, for \(k \ge 1\),
$$a_k = \begin{cases} \dfrac{2(k+1)}{3}, & k \equiv 2 \pmod{3}, \\ 1, & \text{otherwise}. \end{cases}$$
So the sequence after the initial 2 is grouped into triples \(1, 2, 1\), \(1, 4, 1\), \(1, 6, 1\), and so on. This pattern is the only problem-specific input the algorithm needs.
Every regular continued fraction has the standard recurrence
$$p_n = a_n p_{n-1} + p_{n-2}, \qquad q_n = a_n q_{n-1} + q_{n-2}.$$
The implementations use the initialization
$$p_{-1} = 1, \qquad p_0 = 2, \qquad q_{-1} = 0, \qquad q_0 = 1.$$
That means the first convergent \(2/1\) is already loaded before the loop starts. Each later coefficient appends one more layer to the continued fraction, and one recurrence step advances from \(K_{n-1}\) and \(K_{n-2}\) to \(K_n\).
The recurrence preserves the determinant identity
$$p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1}.$$
Since the right-hand side is always \(\pm 1\), every pair \((p_n, q_n)\) is coprime. So the convergents are automatically in lowest terms, and there is never any need to compute a greatest common divisor or reduce a fraction explicitly.
This also explains why the denominator is still tracked in the code even though the final answer only uses the numerator: the numerator and denominator evolve together under the same recurrence and describe the convergent exactly at every step.
The first ten coefficients are
$$2; 1, 2, 1, 1, 4, 1, 1, 6, 1.$$
Applying the recurrence produces
$$\frac{2}{1}, \ \frac{3}{1}, \ \frac{8}{3}, \ \frac{11}{4}, \ \frac{19}{7}, \ \frac{87}{32}, \ \frac{106}{39}, \ \frac{193}{71}, \ \frac{1264}{465}, \ \frac{1457}{536}.$$
For instance,
$$p_1 = 1 \cdot 2 + 1 = 3, \qquad p_2 = 2 \cdot 3 + 2 = 8, \qquad p_5 = 4 \cdot 19 + 11 = 87.$$
So the 10th convergent has numerator \(1457\), and its digit sum is
$$1 + 4 + 5 + 7 = 17.$$
This is the natural checkpoint for the implementation: if term 10 does not give 17, then the indexing or the coefficient pattern is wrong.
After processing coefficients \(a_1\) through \(a_{99}\), the numerator is exactly the numerator of the 100th convergent. The final step is purely decimal: convert that integer to base 10 and add its digits. No symbolic simplification, no search, and no approximation theory beyond the convergent recurrence is required.
The C++, Python, and Java implementations all follow the same structure.
The first coefficient is fixed at \(2\). For every later index, the implementation checks whether the index is congruent to \(2\) modulo \(3\). If not, the coefficient is \(1\); if so, the coefficient is the corresponding even number \(2, 4, 6, \dots\).
The implementation stores the current and previous numerators, and the current and previous denominators. Each loop iteration reads the next coefficient \(a_n\), computes
$$p_n = a_n p_{n-1} + p_{n-2}, \qquad q_n = a_n q_{n-1} + q_{n-2},$$
and then shifts the state forward. Because the first convergent \(2/1\) is already the initial state, term 1 returns immediately and term \(t\) needs exactly \(t-1\) updates.
Once the requested convergent has been built, the implementation converts its numerator to a decimal string and adds the characters' digit values. A built-in checkpoint verifies that the 10th convergent produces digit sum \(17\) before the default 100th-term calculation is trusted.
If \(t\) is the requested term and \(D\) is the number of decimal digits in the final numerator, then the algorithm performs \(t-1\) big-integer updates. Writing \(M(D)\) for the cost of multiplying a \(D\)-digit integer by a small coefficient and adding another \(D\)-digit integer, the running time is \(O(t \cdot M(D))\). With schoolbook arithmetic this behaves like \(O(tD)\).
For the specific input \(t = 100\), the computation is tiny. The implementation stores only the current and previous numerator/denominator pairs, plus the decimal representation used during the final digit sum, so the space usage is \(O(D)\).
Der reguläre Kettenbruch der Eulerschen Zahl lautet
$$e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, \dots].$$
Gesucht ist die 100. Näherung dieses Kettenbruchs, genauer die Ziffernsumme ihres Zählers. Die erste Näherung ist \(2/1\), also erhält man das gewünschte Objekt nach den Koeffizienten \(a_0\) bis \(a_{99}\).
Das ist keine Gleitkommaaufgabe. Sobald das Muster der Kettenbruchkoeffizienten feststeht, entstehen Zähler und Nenner jeder Näherung durch eine kurze ganzzahlige Rekursion.
Bezeichne die Näherungen mit
$$K_n = [a_0; a_1, a_2, \dots, a_n] = \frac{p_n}{q_n}.$$
Für diese Aufgabe wird also die Ziffernsumme von \(p_{99}\) benötigt, denn \(K_{99}\) ist die 100. Näherung.
Die Kettenbruchkoeffizienten folgen einer expliziten Struktur:
$$a_0 = 2,$$
und für jedes \(m \ge 1\)
$$a_{3m-2} = 1, \qquad a_{3m-1} = 2m, \qquad a_{3m} = 1.$$
Äquivalent dazu gilt für \(k \ge 1\)
$$a_k = \begin{cases} \dfrac{2(k+1)}{3}, & k \equiv 2 \pmod{3}, \\ 1, & \text{otherwise}. \end{cases}$$
Nach der führenden 2 zerfällt die Folge also in Dreierblöcke \(1,2,1\), \(1,4,1\), \(1,6,1\) und so weiter. Mehr problemspezifische Eingaben braucht der Algorithmus nicht.
Für reguläre Kettenbrüche gilt die Standardrekursion
$$p_n = a_n p_{n-1} + p_{n-2}, \qquad q_n = a_n q_{n-1} + q_{n-2}.$$
Die Implementierungen benutzen die Initialisierung
$$p_{-1} = 1, \qquad p_0 = 2, \qquad q_{-1} = 0, \qquad q_0 = 1.$$
Damit ist die erste Näherung \(2/1\) schon vor dem Schleifenstart vorhanden. Jeder weitere Koeffizient fügt genau eine Ebene des Kettenbruchs hinzu, und ein Rekurisionsschritt führt von \(K_{n-1}\) und \(K_{n-2}\) zu \(K_n\).
Die Rekursion erhält die Determinantenidentität
$$p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1}.$$
Da die rechte Seite immer \(\pm 1\) ist, sind \(p_n\) und \(q_n\) teilerfremd. Jede Näherung liegt also automatisch vollständig gekürzt vor; ein explizites Kürzen oder ein ggT-Schritt ist unnötig.
Deshalb wird im Code auch der Nenner mitgeführt, obwohl am Ende nur der Zähler abgefragt wird: Beide Größen entwickeln sich gemeinsam und beschreiben die jeweilige Näherung exakt.
Die ersten zehn Koeffizienten sind
$$2; 1, 2, 1, 1, 4, 1, 1, 6, 1.$$
Die Rekursion liefert daraus
$$\frac{2}{1}, \ \frac{3}{1}, \ \frac{8}{3}, \ \frac{11}{4}, \ \frac{19}{7}, \ \frac{87}{32}, \ \frac{106}{39}, \ \frac{193}{71}, \ \frac{1264}{465}, \ \frac{1457}{536}.$$
Zum Beispiel gilt
$$p_1 = 1 \cdot 2 + 1 = 3, \qquad p_2 = 2 \cdot 3 + 2 = 8, \qquad p_5 = 4 \cdot 19 + 11 = 87.$$
Die 10. Näherung hat also den Zähler \(1457\), dessen Ziffernsumme
$$1 + 4 + 5 + 7 = 17$$
ist. Genau dieser Wert dient als Kontrollpunkt der Implementierungen und überprüft sowohl das Indexschema als auch das Koeffizientenmuster.
Nach der Verarbeitung der Koeffizienten \(a_1\) bis \(a_{99}\) steht im Zustand exakt der Zähler der 100. Näherung. Danach bleibt nur noch ein dezimaler Schritt: die Zahl in Basis 10 schreiben und ihre Ziffern aufsummieren. Weder numerische Approximation noch zusätzliche Zahlentheorie sind dafür nötig.
Die C++-, Python- und Java-Implementierungen folgen demselben Ablauf.
Der erste Koeffizient ist fest \(2\). Für jeden späteren Index wird geprüft, ob er kongruent zu \(2\) modulo \(3\) ist. Falls nicht, ist der Koeffizient \(1\); andernfalls wird die passende gerade Zahl \(2, 4, 6, \dots\) erzeugt.
Gespeichert werden jeweils der aktuelle und der vorherige Zähler sowie der aktuelle und der vorherige Nenner. In jeder Iteration wird aus dem nächsten Koeffizienten \(a_n\)
$$p_n = a_n p_{n-1} + p_{n-2}, \qquad q_n = a_n q_{n-1} + q_{n-2}$$
berechnet, danach wird das Zustandsfenster um einen Schritt weitergeschoben. Weil \(2/1\) schon als Anfangszustand vorliegt, liefert Term 1 sofort ein Ergebnis, und Term \(t\) braucht genau \(t-1\) Updates.
Nach dem letzten Rekursionsschritt wandelt die Implementierung den Zähler in eine Dezimaldarstellung um und summiert die einzelnen Ziffern. Ein eingebauter Kontrolltest prüft vorher, dass die 10. Näherung tatsächlich die Ziffernsumme \(17\) besitzt.
Sei \(t\) der gewünschte Term und \(D\) die Anzahl der Dezimalstellen des Endzählers. Dann führt der Algorithmus \(t-1\) Big-Integer-Updates aus. Schreibt man \(M(D)\) für die Kosten einer Multiplikation einer \(D\)-stelligen Zahl mit einem kleinen Koeffizienten plus einer Addition einer weiteren \(D\)-stelligen Zahl, erhält man \(O(t \cdot M(D))\). Mit Schulbucharithmetik verhält sich das wie \(O(tD)\).
Für den konkreten Fall \(t = 100\) ist der Aufwand sehr klein. Gespeichert werden nur zwei aufeinanderfolgende Zähler, zwei aufeinanderfolgende Nenner und die Dezimaldarstellung für die abschließende Ziffernsumme, also \(O(D)\) Speicher.
Euler sayısının düzenli sürekli kesir açılımı
$$e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, \dots]$$
şeklindedir. İstenen şey, bu açılımın 100. yakınsak kesrini alıp payının onluk tabandaki rakamları toplamını bulmaktır. İlk yakınsak \(2/1\) olduğundan, aranan nesne \(a_0\) ile \(a_{99}\) arasındaki katsayılar işlendiğinde elde edilen rasyonel sayıdır.
Bu soru yaklaşık değer üretme sorusu değildir; tamamen tam sayı aritmetiği sorusudur. Katsayı deseni bilindiği anda her yakınsağın payı ve paydası kısa bir yineleme ile belirlenir.
Yakınsakları
$$K_n = [a_0; a_1, a_2, \dots, a_n] = \frac{p_n}{q_n}$$
biçiminde gösterelim. O halde bu problemde istenen değer, 100. yakınsak olan \(K_{99}\)'un payı \(p_{99}\)'un rakam toplamıdır.
Sürekli kesir katsayıları rastgele değildir. Açık biçimde
$$a_0 = 2,$$
ve her \(m \ge 1\) için
$$a_{3m-2} = 1, \qquad a_{3m-1} = 2m, \qquad a_{3m} = 1$$
olur. Eşdeğer olarak, \(k \ge 1\) için
$$a_k = \begin{cases} \dfrac{2(k+1)}{3}, & k \equiv 2 \pmod{3}, \\ 1, & \text{otherwise}. \end{cases}$$
Yani baştaki 2'den sonra katsayılar \(1,2,1\), \(1,4,1\), \(1,6,1\) üçlüleri halinde ilerler. Algoritmanın probleme özgü tek girdisi budur.
Düzenli sürekli kesirler için standart bağıntı
$$p_n = a_n p_{n-1} + p_{n-2}, \qquad q_n = a_n q_{n-1} + q_{n-2}$$
şeklindedir. Uygulamalarda kullanılan başlangıç değerleri ise
$$p_{-1} = 1, \qquad p_0 = 2, \qquad q_{-1} = 0, \qquad q_0 = 1$$
olur. Böylece ilk yakınsak \(2/1\) daha döngü başlamadan hazırdır. Her yeni katsayı, kesre bir katman daha ekler ve tek bir yineleme adımı \(K_{n-2}\) ile \(K_{n-1}\)'den \(K_n\)'e geçer.
Bu yineleme şu determinant değişmezini korur:
$$p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1}.$$
Sağ taraf her zaman \(\pm 1\) olduğundan, \(p_n\) ile \(q_n\) aralarında asaldır. Dolayısıyla her yakınsak kesir zaten en sade haldedir; ayrıca EBOB alıp sadeleştirmek gerekmez.
Kodun payda değerini de taşımasının nedeni budur. Sonuçta sadece payın rakam toplamı istense de, pay ve payda aynı yineleme altında birlikte ilerler ve o andaki yakınsak kesri tam olarak temsil eder.
İlk on katsayı
$$2; 1, 2, 1, 1, 4, 1, 1, 6, 1$$
olur. Yineleme uygulandığında
$$\frac{2}{1}, \ \frac{3}{1}, \ \frac{8}{3}, \ \frac{11}{4}, \ \frac{19}{7}, \ \frac{87}{32}, \ \frac{106}{39}, \ \frac{193}{71}, \ \frac{1264}{465}, \ \frac{1457}{536}$$
dizisi elde edilir. Örneğin
$$p_1 = 1 \cdot 2 + 1 = 3, \qquad p_2 = 2 \cdot 3 + 2 = 8, \qquad p_5 = 4 \cdot 19 + 11 = 87.$$
Demek ki 10. yakınsağın payı \(1457\)'dir ve rakam toplamı
$$1 + 4 + 5 + 7 = 17$$
çıkar. Uygulamalardaki kontrol noktası tam olarak budur; bu değer yanlışsa ya indeksleme ya da katsayı üretimi hatalıdır.
\(a_1\) ile \(a_{99}\) işlendiğinde elde edilen pay, tam olarak 100. yakınsağın payıdır. Bundan sonra kalan tek iş onluk tabana geçip rakamları toplamaktır. Ek bir arama, sembolik dönüşüm veya yaklaşık hesap yöntemi gerekmez.
C++, Python ve Java uygulamalarının akışı aynıdır.
İlk katsayı sabit olarak \(2\) alınır. Daha sonraki her indis için önce \(3\) ile bölümden kalan kontrol edilir. İndis \(2 \pmod{3}\) değilse katsayı \(1\)'dir; öyleyse uygun çift sayı \(2, 4, 6, \dots\) üretilir.
Uygulama, ardışık iki payı ve ardışık iki paydayı saklar. Her döngü adımında yeni katsayı \(a_n\) okunur,
$$p_n = a_n p_{n-1} + p_{n-2}, \qquad q_n = a_n q_{n-1} + q_{n-2}$$
hesaplanır ve pencere ileri kaydırılır. Başlangıçta \(2/1\) zaten hazır olduğu için, terim 1 doğrudan döner; terim \(t\) ise tam olarak \(t-1\) güncelleme ister.
İstenen yakınsak elde edilince uygulama payı onluk yazıya çevirir ve karakterlerin rakam değerlerini toplar. Ayrıca ortak bir kontrol testi, 10. yakınsağın rakam toplamının \(17\) olduğunu doğrulayarak ana hesabı güvence altına alır.
\(t\) istenen yakınsak sayısı, \(D\) ise son payın onluk basamak sayısı olsun. Algoritma \(t-1\) tane büyük tamsayı güncellemesi yapar. \(D\) basamaklı bir sayıyı küçük bir katsayıyla çarpıp başka bir \(D\) basamaklı sayıyla toplamanın maliyetine \(M(D)\) dersek çalışma süresi \(O(t \cdot M(D))\) olur. Okul çarpması yaklaşımıyla bu davranış \(O(tD)\) şeklindedir.
Bu problemde \(t = 100\) olduğundan hesap çok küçüktür. Yalnızca ardışık iki pay, ardışık iki payda ve son rakam toplamı için gereken onluk gösterim tutulur; bellek kullanımı \(O(D)\)'dir.
La fraccion continua regular del numero de Euler es
$$e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, \dots].$$
La tarea pide tomar el 100.o convergente de esa fraccion continua, extraer su numerador y sumar sus digitos decimales. El primer convergente es \(2/1\), asi que el objeto buscado aparece despues de procesar los coeficientes \(a_0\) hasta \(a_{99}\).
No hace falta aproximar \(e\) en coma flotante. Una vez conocido el patron de coeficientes, cada convergente se obtiene exactamente mediante una recurrencia corta de enteros.
Escribamos los convergentes como
$$K_n = [a_0; a_1, a_2, \dots, a_n] = \frac{p_n}{q_n}.$$
En consecuencia, la respuesta del problema es la suma de digitos de \(p_{99}\), porque \(K_{99}\) es el convergente numero 100.
Los coeficientes de la fraccion continua siguen una regla explicita:
$$a_0 = 2,$$
y para todo \(m \ge 1\),
$$a_{3m-2} = 1, \qquad a_{3m-1} = 2m, \qquad a_{3m} = 1.$$
De manera equivalente, para \(k \ge 1\),
$$a_k = \begin{cases} \dfrac{2(k+1)}{3}, & k \equiv 2 \pmod{3}, \\ 1, & \text{otherwise}. \end{cases}$$
Despues del 2 inicial, la sucesion se organiza en bloques \(1,2,1\), \(1,4,1\), \(1,6,1\), etcetera. Ese patron es la unica informacion especifica del problema que necesita el algoritmo.
Para cualquier fraccion continua regular vale la recurrencia estandar
$$p_n = a_n p_{n-1} + p_{n-2}, \qquad q_n = a_n q_{n-1} + q_{n-2}.$$
Las implementaciones arrancan con
$$p_{-1} = 1, \qquad p_0 = 2, \qquad q_{-1} = 0, \qquad q_0 = 1.$$
Eso significa que el primer convergente \(2/1\) ya esta cargado antes de entrar al bucle. Cada nuevo coeficiente agrega una capa mas a la fraccion continua, y un paso de la recurrencia avanza de \(K_{n-1}\) y \(K_{n-2}\) hacia \(K_n\).
La recurrencia conserva la identidad
$$p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1}.$$
Como el lado derecho siempre es \(\pm 1\), los pares \((p_n, q_n)\) son coprimos. Por eso cada convergente ya sale en forma reducida y no se necesita ningun paso adicional de simplificacion.
Tambien por eso el codigo mantiene el denominador aunque la respuesta final solo use el numerador: ambos evolucionan juntos y describen exactamente el convergente en cada iteracion.
Los primeros diez coeficientes son
$$2; 1, 2, 1, 1, 4, 1, 1, 6, 1.$$
Aplicando la recurrencia se obtiene
$$\frac{2}{1}, \ \frac{3}{1}, \ \frac{8}{3}, \ \frac{11}{4}, \ \frac{19}{7}, \ \frac{87}{32}, \ \frac{106}{39}, \ \frac{193}{71}, \ \frac{1264}{465}, \ \frac{1457}{536}.$$
Por ejemplo,
$$p_1 = 1 \cdot 2 + 1 = 3, \qquad p_2 = 2 \cdot 3 + 2 = 8, \qquad p_5 = 4 \cdot 19 + 11 = 87.$$
Asi, el numerador del 10.o convergente es \(1457\), y su suma de digitos es
$$1 + 4 + 5 + 7 = 17.$$
Ese valor funciona como prueba de control para la implementacion: si el termino 10 no produce 17, entonces el patron o la indexacion no son correctos.
Una vez procesados los coeficientes \(a_1\) hasta \(a_{99}\), el numerador almacenado es exactamente el numerador del convergente numero 100. El ultimo paso es solo decimal: escribir ese entero en base 10 y sumar sus digitos. No se necesita busqueda, ni reduccion simbolica, ni teoria adicional de aproximacion.
Las implementaciones en C++, Python y Java siguen la misma idea general.
El primer coeficiente se fija en \(2\). Para cada indice posterior, la implementacion comprueba si el indice es congruente con \(2\) modulo \(3\). Si no lo es, el coeficiente vale \(1\); si lo es, se genera el numero par correspondiente \(2, 4, 6, \dots\).
Se guardan dos numeradores consecutivos y dos denominadores consecutivos. En cada iteracion, con el siguiente coeficiente \(a_n\), se calcula
$$p_n = a_n p_{n-1} + p_{n-2}, \qquad q_n = a_n q_{n-1} + q_{n-2},$$
y luego se desplaza la ventana. Como \(2/1\) ya es el estado inicial, el termino 1 se resuelve de inmediato y el termino \(t\) requiere exactamente \(t-1\) actualizaciones.
Cuando ya se construyo el convergente pedido, la implementacion convierte el numerador a texto decimal y suma el valor de cada digito. Antes del calculo por defecto para el termino 100, se valida el punto de control de que el termino 10 debe dar \(17\).
Si \(t\) es el termino pedido y \(D\) es el numero de digitos del numerador final, el algoritmo realiza \(t-1\) actualizaciones de enteros grandes. Si \(M(D)\) denota el costo de multiplicar un entero de \(D\) digitos por un coeficiente pequeno y sumar otro entero de \(D\) digitos, el tiempo total es \(O(t \cdot M(D))\). Con aritmetica escolar esto se comporta como \(O(tD)\).
Para el caso concreto \(t = 100\), el trabajo es minimo. Solo se almacenan dos numeradores consecutivos, dos denominadores consecutivos y la representacion decimal utilizada en la suma final de digitos, asi que el espacio es \(O(D)\).
欧拉常数 \(e\) 的正规连分数展开为
$$e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, \dots].$$
题目要求取这个连分数的第 100 个渐近分数，提取它的分子，再求该分子的十进制数位和。第一个渐近分数就是 \(2/1\)，因此目标对象正是处理完系数 \(a_0\) 到 \(a_{99}\) 之后得到的那个有理数。
这不是浮点近似题，而是纯粹的精确整数计算题。只要确定了 \(e\) 的连分数系数模式，后续每一个渐近分数的分子和分母都可以由一条很短的递推式唯一确定。
记
$$K_n = [a_0; a_1, a_2, \dots, a_n] = \frac{p_n}{q_n}$$
为第 \(n+1\) 个渐近分数。于是本题所求就是 \(p_{99}\) 的数位和，因为 \(K_{99}\) 正好对应第 100 个渐近分数。
这里最关键的对象是系数序列本身。它满足
$$a_0 = 2,$$
并且对每个整数 \(m \ge 1\)，都有
$$a_{3m-2} = 1, \qquad a_{3m-1} = 2m, \qquad a_{3m} = 1.$$
也可以等价地写成：对 \(k \ge 1\)，
$$a_k = \begin{cases} \dfrac{2(k+1)}{3}, & k \equiv 2 \pmod{3}, \\ 1, & \text{otherwise}. \end{cases}$$
也就是说，开头的 \(2\) 之后，系数按 \(1,2,1\)、\(1,4,1\)、\(1,6,1\) 这样的三元组不断重复。算法并不需要别的题目特定输入；只要这个模式正确，整个计算就被完全确定了。
正规连分数的渐近分数满足标准递推：
$$p_n = a_n p_{n-1} + p_{n-2}, \qquad q_n = a_n q_{n-1} + q_{n-2}.$$
实现采用的初值是
$$p_{-1} = 1, \qquad p_0 = 2, \qquad q_{-1} = 0, \qquad q_0 = 1.$$
这样一来，第一个渐近分数 \(2/1\) 在循环开始前就已经就位。之后每读入一个新系数，就相当于在连分数右端再加一层，而一次递推恰好把状态从 \(K_{n-2}\)、\(K_{n-1}\) 推进到 \(K_n\)。
上述递推保持下面这个行列式恒等式：
$$p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1}.$$
右边永远是 \(\pm 1\)，因此 \(p_n\) 和 \(q_n\) 必然互素。换句话说，每个渐近分数天然就是最简分数，根本不需要额外求最大公约数再约分。
这也说明了为什么实现虽然最终只需要分子，却仍然同步维护分母：分子与分母在同一条递推下共同演化，才能精确表示当前渐近分数的数学对象。
前十个系数为
$$2; 1, 2, 1, 1, 4, 1, 1, 6, 1.$$
按递推计算，得到的渐近分数序列是
$$\frac{2}{1}, \ \frac{3}{1}, \ \frac{8}{3}, \ \frac{11}{4}, \ \frac{19}{7}, \ \frac{87}{32}, \ \frac{106}{39}, \ \frac{193}{71}, \ \frac{1264}{465}, \ \frac{1457}{536}.$$
其中几步可以直接看到：
$$p_1 = 1 \cdot 2 + 1 = 3, \qquad p_2 = 2 \cdot 3 + 2 = 8, \qquad p_5 = 4 \cdot 19 + 11 = 87.$$
因此第 10 个渐近分数的分子是 \(1457\)，它的数位和为
$$1 + 4 + 5 + 7 = 17.$$
这一点和实现中的检查值完全一致，所以它既验证了系数模式，也验证了渐近分数的编号方式。
当系数 \(a_1\) 到 \(a_{99}\) 全部处理完之后，当前分子就精确等于第 100 个渐近分数的分子。剩下的工作只是把这个大整数写成十进制字符串并累加各位数字。整个过程不依赖近似误差估计，也不需要额外的数学技巧。
C++、Python 和 Java 三个实现遵循同一条思路。
实现把第一个系数直接固定为 \(2\)。从后续位置开始，只需判断下标是否满足 \(k \equiv 2 \pmod{3}\)。如果不满足，系数就是 \(1\)；如果满足，就生成对应的偶数 \(2, 4, 6, \dots\)。
程序同时保存相邻两个分子和相邻两个分母。每次读到新系数 \(a_n\) 时，都按
$$p_n = a_n p_{n-1} + p_{n-2}, \qquad q_n = a_n q_{n-1} + q_{n-2}$$
计算下一项，然后把窗口整体向前推进。由于初始状态已经是第一个渐近分数 \(2/1\)，所以当请求第 1 项时可以直接返回；请求第 \(t\) 项时，恰好做 \(t-1\) 次更新。
构造完所需渐近分数之后，实现把最终分子转换为十进制文本，并对每个字符对应的数字值求和。代码中的公共检查点要求第 10 项必须得到数位和 \(17\)，这一步先确认整个递推和编号都没有偏移，再继续默认的第 100 项计算。
设要求的项数为 \(t\)，最终分子的十进制位数为 \(D\)。算法总共进行 \(t-1\) 次大整数更新。若用 \(M(D)\) 表示一个 \(D\) 位整数乘以小系数再加上另一个 \(D\) 位整数的代价，则总时间为 \(O(t \cdot M(D))\)。在普通按位运算模型下，可以把它看成接近 \(O(tD)\)。
对本题而言，\(t = 100\)，规模极小。程序只保存前后两个分子、前后两个分母，以及最终求数位和时使用的十进制表示，因此空间复杂度为 \(O(D)\)。
Регулярная цепная дробь числа Эйлера имеет вид
$$e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, \dots].$$
Нужно взять 100-ю подходящую дробь этого разложения, выделить ее числитель и найти сумму его десятичных цифр. Первая подходящая дробь равна \(2/1\), поэтому искомый объект получается после обработки коэффициентов от \(a_0\) до \(a_{99}\).
Это задача не про приближенные вычисления с плавающей точкой, а про точную целочисленную арифметику. Как только известен шаблон коэффициентов, числитель и знаменатель каждой подходящей дроби задаются короткой рекуррентной формулой.
Обозначим подходящие дроби через
$$K_n = [a_0; a_1, a_2, \dots, a_n] = \frac{p_n}{q_n}.$$
Тогда в этой задаче требуется сумма цифр числа \(p_{99}\), потому что \(K_{99}\) и есть 100-я подходящая дробь.
Коэффициенты цепной дроби задаются явно:
$$a_0 = 2,$$
а для каждого \(m \ge 1\)
$$a_{3m-2} = 1, \qquad a_{3m-1} = 2m, \qquad a_{3m} = 1.$$
То же самое можно записать так: для \(k \ge 1\)
$$a_k = \begin{cases} \dfrac{2(k+1)}{3}, & k \equiv 2 \pmod{3}, \\ 1, & \text{otherwise}. \end{cases}$$
После начального числа 2 коэффициенты идут тройками \(1,2,1\), \(1,4,1\), \(1,6,1\) и так далее. Это единственная специальная для данной задачи структура, которую должен знать алгоритм.
Для регулярной цепной дроби действует стандартная рекурсия
$$p_n = a_n p_{n-1} + p_{n-2}, \qquad q_n = a_n q_{n-1} + q_{n-2}.$$
Реализации используют начальные значения
$$p_{-1} = 1, \qquad p_0 = 2, \qquad q_{-1} = 0, \qquad q_0 = 1.$$
Значит, первая подходящая дробь \(2/1\) уже подготовлена до входа в цикл. Каждый следующий коэффициент добавляет еще один слой к цепной дроби, а один шаг рекурсии переводит состояние от \(K_{n-2}\) и \(K_{n-1}\) к \(K_n\).
Эта рекурсия сохраняет тождество
$$p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1}.$$
Правая часть всегда равна \(\pm 1\), поэтому \(p_n\) и \(q_n\) взаимно просты. Следовательно, каждая подходящая дробь уже находится в несократимом виде, и никакого отдельного шага сокращения не требуется.
Именно поэтому код продолжает вести знаменатель, хотя в ответе нужен только числитель: обе величины вместе подчиняются одной и той же рекурсии и в каждый момент точно описывают текущую подходящую дробь.
Первые десять коэффициентов равны
$$2; 1, 2, 1, 1, 4, 1, 1, 6, 1.$$
Из рекурсии получается последовательность
$$\frac{2}{1}, \ \frac{3}{1}, \ \frac{8}{3}, \ \frac{11}{4}, \ \frac{19}{7}, \ \frac{87}{32}, \ \frac{106}{39}, \ \frac{193}{71}, \ \frac{1264}{465}, \ \frac{1457}{536}.$$
Например,
$$p_1 = 1 \cdot 2 + 1 = 3, \qquad p_2 = 2 \cdot 3 + 2 = 8, \qquad p_5 = 4 \cdot 19 + 11 = 87.$$
Следовательно, числитель 10-й подходящей дроби равен \(1457\), а сумма его цифр равна
$$1 + 4 + 5 + 7 = 17.$$
Это и есть естественная контрольная точка реализации: если для терма 10 не получается 17, значит где-то ошиблись в индексации или в генерации коэффициентов.
После обработки коэффициентов \(a_1\) до \(a_{99}\) текущий числитель точно совпадает с числителем 100-й подходящей дроби. Остается только перевести это большое целое число в десятичную запись и просуммировать цифры. Никаких дополнительных эвристик или методов приближения здесь не требуется.
Реализации на C++, Python и Java устроены одинаково по сути.
Первый коэффициент фиксирован и равен \(2\). Для каждого следующего индекса программа проверяет, сравним ли он с \(2\) по модулю \(3\). Если нет, коэффициент равен \(1\); если да, берется соответствующее четное число \(2, 4, 6, \dots\).
В памяти хранятся два соседних числителя и два соседних знаменателя. На каждом шаге по новому коэффициенту \(a_n\) вычисляется
$$p_n = a_n p_{n-1} + p_{n-2}, \qquad q_n = a_n q_{n-1} + q_{n-2},$$
после чего окно сдвигается вперед. Поскольку состояние \(2/1\) уже подготовлено заранее, запрос для терма 1 возвращается сразу, а для терма \(t\) нужно ровно \(t-1\) обновлений.
Когда нужная подходящая дробь построена, реализация переводит числитель в десятичную строку и суммирует числовые значения символов. Перед стандартным вычислением для 100-го терма выполняется контроль: для 10-го терма сумма цифр должна быть равна \(17\).
Пусть \(t\) обозначает номер требуемой подходящей дроби, а \(D\) — число десятичных цифр в итоговом числителе. Алгоритм выполняет \(t-1\) обновлений больших целых чисел. Если через \(M(D)\) обозначить стоимость умножения \(D\)-значного числа на маленький коэффициент и последующего сложения с другим \(D\)-значным числом, то время работы равно \(O(t \cdot M(D))\). При школьной арифметике это ведет себя как \(O(tD)\).
Для данной задачи \(t = 100\), так что вычисление очень мало. Хранятся только два последних числителя, два последних знаменателя и десятичная запись, используемая при финальном суммировании цифр, то есть требуется \(O(D)\) памяти.
الكسر المستمر المنتظم للعدد \(e\) هو
$$e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, \dots].$$
المطلوب هو أخذ المتقارب رقم 100 لهذا الكسر المستمر، ثم استخراج بسطه، ثم حساب مجموع أرقامه في النظام العشري. بما أن المتقارب الأول هو \(2/1\)، فإن الكسر المطلوب يظهر بعد معالجة المعاملات من \(a_0\) حتى \(a_{99}\).
المسألة هنا ليست مسألة تقريب عشري، بل مسألة حساب صحيح دقيق بالكامل. ما إن نعرف نمط معاملات الكسر المستمر حتى يصبح كل من البسط والمقام محددين بواسطة علاقة عودية قصيرة.
لنكتب المتقاربات على الصورة
$$K_n = [a_0; a_1, a_2, \dots, a_n] = \frac{p_n}{q_n}.$$
إذن المطلوب في هذه المسألة هو مجموع أرقام \(p_{99}\)، لأن \(K_{99}\) يمثل المتقارب المئة.
معاملات الكسر المستمر هنا تتبع صيغة صريحة:
$$a_0 = 2,$$
ولكل \(m \ge 1\)، لدينا
$$a_{3m-2} = 1, \qquad a_{3m-1} = 2m, \qquad a_{3m} = 1.$$
وبصيغة مكافئة، عندما \(k \ge 1\)،
$$a_k = \begin{cases} \dfrac{2(k+1)}{3}, & k \equiv 2 \pmod{3}, \\ 1, & \text{otherwise}. \end{cases}$$
أي أن المعاملات بعد الـ \(2\) الأولى تأتي في كتل من الشكل \(1,2,1\)، ثم \(1,4,1\)، ثم \(1,6,1\)، وهكذا. هذا هو العنصر الرياضي الخاص بالمسألة، وبعد تثبيته يصبح كل شيء آخر مباشرًا.
كل كسر مستمر منتظم يحقق العلاقة القياسية
$$p_n = a_n p_{n-1} + p_{n-2}, \qquad q_n = a_n q_{n-1} + q_{n-2}.$$
أما القيم الابتدائية المستخدمة في التنفيذ فهي
$$p_{-1} = 1, \qquad p_0 = 2, \qquad q_{-1} = 0, \qquad q_0 = 1.$$
وهذا يعني أن المتقارب الأول \(2/1\) موجود أصلًا قبل بداية الحلقة. بعد ذلك يضيف كل معامل جديد طبقة جديدة إلى الكسر المستمر، وخطوة عودية واحدة تنقلنا من \(K_{n-2}\) و\(K_{n-1}\) إلى \(K_n\).
هذه العلاقة العودية تحفظ الهوية
$$p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1}.$$
وبما أن الطرف الأيمن يساوي دائمًا \(\pm 1\)، فإن \(p_n\) و\(q_n\) متباينان أوليًا دائمًا. لذلك فكل متقارب يخرج في أبسط صورة تلقائيًا، ولا حاجة مطلقًا إلى حساب القاسم المشترك الأكبر أو إجراء خطوة اختزال منفصلة.
ولهذا السبب أيضًا يحتفظ التنفيذ بالمقام رغم أن المطلوب النهائي يستخدم البسط فقط: فالبسط والمقام يتحركان معًا تحت العلاقة نفسها ويمثلان المتقارب بدقة في كل مرحلة.
أول عشرة معاملات هي
$$2; 1, 2, 1, 1, 4, 1, 1, 6, 1.$$
وعند تطبيق العلاقة العودية نحصل على
$$\frac{2}{1}, \ \frac{3}{1}, \ \frac{8}{3}, \ \frac{11}{4}, \ \frac{19}{7}, \ \frac{87}{32}, \ \frac{106}{39}, \ \frac{193}{71}, \ \frac{1264}{465}, \ \frac{1457}{536}.$$
فعلى سبيل المثال،
$$p_1 = 1 \cdot 2 + 1 = 3, \qquad p_2 = 2 \cdot 3 + 2 = 8, \qquad p_5 = 4 \cdot 19 + 11 = 87.$$
إذن بسط المتقارب العاشر هو \(1457\)، ومجموع أرقامه يساوي
$$1 + 4 + 5 + 7 = 17.$$
وهذه هي نقطة التحقق الطبيعية في التنفيذ: إذا لم يعطِ الطلب الخاص بالحد العاشر القيمة \(17\)، فهناك خطأ في الفهرسة أو في توليد المعاملات.
بعد معالجة المعاملات من \(a_1\) حتى \(a_{99}\)، يكون البسط الحالي هو بالضبط بسط المتقارب رقم 100. وبعد ذلك لا يبقى إلا تحويل هذا العدد الصحيح الكبير إلى تمثيل عشري وجمع أرقامه. لا توجد هنا حاجة إلى بحث، ولا إلى تقريب عددي، ولا إلى خطوات إضافية خارج هذه العودية.
التنفيذات في C++ وPython وJava تتبع الخطة نفسها.
المعامل الأول يثبت مباشرة على \(2\). ولكل فهرس تالٍ، يفحص التنفيذ هل الفهرس يحقق \(k \equiv 2 \pmod{3}\). إذا لم يحقق ذلك فالمعامل هو \(1\)، وإذا حققه فالمعامل هو العدد الزوجي المناسب \(2, 4, 6, \dots\).
يحتفظ التنفيذ بآخر بسطين وآخر مقامين. في كل دورة، ومع المعامل الجديد \(a_n\)، يحسب
$$p_n = a_n p_{n-1} + p_{n-2}, \qquad q_n = a_n q_{n-1} + q_{n-2},$$
ثم يزحزح الحالة إلى الأمام. وبما أن الحالة الابتدائية تمثل أصلًا \(2/1\)، فإن الطلب للحد الأول يعاد فورًا، بينما يحتاج الحد \(t\) إلى \(t-1\) تحديثات بالضبط.
بعد بناء المتقارب المطلوب، يحول التنفيذ البسط إلى نص عشري ثم يجمع القيم الرقمية للمحارف. وهناك تحقق داخلي إضافي يؤكد أن الحد العاشر يجب أن يعطي مجموع أرقام يساوي \(17\) قبل الاعتماد على حساب الحد رقم 100.
إذا كان \(t\) هو رقم المتقارب المطلوب، وكان \(D\) هو عدد أرقام البسط النهائي، فإن الخوارزمية تنفذ \(t-1\) تحديثات لأعداد صحيحة كبيرة. وإذا رمزنا بـ \(M(D)\) إلى كلفة ضرب عدد مكوَّن من \(D\) أرقام في معامل صغير ثم جمع عدد آخر من \(D\) أرقام، فإن الزمن الكلي يساوي \(O(t \cdot M(D))\). ومع الحساب المدرسي للأرقام يمكن النظر إليه على أنه قريب من \(O(tD)\).
في هذه المسألة تحديدًا لدينا \(t = 100\)، لذا فالحساب صغير جدًا. الذاكرة المطلوبة لا تتجاوز آخر بسطين وآخر مقامين والتمثيل العشري المستخدم في مرحلة جمع الأرقام، أي \(O(D)\).