The Project Euler instance asks for the sum of the decimal digits of \(100!\). The number \(100!=1\cdot2\cdot3\cdots100\) is far too large for ordinary fixed-width integers: it has \(158\) decimal digits and ends with \(24\) zeros. So the task is not to approximate the factorial, but to construct its exact decimal expansion and then add those digits.
Let \(F_k=k!\) and let \(s(k)\) denote the sum of the decimal digits of \(F_k\). All three implementations rely on the same mathematical fact: factorials grow by the recurrence \(F_k=kF_{k-1}\), so if we can maintain the exact decimal representation after each multiplication, the final digit sum is immediate.
The starting point is
$$F_0=1,\qquad F_k=kF_{k-1}\quad(k\ge1).$$
This recurrence is problem-specific and complete: to reach \(100!\), we do not need any combinatorial reformulation, only a sequence of exact multiplications by \(2,3,\dots,100\). The boundary case \(0!=1\) is also built into the recurrence and is a useful correctness check.
Write the current factorial as
$$F_k=\sum_{j=0}^{m_k-1} d_j\,10^j,\qquad 0\le d_j\le9.$$
Here \(d_0\) is the units digit, \(d_1\) the tens digit, and so on. Storing digits in this little-endian order is convenient because multiplication by a small integer begins at the units place and pushes carry to higher places. Once the last multiplication is finished, the target quantity is simply
$$s(k)=\sum_{j=0}^{m_k-1} d_j.$$
Assume the digits \(d_j\) already represent \((k-1)!\). To multiply by \(k\), process the decimal expansion one digit at a time. With initial carry \(c_0=0\), define
$$t_j=kd_j+c_j,\qquad d'_j=t_j\bmod 10,\qquad c_{j+1}=\left\lfloor\frac{t_j}{10}\right\rfloor.$$
After all existing digits have been updated, the remaining carry \(c_{m_k}\) is written out as additional decimal digits. This is exactly schoolbook multiplication in base \(10\). The key invariant is: after finishing multiplier \(k\), the updated digit list represents \(k!\) exactly. That invariant is what makes the final digit sum trustworthy.
The sum-of-digits function is not multiplicative, because carries matter. Knowing only the current digit sum does not tell us the next one after multiplication. For instance, \(8\cdot5=40\): the product has digit sum \(4\), not \(8\cdot5\), not \(8+5\), and not anything that can be recovered without the actual decimal carries. That is why the implementations compute the whole factorial exactly and postpone digit summation until the end.
The recurrence produces
$$1,\ 2,\ 6,\ 24,\ 120,\ 720,\ 5040,\ 40320,\ 362880,\ 3628800.$$
Therefore
$$10!=3628800,\qquad s(10)=3+6+2+8+8+0+0=27.$$
This example is large enough to show both phenomena that matter for the full problem: carries appear repeatedly, and the decimal representation acquires trailing zeros automatically when enough factors of \(2\) and \(5\) have accumulated.
Two classical formulas provide strong sanity checks. First, for any nonnegative integer \(N\), the decimal digit sum satisfies
$$s(N)\equiv N\pmod 9.$$
Since \(n!\) is divisible by \(9\) for every \(n\ge6\), we must have \(s(n!)\equiv0\pmod 9\) in the Project Euler range. Second, the number of trailing zeros is controlled by the exponent of \(5\):
$$z(n)=\sum_{r\ge1}\left\lfloor\frac{n}{5^r}\right\rfloor.$$
For \(n=100\), this gives \(z(100)=\lfloor100/5\rfloor+\lfloor100/25\rfloor=20+4=24\). Those zeros add nothing to the digit sum, but they explain the long string of final zeros. A size estimate also comes from
$$D(n)=\lfloor\log_{10}(n!)\rfloor+1,$$
and Stirling's approximation confirms that \(100!\) has \(158\) digits, so an explicit decimal-digit method is entirely manageable.
The C++ implementation follows the mathematics directly. It starts from the decimal number \(1\), stored as a one-digit list, then multiplies by every integer from \(2\) through \(n\). Each pass updates every stored digit with the carry recurrence above, appends any remaining carry digits, and preserves the invariant that the list is the exact decimal representation of the current factorial. After the final multiplication, it sums the digits in that list.
The Python and Java implementations perform the same logical computation at a higher level. They build the exact factorial using the language runtime's arbitrary-precision integer machinery, convert the result to decimal text, and add the decimal digits. So the implementations differ only in how explicitly they expose the big-integer arithmetic; mathematically, all three compute the same exact object before taking the digit sum.
For the explicit decimal-digit method, if \(D(k)\) is the number of decimal digits of \(k!\), then multiplying \((k-1)!\) by \(k\) touches \(D(k-1)\) digits and performs constant work per digit. Therefore the total running time is
$$\sum_{k=1}^{n} O(D(k))=O\!\left(\sum_{k=1}^{n} k\log k\right)=O(n^2\log n).$$
The storage requirement is the size of the current decimal expansion, namely \(O(D(n))=O(n\log n)\) digits. For the actual Project Euler input \(n=100\), this is tiny: only \(158\) decimal digits are stored at the end, and the final digit-summing pass is linear in that length. The higher-level arbitrary-precision implementations may use faster internal multiplication routines, but for this problem they are still dominated by constructing and scanning one exact factorial.
Im Project-Euler-Fall soll die Summe der Dezimalziffern von \(100!\) bestimmt werden. Die Zahl \(100!=1\cdot2\cdot3\cdots100\) ist für gewöhnliche Festbreiten-Ganzzahlen viel zu groß: Sie besitzt \(158\) Dezimalstellen und endet mit \(24\) Nullen. Gesucht ist also keine Näherung, sondern die exakte Dezimaldarstellung von \(100!\) und anschließend deren Ziffernsumme.
Sei \(F_k=k!\) und \(s(k)\) die Summe der Dezimalziffern von \(F_k\). Alle drei Implementierungen beruhen auf derselben mathematischen Struktur: Fakultäten wachsen rekursiv über \(F_k=kF_{k-1}\). Wenn man nach jedem Schritt die exakte Dezimaldarstellung erhält, ist die Ziffernsumme am Ende sofort verfügbar.
Der Ausgangspunkt ist
$$F_0=1,\qquad F_k=kF_{k-1}\quad(k\ge1).$$
Mehr braucht das Problem nicht. Um \(100!\) zu berechnen, werden einfach die Faktoren \(2,3,\dots,100\) nacheinander eingearbeitet. Gleichzeitig steckt der Randfall \(0!=1\) bereits in dieser Formel und dient als einfache Korrektheitsprüfung.
Schreibe
$$F_k=\sum_{j=0}^{m_k-1} d_j\,10^j,\qquad 0\le d_j\le9.$$
Dabei ist \(d_0\) die Einerziffer, \(d_1\) die Zehnerziffer usw. Diese Little-Endian-Reihenfolge passt perfekt zur schriftlichen Multiplikation, weil Überträge immer von niedrigen zu höheren Stellen wandern. Sobald die Enddarstellung vorliegt, ist die gesuchte Größe einfach
$$s(k)=\sum_{j=0}^{m_k-1} d_j.$$
Angenommen, die Ziffern \(d_j\) repräsentieren bereits \((k-1)!\). Dann erfolgt die Multiplikation mit \(k\) stellenweise. Mit Anfangsübertrag \(c_0=0\) setzt man
$$t_j=kd_j+c_j,\qquad d'_j=t_j\bmod 10,\qquad c_{j+1}=\left\lfloor\frac{t_j}{10}\right\rfloor.$$
Nachdem alle vorhandenen Stellen verarbeitet wurden, wird der verbleibende Übertrag \(c_{m_k}\) selbst wieder in Dezimalziffern zerlegt und angehängt. Genau das ist schriftliche Multiplikation in Basis \(10\). Die zentrale Invariante lautet: Nach Abschluss des Schritts mit Faktor \(k\) kodiert die Ziffernliste exakt den Wert \(k!\).
Die Ziffernsummenfunktion ist nicht multiplikativ, weil Überträge das Ergebnis verändern. Aus der bisherigen Ziffernsumme allein lässt sich die nächste Ziffernsumme nicht rekonstruieren. Schon \(8\cdot5=40\) zeigt das: Die Ziffernsumme des Produkts ist \(4\), und dieser Wert ist ohne die konkrete Dezimalmultiplikation nicht direkt ableitbar. Deshalb behalten die Implementierungen die vollständige Dezimalstruktur bis zum Ende bei.
Die Rekursion erzeugt die Folge
$$1,\ 2,\ 6,\ 24,\ 120,\ 720,\ 5040,\ 40320,\ 362880,\ 3628800.$$
Somit gilt
$$10!=3628800,\qquad s(10)=3+6+2+8+8+0+0=27.$$
Dieses Beispiel zeigt bereits alle wesentlichen Effekte: Überträge treten mehrfach auf, und Endnullen entstehen automatisch, sobald genügend Faktoren \(2\) und \(5\) vorhanden sind.
Zwei klassische Formeln liefern starke Plausibilitätschecks. Erstens gilt für jede nichtnegative ganze Zahl \(N\)
$$s(N)\equiv N\pmod 9.$$
Da \(n!\) für jedes \(n\ge6\) durch \(9\) teilbar ist, muss auch \(s(n!)\equiv0\pmod 9\) gelten. Zweitens wird die Anzahl der Endnullen durch die Fünferpotenzen gesteuert:
$$z(n)=\sum_{r\ge1}\left\lfloor\frac{n}{5^r}\right\rfloor.$$
Für \(n=100\) ergibt das \(z(100)=20+4=24\). Diese Nullen tragen nichts zur Ziffernsumme bei, erklären aber das Ende der Dezimaldarstellung. Eine Größenabschätzung folgt außerdem aus
$$D(n)=\lfloor\log_{10}(n!)\rfloor+1,$$
und mit Stirling sieht man, dass \(100!\) genau \(158\) Stellen hat. Die explizite Dezimalmethode ist also völlig praktikabel.
Die C++-Implementierung setzt die Herleitung direkt um. Sie startet mit der Dezimalzahl \(1\), gespeichert als Liste einer einzigen Ziffer, und multipliziert dann nacheinander mit allen Zahlen von \(2\) bis \(n\). In jedem Durchlauf werden alle gespeicherten Stellen mit der Übertragsformel aktualisiert, restliche Übertragsziffern angehängt und die Invariante erhalten, dass die Liste exakt die aktuelle Fakultät repräsentiert. Am Ende werden diese Ziffern addiert.
Die Python- und Java-Implementierungen führen dieselbe mathematische Rechnung auf höherem Abstraktionsniveau aus. Sie bilden die exakte Fakultät mit der eingebauten Ganzzahlarithmetik beliebiger Präzision, wandeln das Ergebnis in eine Dezimaldarstellung um und summieren deren Ziffern. Der Unterschied liegt also nur darin, wie sichtbar die Großzahlarithmetik im Quelltext ist; mathematisch wird in allen Fällen dieselbe exakte Zahl erzeugt.
Für die explizite Dezimalziffern-Methode sei \(D(k)\) die Anzahl der Dezimalstellen von \(k!\). Die Multiplikation von \((k-1)!\) mit \(k\) verarbeitet jede vorhandene Stelle genau einmal und benötigt daher \(O(D(k-1))\) Zeit. Insgesamt ergibt sich
$$\sum_{k=1}^{n} O(D(k))=O\!\left(\sum_{k=1}^{n} k\log k\right)=O(n^2\log n).$$
Der Speicherbedarf ist die Länge der aktuellen Dezimalentwicklung, also \(O(D(n))=O(n\log n)\) Ziffern. Für den konkreten Projekt-Euler-Wert \(n=100\) ist das klein: Am Ende liegen nur \(158\) Stellen vor, und das abschließende Summieren ist linear in dieser Länge. Die eingebauten Großzahl-Implementierungen können intern schnellere Multiplikationsverfahren verwenden, aber auch dort dominiert für dieses Problem das Konstruieren und anschließende Durchlaufen einer exakten Fakultätszahl.
Bu soruda \(100!\) sayısının ondalık yazımındaki rakamların toplamı istenir. \(100!=1\cdot2\cdot3\cdots100\) değeri sıradan sabit genişlikli tamsayıların çok ötesindedir: \(158\) basamaklıdır ve sonunda \(24\) tane sıfır vardır. Dolayısıyla asıl iş, yaklaşık bir değer üretmek değil, \(100!\)’in tam ondalık açılımını oluşturup ardından basamaklarını toplamaktır.
\(F_k=k!\) ve \(s(k)\) de \(F_k\)’nin ondalık basamak toplamı olsun. Üç uygulamanın ortak matematiksel temeli aynıdır: faktöriyel
$$F_0=1,\qquad F_k=kF_{k-1}$$
bağıntısıyla büyür. Bu yüzden her çarpma adımından sonra tam ondalık gösterimi koruyabilirsek, en sonda basamak toplamını almak doğrudan mümkün olur.
Bu problem için gereken temel durum uzayı zaten formülün içinde bulunur. \(1\)’den başlayıp sırayla \(2,3,\dots,100\) ile çarpmak yeterlidir. Ayrıca \(0!=1\) sınır durumu da aynı çerçeve içinde yer alır ve kodun doğru çalıştığını kontrol etmek için iyi bir başlangıç testidir.
Mevcut faktöriyeli
$$F_k=\sum_{j=0}^{m_k-1} d_j\,10^j,\qquad 0\le d_j\le9$$
şeklinde yazalım. Burada \(d_0\) birler, \(d_1\) onlar basamağıdır. Basamakları küçükten büyüğe doğru tutmak doğaldır; çünkü çarpma ve elde aktarımı her zaman en düşük basamaktan başlar. Son durumda aradığımız nicelik yalnızca
$$s(k)=\sum_{j=0}^{m_k-1} d_j$$
olur.
\((k-1)!\) sayısının basamakları elimizde olsun. \(k\) ile çarpmak için her basamak tek tek işlenir. Başlangıç elde değeri \(c_0=0\) olmak üzere
$$t_j=kd_j+c_j,\qquad d'_j=t_j\bmod 10,\qquad c_{j+1}=\left\lfloor\frac{t_j}{10}\right\rfloor$$
tanımlanır. Mevcut tüm basamaklar bittiğinde son elde değeri de ayrı basamaklara ayrılıp sona eklenir. Bu, ilkokulda yapılan onluk sistem çarpmasının aynısıdır. Korunan temel değişmez şudur: \(k\) adımı bittiğinde yeni basamak dizisi tam olarak \(k!\)’yi temsil eder.
Basamak toplamı fonksiyonu çarpma ile uyumlu değildir; elde oluşumu bilgiyi değiştirir. Sadece mevcut basamak toplamını bilmek, bir sonraki çarpımdan sonra oluşacak toplamı vermez. Örneğin \(8\cdot5=40\) olduğunda sonuçtaki basamak toplamı \(4\) olur. Bu değer, çarpanların basamak toplamlarından veya çarpımlarından doğrudan çıkmaz. Bu nedenle çözüm, basamak toplamını değil, tam ondalık durumu taşır.
Bağıntı şu zinciri üretir:
$$1,\ 2,\ 6,\ 24,\ 120,\ 720,\ 5040,\ 40320,\ 362880,\ 3628800.$$
Dolayısıyla
$$10!=3628800,\qquad s(10)=3+6+2+8+8+0+0=27.$$
Bu örnek tam problem için gereken iki ana özelliği gösterir: elde zincirleri gerçekten oluşur ve yeterince çok \(2\) ile \(5\) çarpanı biriktiğinde sondaki sıfırlar kendiliğinden ortaya çıkar.
İki klasik formül güçlü kontrol noktaları sağlar. Birincisi, her tam sayı \(N\) için
$$s(N)\equiv N\pmod 9$$
olur. \(n!\), \(n\ge6\) olduğunda \(9\)’a bölündüğü için \(s(n!)\equiv0\pmod 9\) beklenir. İkincisi, sondaki sıfır sayısı \(5\) çarpanlarının sayısıyla belirlenir:
$$z(n)=\sum_{r\ge1}\left\lfloor\frac{n}{5^r}\right\rfloor.$$
\(n=100\) için bu toplam \(20+4=24\) eder. Bu sıfırlar basamak toplamına katkı yapmaz, ama ondalık gösterimin neden sıfırlarla bittiğini açıklar. Ayrıca
$$D(n)=\lfloor\log_{10}(n!)\rfloor+1$$
formülü ve Stirling yaklaşımı, \(100!\)’in \(158\) basamaklı olduğunu gösterir; yani açık basamak dizisi yöntemi rahatlıkla uygulanabilir.
C++ uygulaması matematiği doğrudan uygular. Başlangıçta yalnızca \(1\) rakamı tutulur; sonra \(2\)’den \(n\)’e kadar her sayı ile çarpılır. Her turda mevcut bütün basamaklar elde bağıntısıyla güncellenir, artan elde yeni basamaklar olarak eklenir ve böylece dizinin her adımda güncel faktöriyeli tam olarak temsil ettiği değişmez korunur. Sonunda dizi içindeki basamaklar toplanır.
Python ve Java uygulamaları aynı matematiksel işlemi daha yüksek seviyede yapar. Çalışma zamanı sisteminin keyfi duyarlıklı tamsayı altyapısı ile tam faktöriyeli üretir, sonucu ondalık metne çevirir ve karakterleri rakama dönüştürerek toplar. Yani fark, büyük sayı aritmetiğinin ne kadar açık yazıldığıdır; hesaplanan nesne her üç dilde de aynı tam \(n!\) değeridir.
Açık ondalık basamak yönteminde \(D(k)\), \(k!\)’nin basamak sayısı olsun. \((k-1)!\)’yi \(k\) ile çarpmak, mevcut \(D(k-1)\) basamağın her birine sabit maliyetli işlem uygular. Toplam süre bu nedenle
$$\sum_{k=1}^{n} O(D(k))=O\!\left(\sum_{k=1}^{n} k\log k\right)=O(n^2\log n)$$
olur. Bellek kullanımı, son değerin basamak sayısı kadardır:
$$O(D(n))=O(n\log n).$$
Project Euler girdisi olan \(n=100\) için bu son derece küçüktür; nihai sayıda sadece \(158\) basamak vardır ve son toplama geçişi bu uzunlukta doğrusaldır. Yerleşik büyük tamsayı uygulamaları içeride daha gelişmiş çarpma yöntemleri kullanabilir, fakat bu problem ölçeğinde baskın maliyet yine tek bir tam faktöriyeli üretip taramaktır.
La instancia de Project Euler pide la suma de las cifras decimales de \(100!\). El valor \(100!=1\cdot2\cdot3\cdots100\) es demasiado grande para los enteros de tamaño fijo habituales: tiene \(158\) cifras decimales y termina con \(24\) ceros. Por eso el problema no consiste en aproximar el factorial, sino en construir su expansión decimal exacta y luego sumar esas cifras.
Sea \(F_k=k!\) y sea \(s(k)\) la suma de las cifras decimales de \(F_k\). Las tres implementaciones usan la misma idea matemática: el factorial crece por la recurrencia
$$F_0=1,\qquad F_k=kF_{k-1},$$
de modo que, si mantenemos la representación decimal exacta después de cada multiplicación, la suma final de cifras se obtiene sin pasos adicionales sofisticados.
La estructura correcta del problema ya está en la fórmula anterior. Para llegar a \(100!\) basta empezar en \(1\) e incorporar sucesivamente los factores \(2,3,\dots,100\). El caso límite \(0!=1\) también aparece de forma natural y sirve como verificación elemental de que el procedimiento arranca correctamente.
Escribimos
$$F_k=\sum_{j=0}^{m_k-1} d_j\,10^j,\qquad 0\le d_j\le9.$$
Aquí \(d_0\) es la cifra de unidades, \(d_1\) la de decenas, etcétera. Este orden little-endian es ideal porque la multiplicación por un entero pequeño empieza en las unidades y propaga el acarreo hacia posiciones superiores. Cuando el proceso termina, la cantidad pedida es simplemente
$$s(k)=\sum_{j=0}^{m_k-1} d_j.$$
Supongamos que los dígitos \(d_j\) representan ya \((k-1)!\). Para multiplicar por \(k\), se procesa la expansión decimal cifra por cifra. Con acarreo inicial \(c_0=0\), definimos
$$t_j=kd_j+c_j,\qquad d'_j=t_j\bmod 10,\qquad c_{j+1}=\left\lfloor\frac{t_j}{10}\right\rfloor.$$
Al terminar las cifras existentes, el acarreo restante \(c_{m_k}\) se descompone también en base \(10\) y se añade al final. Esto es exactamente la multiplicación escolar en decimal. La invariante central es: después de completar el paso con el factor \(k\), la nueva lista de cifras representa \(k!\) de manera exacta.
La función suma de cifras no es multiplicativa, porque los acarreos modifican la estructura decimal. Conocer la suma actual no permite deducir la siguiente tras multiplicar. Por ejemplo, \(8\cdot5=40\), y la suma de cifras del producto es \(4\); ese valor no puede obtenerse a partir de una regla simple que use solo las sumas previas. Por eso la implementación conserva el estado decimal completo y solo suma cifras al final.
La recurrencia genera la sucesión
$$1,\ 2,\ 6,\ 24,\ 120,\ 720,\ 5040,\ 40320,\ 362880,\ 3628800.$$
Por lo tanto,
$$10!=3628800,\qquad s(10)=3+6+2+8+8+0+0=27.$$
Este ejemplo ya muestra los dos fenómenos esenciales del problema completo: aparecen acarreos en varias etapas y, cuando se acumulan suficientes factores \(2\) y \(5\), los ceros finales surgen automáticamente en la representación decimal.
Dos fórmulas clásicas sirven para verificar el resultado. La primera dice que, para cualquier entero no negativo \(N\),
$$s(N)\equiv N\pmod 9.$$
Como \(n!\) es divisible por \(9\) para todo \(n\ge6\), debe cumplirse \(s(n!)\equiv0\pmod 9\) en este problema. La segunda controla los ceros finales mediante las potencias de \(5\):
$$z(n)=\sum_{r\ge1}\left\lfloor\frac{n}{5^r}\right\rfloor.$$
Para \(n=100\), esto da \(z(100)=20+4=24\). Esos ceros no aportan nada a la suma de cifras, pero explican la forma final del número. Además, la longitud decimal viene dada por
$$D(n)=\lfloor\log_{10}(n!)\rfloor+1,$$
y la aproximación de Stirling confirma que \(100!\) tiene \(158\) cifras. Así, trabajar con una lista explícita de dígitos es completamente razonable.
La implementación en C++ sigue la derivación de forma directa. Empieza con el número decimal \(1\), almacenado como una lista con una sola cifra, y lo multiplica sucesivamente por todos los enteros entre \(2\) y \(n\). En cada pasada actualiza cada cifra con la regla de acarreo, añade las cifras que quedan en el acarreo final y mantiene la invariante de que la lista es la representación decimal exacta del factorial actual. Al terminar, suma todas las cifras almacenadas.
Las implementaciones en Python y Java realizan la misma operación matemática a un nivel más alto. Construyen el factorial exacto con enteros de precisión arbitraria del entorno de ejecución, convierten el resultado a texto decimal y suman sus caracteres numéricos. La diferencia está solo en cuánta aritmética de enteros grandes aparece explícitamente; el objeto matemático calculado es el mismo en los tres casos.
En el método explícito por dígitos decimales, si \(D(k)\) denota el número de cifras de \(k!\), entonces multiplicar \((k-1)!\) por \(k\) recorre una vez esas \(D(k-1)\) cifras y hace trabajo constante por cifra. Por tanto, el tiempo total es
$$\sum_{k=1}^{n} O(D(k))=O\!\left(\sum_{k=1}^{n} k\log k\right)=O(n^2\log n).$$
La memoria necesaria es el tamaño de la expansión decimal actual, es decir, \(O(D(n))=O(n\log n)\) cifras. Para la entrada concreta \(n=100\), el coste real es pequeño: el número final tiene solo \(158\) cifras y el paso de sumar cifras es lineal en esa longitud. Las bibliotecas de precisión arbitraria pueden usar multiplicación interna más rápida, pero en esta escala siguen estando dominadas por construir y recorrer un único factorial exacto.
本题要求求出 \(100!\) 的十进制数位和。这里的 \(100!=1\cdot2\cdot3\cdots100\) 不是一个可以放进普通固定宽度整数类型的小数；它有 \(158\) 位十进制数字，并且末尾有 \(24\) 个零。因此问题的核心不是近似计算，而是先精确构造 \(100!\) 的十进制展开，再把所有数位相加。
记 \(F_k=k!\)，记 \(s(k)\) 为 \(F_k\) 的十进制数位和。三份实现虽然写法不同，但数学上完全一致：都利用了阶乘的递推关系
$$F_0=1,\qquad F_k=kF_{k-1}.$$
只要每一步乘法之后都能保留当前结果的精确十进制表示，最后的数位和就只是一次线性求和。
这个问题并不需要更复杂的组合变形。要得到 \(100!\)，只需从 \(1\) 开始，依次乘上 \(2,3,\dots,100\)。递推式本身也自然包含了边界情形 \(0!=1\)，这正是代码里一个很重要的正确性检查：如果连起点都不对，后续每一步都会错。
把当前值表示为
$$F_k=\sum_{j=0}^{m_k-1} d_j\,10^j,\qquad 0\le d_j\le9.$$
其中 \(d_0\) 是个位，\(d_1\) 是十位，依此类推。按从低位到高位的顺序保存这些数字是最自然的，因为整数乘法总是从最低位开始，并把进位向更高位传递。等到全部乘法结束之后，题目真正需要的量就是
$$s(k)=\sum_{j=0}^{m_k-1} d_j.$$
假设当前数位 \(d_j\) 已经精确表示了 \((k-1)!\)。现在要乘上 \(k\)。令初始进位 \(c_0=0\)，然后对每一位做
$$t_j=kd_j+c_j,\qquad d'_j=t_j\bmod 10,\qquad c_{j+1}=\left\lfloor\frac{t_j}{10}\right\rfloor.$$
所有原有数位处理完之后，如果还剩进位 \(c_{m_k}\)，就继续把它拆成十进制数位追加到末尾。这个过程与手算十进制乘法完全相同。最关键的不变量是：完成乘数 \(k\) 的这一轮后，新的数位数组精确表示 \(k!\)。只要这个不变量保持成立，最后得到的数位和就一定正确。
数位和函数并不满足简单的乘法规律，因为进位会改变高位结构。只知道当前数位和，并不能推出下一次乘法后的数位和。例如 \(8\cdot5=40\)，结果的数位和是 \(4\)，这个值既不是两个数位和的乘积，也不是它们的和。造成差异的正是十进制进位。因此实现必须保留完整的十进制状态，而不是试图只更新一个“数位和”标量。
按照递推式，数值依次变为
$$1,\ 2,\ 6,\ 24,\ 120,\ 720,\ 5040,\ 40320,\ 362880,\ 3628800.$$
于是
$$10!=3628800,\qquad s(10)=3+6+2+8+8+0+0=27.$$
这个例子已经足够说明完整问题中的两个关键现象：一方面，连续乘法中会不断出现进位；另一方面，当因子中积累了足够多的 \(2\) 和 \(5\) 时，十进制表示会自动在末尾出现多个零。
第一条校验来自模 \(9\) 性质。对任意非负整数 \(N\)，都有
$$s(N)\equiv N\pmod 9.$$
由于当 \(n\ge6\) 时，\(n!\) 一定含有因子 \(9\)，所以在本题范围内必然满足 \(s(n!)\equiv0\pmod 9\)。第二条校验来自末尾零的个数，它由 \(5\) 的指数决定：
$$z(n)=\sum_{r\ge1}\left\lfloor\frac{n}{5^r}\right\rfloor.$$
当 \(n=100\) 时，这个值是 \(20+4=24\)。这些零本身对数位和没有贡献，但它们解释了为什么十进制展开最后会有一长串零。数位总长度也可以由
$$D(n)=\lfloor\log_{10}(n!)\rfloor+1$$
估计，再结合 Stirling 公式就能确认 \(100!\) 恰好有 \(158\) 位。所以显式维护一个十进制数位数组，不仅正确，而且规模非常小。
C++ 实现把上面的推导完全显式化。它从十进制数 \(1\) 开始，把当前结果保存为一个低位在前的数位列表，然后依次乘上 \(2\) 到 \(n\) 的每个整数。每一轮都会按进位公式更新所有现有数位，把剩余进位拆成新数位追加到末尾，并始终保持“列表精确表示当前阶乘”的不变量。最后再把列表中的所有数字求和。
Python 和 Java 实现执行的是同一个数学过程，只是把大整数乘法交给运行时的任意精度整数机制来完成。它们先构造出精确的阶乘值，再转成十进制字符串，并把每个字符对应的数字加起来。也就是说，三份实现的差别只在于大整数算术是显式写出来，还是由语言库隐藏起来；数学对象始终都是精确的 \(n!\) 十进制展开。
对显式十进制数位算法而言，设 \(D(k)\) 是 \(k!\) 的十进制位数。把 \((k-1)!\) 乘以 \(k\) 时，需要扫描所有现有数位，并对每一位做常数次运算，因此这一轮代价是 \(O(D(k-1))\)。总时间为
$$\sum_{k=1}^{n} O(D(k))=O\!\left(\sum_{k=1}^{n} k\log k\right)=O(n^2\log n).$$
空间复杂度等于当前十进制展开所需的位数，即 \(O(D(n))=O(n\log n)\)。对本题的实际输入 \(n=100\) 来说，这个规模非常小，因为最终只需保存 \(158\) 位数字，最后的数位求和也是对这 \(158\) 位做一次线性扫描。至于 Python 和 Java 中的任意精度整数实现，内部可能采用更快的乘法策略，但在这个问题上，本质成本仍然是构造并遍历一个精确的阶乘结果。
В задаче требуется найти сумму десятичных цифр числа \(100!\). Значение \(100!=1\cdot2\cdot3\cdots100\) слишком велико для обычных целочисленных типов фиксированной длины: оно содержит \(158\) десятичных цифр и оканчивается \(24\) нулями. Поэтому нужно не приближать факториал, а построить его точную десятичную запись и только потом сложить цифры.
Обозначим \(F_k=k!\), а через \(s(k)\) сумму десятичных цифр числа \(F_k\). Во всех трёх реализациях используется одна и та же математическая схема: факториал растёт по рекуррентной формуле
$$F_0=1,\qquad F_k=kF_{k-1}.$$
Если после каждого умножения хранить точное десятичное представление текущего значения, то итоговая сумма цифр получается непосредственным суммированием цифр финального числа.
Для этой задачи не нужна никакая более сложная теория. Чтобы получить \(100!\), достаточно стартовать с \(1\) и последовательно домножать на \(2,3,\dots,100\). Граничный случай \(0!=1\) уже встроен в эту же формулу и служит полезной проверкой корректности на самом первом шаге.
Запишем
$$F_k=\sum_{j=0}^{m_k-1} d_j\,10^j,\qquad 0\le d_j\le9.$$
Здесь \(d_0\) обозначает цифру единиц, \(d_1\) цифру десятков и так далее. Хранение в порядке от младшего разряда к старшему удобно потому, что умножение на небольшое число начинается с младших разрядов и перенос естественным образом уходит влево. Когда последняя итерация завершена, искомая величина равна
$$s(k)=\sum_{j=0}^{m_k-1} d_j.$$
Пусть цифры \(d_j\) уже представляют число \((k-1)!\). Тогда при умножении на \(k\) мы идём по цифрам слева направо по массиву младших разрядов. При начальном переносе \(c_0=0\) определяем
$$t_j=kd_j+c_j,\qquad d'_j=t_j\bmod 10,\qquad c_{j+1}=\left\lfloor\frac{t_j}{10}\right\rfloor.$$
После обработки всех имеющихся цифр оставшийся перенос \(c_{m_k}\) тоже раскладывается на десятичные цифры и дописывается в конец массива. Это в точности школьное умножение в десятичной системе. Главная инварианта такова: после завершения шага с множителем \(k\) обновлённый массив цифр точно равен \(k!\).
Функция суммы цифр не согласуется с умножением из-за переносов. По одной лишь текущей сумме цифр невозможно восстановить следующую после умножения. Например, \(8\cdot5=40\), и сумма цифр результата равна \(4\); этот переход нельзя вывести из простой формулы, не зная точной десятичной структуры произведения. Поэтому решение хранит полное число, а не только агрегированную сумму цифр.
Рекурсия последовательно даёт
$$1,\ 2,\ 6,\ 24,\ 120,\ 720,\ 5040,\ 40320,\ 362880,\ 3628800.$$
Следовательно,
$$10!=3628800,\qquad s(10)=3+6+2+8+8+0+0=27.$$
Этот пример уже показывает обе существенные особенности полной задачи: переносы возникают многократно, а конечные нули появляются автоматически, когда в факторизации накапливается достаточно множителей \(2\) и \(5\).
Есть две удобные формулы для контроля результата. Первая: для любого неотрицательного целого \(N\)
$$s(N)\equiv N\pmod 9.$$
Поскольку \(n!\) делится на \(9\) при каждом \(n\ge6\), в нашей задаче обязательно должно выполняться \(s(n!)\equiv0\pmod 9\). Вторая формула описывает число конечных нулей через степени пятёрки:
$$z(n)=\sum_{r\ge1}\left\lfloor\frac{n}{5^r}\right\rfloor.$$
Для \(n=100\) получаем \(z(100)=20+4=24\). Эти нули не участвуют в сумме цифр, но объясняют форму конца десятичной записи. Кроме того, число цифр задаётся выражением
$$D(n)=\lfloor\log_{10}(n!)\rfloor+1,$$
а приближение Стирлинга подтверждает, что \(100!\) содержит \(158\) цифр. Значит, явное хранение десятичного массива здесь вполне удобно.
Реализация на C++ буквально следует изложенной схеме. Она начинает с десятичного числа \(1\), хранимого как список из одной цифры, а затем по очереди умножает его на все целые числа от \(2\) до \(n\). На каждом шаге каждая цифра обновляется по формуле переноса, оставшийся перенос раскладывается на новые цифры, и сохраняется инварианта, что массив точно представляет текущий факториал. После последнего умножения все цифры массива суммируются.
Реализации на Python и Java делают то же самое математически, но прячут длинную арифметику внутри стандартных средств произвольной точности. Они строят точное значение факториала, переводят его в десятичную строку и суммируют цифры этой строки. То есть различается только степень явности реализации больших чисел; вычисляемый объект во всех трёх случаях один и тот же.
Для явного десятичного алгоритма обозначим через \(D(k)\) число цифр в \(k!\). Умножение \((k-1)!\) на \(k\) просматривает все \(D(k-1)\) текущих цифр и делает постоянное число операций на цифру. Поэтому суммарное время равно
$$\sum_{k=1}^{n} O(D(k))=O\!\left(\sum_{k=1}^{n} k\log k\right)=O(n^2\log n).$$
Память равна длине текущей десятичной записи, то есть \(O(D(n))=O(n\log n)\) цифр. Для фактического входа \(n=100\) это очень мало: в финале хранится лишь \(158\) цифр, а итоговый проход по ним линейный. Встроенные реализации длинной арифметики могут использовать более быстрые внутренние методы умножения, но на масштабе этой задачи их стоимость всё равно определяется построением и просмотром одного точного факториала.
المطلوب هو إيجاد مجموع الأرقام العشرية للعدد \(100!\). والعدد \(100!=1\cdot2\cdot3\cdots100\) أكبر بكثير من أن يُخزَّن في أنواع الأعداد الصحيحة ذات السعة الثابتة المعتادة؛ فهو يتكون من \(158\) رقماً عشرياً وينتهي بـ \(24\) صفراً. لذلك فجوهر المسألة ليس التقريب، بل بناء التمثيل العشري الدقيق لـ \(100!\) ثم جمع أرقامه.
لنكتب \(F_k=k!\)، ولتكن \(s(k)\) مجموع الأرقام العشرية للعدد \(F_k\). تعتمد التطبيقات الثلاثة على الفكرة الرياضية نفسها: العاملية تنمو وفق العلاقة التكرارية
$$F_0=1,\qquad F_k=kF_{k-1}.$$
فإذا استطعنا حفظ التمثيل العشري الدقيق بعد كل عملية ضرب، فإن مجموع الأرقام في النهاية يصبح مجرد جمع مباشر لأرقام التمثيل النهائي.
لا تحتاج هذه المسألة إلى تحويل تركيبي معقد. للوصول إلى \(100!\) يكفي أن نبدأ من \(1\) ثم نضرب بالتتابع في \(2,3,\dots,100\). كما أن الحالة الحدية \(0!=1\) تظهر طبيعياً داخل الإطار نفسه، وهي نقطة فحص مفيدة للتأكد من أن البناء يبدأ بشكل صحيح.
نكتب
$$F_k=\sum_{j=0}^{m_k-1} d_j\,10^j,\qquad 0\le d_j\le9.$$
حيث يمثّل \(d_0\) رقم الآحاد و\(d_1\) رقم العشرات وهكذا. والاحتفاظ بالأرقام من الأقل أهمية إلى الأعلى مناسب جداً، لأن الضرب يبدأ من الآحاد ثم يدفع الحمل إلى الخانات الأعلى. وبعد اكتمال البناء، تكون الكمية المطلوبة ببساطة
$$s(k)=\sum_{j=0}^{m_k-1} d_j.$$
افترض أن الأرقام \(d_j\) تمثل بدقة العدد \((k-1)!\). عند الضرب في \(k\)، نعالج كل خانة على حدة. مع حمل ابتدائي \(c_0=0\)، نعرّف
$$t_j=kd_j+c_j,\qquad d'_j=t_j\bmod 10,\qquad c_{j+1}=\left\lfloor\frac{t_j}{10}\right\rfloor.$$
وبعد الانتهاء من جميع الخانات الموجودة، يُفكك الحمل المتبقي \(c_{m_k}\) إلى أرقام عشرية جديدة تُلحق في النهاية. هذا هو الضرب المدرسي نفسه في الأساس \(10\). والثابت الأساسي هنا هو: بعد إنهاء خطوة الضرب في \(k\)، تمثل مصفوفة الأرقام الجديدة العدد \(k!\) تمثيلاً دقيقاً تماماً.
دالة مجموع الأرقام ليست دالة ضربٍ بسيطة، لأن الحمل يغيّر البنية العشرية. إذا عرفت مجموع الأرقام الحالي فقط، فلن تتمكن من استنتاج مجموع الأرقام بعد الضرب التالي. فمثلاً \(8\cdot5=40\)، ومجموع أرقام الناتج هو \(4\)، وهذا لا يُستنتج من مجرد معرفة مجاميع الأرقام السابقة من دون معرفة ما أحدثه الحمل. لذلك يجب أن تحتفظ الخوارزمية بالحالة العشرية الكاملة، لا بمجرد مجموعٍ واحد.
تعطي العلاقة التكرارية السلسلة
$$1,\ 2,\ 6,\ 24,\ 120,\ 720,\ 5040,\ 40320,\ 362880,\ 3628800.$$
ومن ثم
$$10!=3628800,\qquad s(10)=3+6+2+8+8+0+0=27.$$
هذا المثال يكشف بالفعل الظاهرتين الأساسيتين في المسألة الكاملة: الأحمال تتولد على عدة مراحل، والأصفار النهائية تظهر تلقائياً عندما يتراكم عدد كافٍ من العوامل \(2\) و\(5\).
هناك صيغتان كلاسيكيتان تفيدان في التحقق من النتيجة. الأولى تقول إنه لأي عدد صحيح غير سالب \(N\)، لدينا
$$s(N)\equiv N\pmod 9.$$
وبما أن \(n!\) يقبل القسمة على \(9\) لكل \(n\ge6\)، فيجب أن يتحقق \(s(n!)\equiv0\pmod 9\) في هذه المسألة. أما الصيغة الثانية فتصف عدد الأصفار النهائية عبر أسس العدد \(5\):
$$z(n)=\sum_{r\ge1}\left\lfloor\frac{n}{5^r}\right\rfloor.$$
وعند \(n=100\) نحصل على \(z(100)=20+4=24\). هذه الأصفار لا تضيف شيئاً إلى مجموع الأرقام، لكنها تفسر الشكل النهائي للتمثيل العشري. كما أن عدد الأرقام نفسه يقدَّر من
$$D(n)=\lfloor\log_{10}(n!)\rfloor+1,$$
ومع تقريب ستيرلنغ نصل إلى أن \(100!\) يتكون من \(158\) رقماً، ولهذا فطريقة الاحتفاظ الصريح بالأرقام العشرية عملية تماماً هنا.
التنفيذ في C++ يطبق الاشتقاق الرياضي مباشرة. يبدأ من العدد العشري \(1\) المخزن على هيئة قائمة من رقم واحد، ثم يضربه بالتتابع في كل الأعداد من \(2\) حتى \(n\). في كل دورة تُحدَّث كل خانة وفق علاقة الحمل، وتُلحق أرقام الحمل المتبقية، ويُحفَظ الثابت القائل إن القائمة تمثل العاملية الحالية بدقة تامة. وفي النهاية تُجمع الأرقام الموجودة في هذه القائمة.
أما تنفيذا Python وJava فيؤديان الحساب الرياضي نفسه على مستوى أعلى. فهما يبنيان العاملية الدقيقة باستخدام أعداد صحيحة ذات دقة غير محدودة من بيئة التشغيل، ثم يحولان الناتج إلى نص عشري ويجمعان رموزه الرقمية. إذن الاختلاف بين اللغات ليس في الرياضيات، بل فقط في مدى ظهور حساب الأعداد الكبيرة صراحة داخل الشيفرة.
في خوارزمية الأرقام العشرية الصريحة، إذا رمزنا بـ \(D(k)\) إلى عدد أرقام \(k!\)، فإن ضرب \((k-1)!\) في \(k\) يمر مرة واحدة على \(D(k-1)\) خانة ويؤدي عملاً ثابتاً لكل خانة. لذا يكون الزمن الكلي
$$\sum_{k=1}^{n} O(D(k))=O\!\left(\sum_{k=1}^{n} k\log k\right)=O(n^2\log n).$$
أما الذاكرة المطلوبة فهي طول التمثيل العشري الحالي، أي \(O(D(n))=O(n\log n)\) خانة. وبالنسبة إلى قيمة Project Euler وهي \(n=100\)، فإن هذا الحجم صغير جداً: التمثيل النهائي لا يحتاج إلا إلى \(158\) رقماً، وتمرير جمع الأرقام في النهاية خطي في هذا الطول. وقد تستعمل البيئات ذات الدقة غير المحدودة خوارزميات ضرب أسرع داخلياً، لكن الكلفة الجوهرية في هذه المسألة تبقى بناء عاملية دقيقة واحدة ثم المرور على أرقامها.