Let \(F(n)\) be the sum of the factorials of the decimal digits of \(n\). Problem 34 asks for all positive integers satisfying \(F(n)=n\), and then for the sum of the non-trivial ones. The equalities \(1=1!\) and \(2=2!\) are excluded because the problem is interested in numbers that arise as a genuine sum of digit factorials rather than a one-term identity.
So the target objects are the non-trivial fixed points of the digit-factorial map in base 10. The implementations solve the problem in a mathematically complete way: prove a finite search range, precompute the ten factorial values, and test every candidate inside that proven range.
The entire method comes from three simple but decisive observations: every decimal digit contributes at most \(9!\), the number of digits forces a lower bound on \(n\), and factorials of digits can be reused through a tiny lookup table.
If the decimal digits of \(n\) are \(d_1,d_2,\dots,d_k\), define
$$F(n)=d_1!+d_2!+\cdots+d_k!.$$
We are looking for numbers with \(F(n)=n\). That is a fixed-point equation, but it is a very concrete one: each digit contributes independently through its factorial. The contribution of a zero digit is especially important, because \(0!=1\), not \(0\). This matters in the example \(40585\).
The implementations therefore precompute the ten values \(0!,1!,\dots,9!\) once, using the recurrence
$$f_0=1,\qquad f_d=d\,f_{d-1}\quad(1\le d\le 9).$$
After that, evaluating \(F(n)\) is just a digit scan with table lookups.
Suppose \(n\) has exactly \(k\) decimal digits. Then each digit contributes at most \(9!=362{,}880\), so
$$F(n)\le k\cdot 9!.$$
On the other hand, every \(k\)-digit number satisfies
$$n\ge 10^{k-1}.$$
Therefore a \(k\)-digit solution can exist only if
$$10^{k-1}\le k\cdot 9!.$$
The left side grows exponentially with \(k\), while the right side grows only linearly. So beyond some digit length the inequality fails permanently, which means there can be only finitely many decimal solutions.
The code does not hard-code the bound; it derives it by advancing through digit lengths until the smallest number with that many digits is larger than the largest possible digit-factorial sum for that same length.
For seven digits we still have
$$7\cdot 9!=2{,}540{,}160,$$
which is large enough to cover all possible seven-digit candidates. But for eight digits,
$$8\cdot 9!=2{,}903{,}040<10^7,$$
so no eight-digit number can ever equal the sum of the factorials of its digits. Hence every solution lies in the interval
$$10\le n\le 7\cdot 9!=2{,}540{,}160.$$
Once this inequality is proved, a complete scan of that interval is not a heuristic. It is a proof-producing exhaustive search.
The two non-trivial decimal factorions are easy to verify directly:
$$145=1!+4!+5!=1+24+120,$$
$$40585=4!+0!+5!+8!+5!=24+1+120+40{,}320+120.$$
The second example shows why handling \(0!=1\) correctly is essential. Because the search over the entire proven interval finds no further values, these are the only non-trivial solutions in base 10.
The required total is therefore
$$145+40585=40{,}730.$$
The C++, Python, and Java implementations first build the ten-entry factorial table iteratively. They then walk upward through possible digit lengths, keeping track of the smallest number with the current length and the largest digit-factorial sum compatible with that length. The first length for which the lower bound overtakes the upper bound is impossible, so the previous length yields the final search limit.
To evaluate a candidate, the implementation repeatedly takes the last decimal digit, adds the precomputed factorial of that digit to a running total, and removes the digit from the remaining prefix. After each iteration, the running total equals the sum of the factorials of the digits already peeled off. When no digits remain, the running total is exactly \(F(n)\), and comparing it with the original number decides whether the candidate is a factorion.
The scan begins at \(10\), which automatically excludes the one-digit trivialities. Every candidate satisfying \(F(n)=n\) is added to the final sum. Before the full sweep, the implementations also validate the two known non-trivial examples \(145\) and \(40585\); these checkpoints make sure the digit-factorial evaluation is correct before the exhaustive pass starts.
Let
$$U=7\cdot 9!=2{,}540{,}160.$$
Each candidate requires one decimal digit scan, and every scanned candidate has at most seven digits. So the running time is
$$O(U\cdot 7)=O(U),$$
with a very small constant factor in practice.
The extra space is constant: only the ten factorial values and a handful of counters are stored. That is \(O(10)\), equivalently \(O(1)\).
Sei \(F(n)\) die Summe der Fakultäten der Dezimalziffern von \(n\). In Problem 34 sollen alle positiven ganzen Zahlen mit \(F(n)=n\) gefunden werden, und anschließend die Summe der nichttrivialen Lösungen. Die Gleichungen \(1=1!\) und \(2=2!\) werden ausgeschlossen, weil das Problem Zahlen sucht, die als echte Summe von Ziffernfakultäten entstehen und nicht nur als einstelliges Identitätsbeispiel.
Gesucht sind also die nichttrivialen Fixpunkte der Ziffern-Fakultäts-Abbildung im Dezimalsystem. Die Implementierungen lösen das vollständig mathematisch: Zuerst wird ein endlicher Suchbereich bewiesen, dann werden die zehn Fakultätswerte vorgerechnet, und schließlich wird jeder Kandidat in diesem bewiesenen Bereich getestet.
Die ganze Lösung beruht auf drei einfachen Beobachtungen: Jede Dezimalziffer trägt höchstens \(9!\) bei, die Stellenzahl liefert eine untere Schranke für \(n\), und Ziffernfakultäten lassen sich in einer winzigen Tabelle wiederverwenden.
Hat \(n\) die Dezimalziffern \(d_1,d_2,\dots,d_k\), so definieren wir
$$F(n)=d_1!+d_2!+\cdots+d_k!.$$
Gesucht sind Zahlen mit \(F(n)=n\). Das ist eine Fixpunktgleichung, aber eine sehr konkrete: Jede Ziffer wirkt unabhängig über ihre Fakultät. Besonders wichtig ist, dass eine Nullziffer den Beitrag \(0!=1\) liefert und nicht \(0\). Genau das spielt bei \(40585\) eine Rolle.
Darum berechnen die Implementierungen die zehn Werte \(0!,1!,\dots,9!\) einmal vor, und zwar mit der Rekursion
$$f_0=1,\qquad f_d=d\,f_{d-1}\quad(1\le d\le 9).$$
Danach besteht die Auswertung von \(F(n)\) nur noch aus einem Ziffernscan mit Tabellenzugriffen.
Angenommen, \(n\) hat genau \(k\) Dezimalstellen. Dann trägt jede Ziffer höchstens \(9!=362{,}880\) bei, also gilt
$$F(n)\le k\cdot 9!.$$
Gleichzeitig erfüllt jede \(k\)-stellige Zahl
$$n\ge 10^{k-1}.$$
Eine \(k\)-stellige Lösung kann also nur existieren, wenn
$$10^{k-1}\le k\cdot 9!.$$
Die linke Seite wächst exponentiell in \(k\), die rechte nur linear. Also schlägt die Ungleichung ab einer gewissen Stellenzahl dauerhaft fehl. Damit gibt es nur endlich viele Lösungen im Dezimalsystem.
Der Code schreibt die obere Grenze nicht fest hinein, sondern leitet sie ab: Er geht Stellenzahl für Stellenzahl voran und vergleicht die kleinste Zahl mit dieser Stellenzahl mit der größtmöglichen Summe von Ziffernfakultäten derselben Länge.
Für sieben Stellen gilt noch
$$7\cdot 9!=2{,}540{,}160,$$
also ist ein vollständiger Test aller möglichen siebenstelligen Kandidaten sinnvoll. Für acht Stellen erhält man jedoch
$$8\cdot 9!=2{,}903{,}040<10^7,$$
und damit kann keine achtstellige Zahl mehr die Summe ihrer Ziffernfakultäten sein. Folglich liegt jede Lösung im Intervall
$$10\le n\le 7\cdot 9!=2{,}540{,}160.$$
Ist diese Schranke einmal bewiesen, dann ist die anschließende vollständige Suche ein exakter Nachweis und keine bloße Heuristik.
Die beiden nichttrivialen Factorions im Dezimalsystem lassen sich direkt überprüfen:
$$145=1!+4!+5!=1+24+120,$$
$$40585=4!+0!+5!+8!+5!=24+1+120+40{,}320+120.$$
Das zweite Beispiel zeigt noch einmal, warum \(0!=1\) korrekt berücksichtigt werden muss. Da der vollständige Test im gesamten bewiesenen Bereich keine weiteren Werte findet, sind dies die einzigen nichttrivialen Lösungen in Basis 10.
Die gesuchte Summe lautet also
$$145+40585=40{,}730.$$
Die C++-, Python- und Java-Implementierungen erzeugen zuerst iterativ die Tabelle mit den zehn Fakultätswerten. Danach laufen sie über die möglichen Stellenzahlen und verfolgen dabei sowohl die kleinste Zahl einer gegebenen Länge als auch die größte mögliche Ziffern-Fakultätssumme derselben Länge. Sobald die untere Schranke größer wird als die obere, ist diese Stellenzahl unmöglich, und die vorherige liefert das endgültige Suchlimit.
Zur Auswertung eines Kandidaten wird wiederholt die letzte Dezimalziffer genommen, ihre vorgerechnete Fakultät zu einer laufenden Summe addiert und die Ziffer aus dem Restpräfix entfernt. Nach jedem Schritt ist die laufende Summe genau die Summe der Fakultäten der bereits abgetrennten Ziffern. Sind keine Ziffern mehr übrig, ist die laufende Summe exakt \(F(n)\), und der Vergleich mit der ursprünglichen Zahl entscheidet den Test.
Die Suche beginnt bei \(10\), wodurch die trivialen einstelligen Fälle automatisch wegfallen. Jeder Kandidat mit \(F(n)=n\) wird zur Endsumme addiert. Vor dem vollständigen Durchlauf prüfen die Implementierungen außerdem die beiden bekannten nichttrivialen Beispiele \(145\) und \(40585\); diese Kontrollpunkte bestätigen, dass die Ziffern-Fakultäts-Auswertung korrekt arbeitet.
Sei
$$U=7\cdot 9!=2{,}540{,}160.$$
Jeder Kandidat benötigt genau einen Dezimalziffern-Scan, und jede geprüfte Zahl hat höchstens sieben Stellen. Damit ergibt sich für die Laufzeit
$$O(U\cdot 7)=O(U),$$
praktisch also nur einige Millionen sehr einfacher Ziffernoperationen.
Der zusätzliche Speicher ist konstant: Gespeichert werden nur die zehn Fakultätswerte und wenige Zähler. Das ist \(O(10)\), also äquivalent zu \(O(1)\).
\(F(n)\), \(n\) sayısının onluk tabandaki rakamlarının faktöriyelleri toplamı olsun. Problem 34, \(F(n)=n\) eşitliğini sağlayan tüm pozitif tam sayıları ve ardından bu çözümlerin önemsiz olmayanlarının toplamını ister. \(1=1!\) ve \(2=2!\) eşitlikleri, problem gerçek bir rakam-faktöriyel toplamı aradığı için dışarıda bırakılır.
Dolayısıyla aranan nesneler, onluk tabanda rakam-faktöriyel dönüşümünün önemsiz olmayan sabit noktalarıdır. Uygulamalar bunu eksiksiz biçimde çözer: önce sonlu bir arama aralığı kanıtlanır, sonra \(0!\) ile \(9!\) arasındaki on değer önceden hesaplanır, en son da bu aralıktaki tüm adaylar denenir.
Tüm yöntem üç gözleme dayanır: her rakam en fazla \(9!\) katkı yapabilir, basamak sayısı \(n\) için bir alt sınır verir ve rakam faktöriyelleri küçük bir tabloda tekrar tekrar kullanılabilir.
\(n\) sayısının onluk tabandaki rakamları \(d_1,d_2,\dots,d_k\) ise
$$F(n)=d_1!+d_2!+\cdots+d_k!$$
olarak tanımlarız. Aradığımız sayılar \(F(n)=n\) koşulunu sağlar; yani bu dönüşümün sabit noktalarıdır. Burada özellikle sıfır rakamının katkısı önemlidir, çünkü \(0!=1\) olur. \(40585\) örneğinde bu ayrıntı belirleyicidir.
Bu yüzden uygulamalar \(0!,1!,\dots,9!\) değerlerini tek seferde şu yineleme ile üretir:
$$f_0=1,\qquad f_d=d\,f_{d-1}\quad(1\le d\le 9).$$
Bundan sonra \(F(n)\) hesabı yalnızca rakamları ayırıp tablodan bakmaktan ibarettir.
\(n\) tam olarak \(k\) basamaklı olsun. Her rakam en fazla \(9!=362{,}880\) katkı yaptığı için
$$F(n)\le k\cdot 9!$$
elde edilir. Öte yandan her \(k\)-basamaklı sayı için
$$n\ge 10^{k-1}$$
olur. O halde \(k\)-basamaklı bir çözüm ancak
$$10^{k-1}\le k\cdot 9!$$
durumunda mümkün olabilir. Sol taraf \(k\) ile üstel büyür, sağ taraf ise doğrusal büyür. Bu yüzden belli bir basamak sayısından sonra eşitsizlik artık hiç sağlanamaz ve çözüm sayısı sonlu olur.
Kod üst sınırı sabit yazmaz; onu basamak sayısı üzerinden türetir. Her adımda, belirli bir basamak uzunluğundaki en küçük sayı ile aynı uzunlukta elde edilebilecek en büyük rakam-faktöriyel toplamı karşılaştırılır.
Yedi basamak için hâlâ
$$7\cdot 9!=2{,}540{,}160$$
vardır ve bu tüm olası yedi basamaklı adayları kapsar. Fakat sekiz basamakta
$$8\cdot 9!=2{,}903{,}040<10^7$$
olduğu için hiçbir sekiz basamaklı sayı kendi rakam faktöriyelleri toplamına eşit olamaz. Demek ki tüm çözümler şu aralıkta kalmak zorundadır:
$$10\le n\le 7\cdot 9!=2{,}540{,}160.$$
Bu eşitsizlik kanıtlandıktan sonra bu aralığın tamamını taramak sezgisel bir yaklaşım değil, tam bir kapsayıcı aramadır.
Onluk tabandaki iki önemsiz olmayan faktöriyon doğrudan doğrulanabilir:
$$145=1!+4!+5!=1+24+120,$$
$$40585=4!+0!+5!+8!+5!=24+1+120+40{,}320+120.$$
İkinci örnek, \(0!=1\) ayrıntısının neden doğru ele alınması gerektiğini açıkça gösterir. Kanıtlanmış aralığın tamamı tarandığında başka hiçbir değer bulunmadığı için, bunlar onluk tabandaki tek önemsiz olmayan çözümlerdir.
İstenen toplam da
$$145+40585=40{,}730$$
olur.
C++, Python ve Java uygulamaları önce on elemanlı faktöriyel tablosunu iteratif olarak kurar. Ardından olası basamak sayılarını sırayla gezerken bir yandan o uzunluktaki en küçük sayıyı, diğer yandan aynı uzunluk için mümkün olan en büyük rakam-faktöriyel toplamını izler. Alt sınır üst sınırı geçtiği anda o basamak sayısının imkansız olduğu anlaşılır ve bir önceki uzunluk nihai arama sınırını verir.
Bir aday değerlendirilirken son rakam tekrar tekrar alınır, o rakamın önceden hesaplanmış faktöriyeli akan toplama eklenir ve rakam geriye kalan ön ekten atılır. Her adım sonunda akan toplam, artık çıkarılmış rakamların faktöriyeller toplamına eşittir. Hiç rakam kalmadığında elde edilen değer tam olarak \(F(n)\) olur; sonra da bu değer adayın kendisiyle karşılaştırılır.
Tarama \(10\) sayısından başlar; böylece tek basamaklı önemsiz durumlar otomatik olarak dışarıda kalır. \(F(n)=n\) şartını sağlayan her aday sonuca eklenir. Ayrıca tam tarama başlamadan önce uygulamalar \(145\) ve \(40585\) örneklerini doğrular; bu kontrol noktaları rakam-faktöriyel hesabının doğru çalıştığını garanti eder.
Şu üst sınırı yazalım:
$$U=7\cdot 9!=2{,}540{,}160.$$
Her aday için tek bir rakam taraması gerekir ve incelenen her sayı en fazla yedi basamaklıdır. Bu nedenle çalışma süresi
$$O(U\cdot 7)=O(U)$$
olur; pratikte bu yalnızca birkaç milyon çok basit rakam işlemidir.
Ek bellek sabittir: yalnızca on faktöriyel değeri ve birkaç sayaç tutulur. Bu da \(O(10)\), yani eşdeğer olarak \(O(1)\) bellek demektir.
Sea \(F(n)\) la suma de los factoriales de las cifras decimales de \(n\). El Problema 34 pide encontrar todos los enteros positivos que satisfacen \(F(n)=n\) y luego sumar las soluciones no triviales. Las igualdades \(1=1!\) y \(2=2!\) se excluyen porque el enunciado busca números que aparezcan como una suma real de factoriales de cifras, no como una identidad de un solo término.
Por tanto, los objetos matemáticos relevantes son los puntos fijos no triviales de la aplicación cifra-factorial en base 10. Las implementaciones resuelven esto de manera completa: primero demuestran que el rango de búsqueda es finito, después precalculan los diez factoriales posibles, y finalmente prueban cada candidato dentro de ese intervalo demostrado.
Toda la solución descansa en tres hechos muy concretos: cada cifra decimal aporta como máximo \(9!\), el número de cifras impone una cota inferior sobre \(n\), y los factoriales de cifras pueden reutilizarse desde una tabla diminuta.
Si las cifras decimales de \(n\) son \(d_1,d_2,\dots,d_k\), definimos
$$F(n)=d_1!+d_2!+\cdots+d_k!.$$
Buscamos números con \(F(n)=n\). Es una ecuación de punto fijo, pero muy concreta: cada cifra contribuye de forma independiente a través de su factorial. La cifra cero merece atención especial, porque \(0!=1\), no \(0\). Eso es exactamente lo que interviene en \(40585\).
Por ello, las implementaciones construyen una sola vez los diez valores \(0!,1!,\dots,9!\) mediante la recurrencia
$$f_0=1,\qquad f_d=d\,f_{d-1}\quad(1\le d\le 9).$$
Después, evaluar \(F(n)\) se reduce a recorrer las cifras y consultar la tabla.
Supongamos que \(n\) tiene exactamente \(k\) cifras decimales. Entonces cada cifra aporta a lo sumo \(9!=362{,}880\), así que
$$F(n)\le k\cdot 9!.$$
Al mismo tiempo, cualquier número de \(k\) cifras satisface
$$n\ge 10^{k-1}.$$
Por lo tanto, una solución de \(k\) cifras solo puede existir si
$$10^{k-1}\le k\cdot 9!.$$
El lado izquierdo crece exponencialmente con \(k\), mientras que el derecho solo crece linealmente. Así, a partir de cierta longitud la desigualdad falla para siempre, lo que demuestra que solo puede haber un número finito de soluciones decimales.
El código no fija la cota superior a mano; la deduce recorriendo las longitudes posibles y comparando el menor número con esa cantidad de cifras con la mayor suma de factoriales de cifras compatible con la misma longitud.
Para siete cifras todavía tenemos
$$7\cdot 9!=2{,}540{,}160,$$
de modo que sigue teniendo sentido revisar todos los candidatos posibles de hasta siete cifras. Pero para ocho cifras ocurre que
$$8\cdot 9!=2{,}903{,}040<10^7,$$
y eso hace imposible que un número de ocho cifras sea igual a la suma de los factoriales de sus cifras. En consecuencia, toda solución está dentro del intervalo
$$10\le n\le 7\cdot 9!=2{,}540{,}160.$$
Una vez demostrada esta desigualdad, recorrer por fuerza bruta todo ese rango es una búsqueda exhaustiva justificada, no una suposición experimental.
Los dos factoriones decimales no triviales se verifican de inmediato:
$$145=1!+4!+5!=1+24+120,$$
$$40585=4!+0!+5!+8!+5!=24+1+120+40{,}320+120.$$
El segundo ejemplo muestra otra vez por qué es esencial tratar \(0!=1\) correctamente. Como el barrido completo del intervalo demostrado no encuentra más valores, estas son las únicas soluciones no triviales en base 10.
La suma pedida es entonces
$$145+40585=40{,}730.$$
Las implementaciones en C++, Python y Java construyen primero de forma iterativa la tabla con los diez factoriales. Después avanzan por las posibles longitudes decimales, siguiendo a la vez el menor número con esa longitud y la mayor suma de factoriales de cifras que esa longitud podría producir. En cuanto la cota inferior supera a la superior, esa longitud queda descartada y la anterior determina el límite final de búsqueda.
Para evaluar un candidato, la implementación toma repetidamente la última cifra decimal, añade a una suma acumulada el factorial precalculado de esa cifra y elimina la cifra del prefijo restante. Tras cada iteración, la suma acumulada coincide con la suma de los factoriales de las cifras ya extraídas. Cuando ya no quedan cifras, el total acumulado es exactamente \(F(n)\), y compararlo con el valor original decide si el candidato es un factorión.
El recorrido empieza en \(10\), lo que excluye automáticamente los casos triviales de una sola cifra. Todo candidato que cumple \(F(n)=n\) se añade a la suma final. Antes del barrido completo, las implementaciones también verifican los dos ejemplos no triviales conocidos, \(145\) y \(40585\); esos puntos de control confirman que la evaluación de factoriales de cifras es correcta.
Definamos
$$U=7\cdot 9!=2{,}540{,}160.$$
Cada candidato necesita un único recorrido por sus cifras, y cada número examinado tiene como máximo siete cifras. Por ello, el tiempo total es
$$O(U\cdot 7)=O(U),$$
con una constante práctica muy pequeña.
La memoria extra es constante: solo se almacenan los diez factoriales y unos pocos contadores. Eso es \(O(10)\), o equivalentemente \(O(1)\).
记 \(F(n)\) 为整数 \(n\) 的十进制各位数字阶乘之和。第 34 题要求找出所有满足 \(F(n)=n\) 的正整数，然后把其中非平凡的解相加。等式 \(1=1!\) 与 \(2=2!\) 被排除在外，因为题目强调的是“由各位数字阶乘求和得到自身”的数，而不是只有一项的平凡恒等式。
因此，真正要寻找的是十进制下这个“数字阶乘映射”的非平凡不动点。三种实现都遵循同一条完整路线：先证明搜索区间必然有限，再预计算 \(0!\) 到 \(9!\) 这十个值，最后对证明出来的全部候选范围做穷尽检查。
整道题之所以可以直接暴力扫描，并不是因为运气好，而是因为背后有三个明确的数学事实：每一位数字的贡献上界是 \(9!\)，数字位数本身给出了 \(n\) 的下界，而阶乘值只需要计算十次就能反复复用。
如果 \(n\) 的十进制数字是 \(d_1,d_2,\dots,d_k\)，那么定义
$$F(n)=d_1!+d_2!+\cdots+d_k!.$$
题目要求的就是满足 \(F(n)=n\) 的数，也就是这个映射的固定点。这里有一个很容易忽略但必须正确处理的细节：数字 \(0\) 的贡献不是 0，而是 \(0!=1\)。数 \(40585\) 之所以成立，正是因为中间那个 0 要贡献 1。
因此，程序第一步就把 \(0!,1!,\dots,9!\) 全部预先算好。实现中使用的递推关系是
$$f_0=1,\qquad f_d=d\,f_{d-1}\quad(1\le d\le 9).$$
有了这张十项表之后，计算 \(F(n)\) 就只剩下逐位拆分和查表相加。
设 \(n\) 恰好有 \(k\) 位十进制数字。由于每一位最多贡献 \(9!=362{,}880\)，于是一定有
$$F(n)\le k\cdot 9!.$$
另一方面，任何一个 \(k\) 位数都满足
$$n\ge 10^{k-1}.$$
因此，若要存在 \(k\) 位解，就必须满足
$$10^{k-1}\le k\cdot 9!.$$
左边随着 \(k\) 指数增长，右边却只按线性增长，所以一旦位数足够大，这个不等式就会永久失效。也就是说，十进制解的个数必然有限。
程序并没有把上界写死成某个神秘常数，而是按位数逐步推出它。思路是：对每一种位数，比较“该位数的最小整数”和“该位数下数字阶乘和的最大可能值”；一旦前者超过后者，这个位数就彻底不可能出现解。
对七位数来说，仍然有
$$7\cdot 9!=2{,}540{,}160,$$
所以七位范围内还需要完整检查。可是一旦到八位数，就有
$$8\cdot 9!=2{,}903{,}040<10^7,$$
这说明任何八位数都不可能等于其数字阶乘和。于是所有候选数都被严格限制在
$$10\le n\le 7\cdot 9!=2{,}540{,}160$$
这个区间里。证明出这个范围以后，再去遍历整个区间就是严格穷举，而不是经验性猜测。
十进制下两个非平凡 factorion 可以直接验算：
$$145=1!+4!+5!=1+24+120,$$
$$40585=4!+0!+5!+8!+5!=24+1+120+40{,}320+120.$$
第二个例子再次说明，\(0!=1\) 这一点绝不能漏掉。由于对整个已证明区间的完全扫描再也找不到别的值，所以这两个就是十进制下全部非平凡解。
题目要求的总和因此为
$$145+40585=40{,}730.$$
C++、Python 和 Java 三个实现都会先用递推方式建立十项阶乘表。随后，程序按位数向上推进，同时维护“当前位数下的最小整数”和“当前位数下数字阶乘和的最大可能值”。当最小整数第一次超过最大可能和时，说明这个位数已经不可能产生解，于是上一位数对应的最大和就是最终搜索上界。
检测一个候选数时，程序反复取出它的最后一位，把该位对应的阶乘值加入累计和，然后把这一位从剩余前缀中删除。每做完一步，累计和都恰好等于“已经剥离出去的那些数字”的阶乘和；还没处理的部分则完整保留在剩余前缀中。等所有数字都处理完，累计和就正好等于 \(F(n)\)，再和原数比较即可判定。
扫描从 \(10\) 开始，因此一位数的平凡情形自动不会进入结果。凡是满足 \(F(n)=n\) 的候选数都会被加入最终答案。除此之外，完整扫描之前，三个实现还会先验证 \(145\) 和 \(40585\) 这两个已知非平凡例子，以确认数字阶乘求和逻辑没有偏差。
记
$$U=7\cdot 9!=2{,}540{,}160.$$
每个候选数只需要做一次按十进制位的扫描，而每个被检查的数最多只有 7 位，因此总时间复杂度为
$$O(U\cdot 7)=O(U),$$
实际常数也非常小，本质上只是几百万次简单的取位和查表操作。
额外空间是常数级的：程序只保存 10 个阶乘值以及少量计数变量，所以空间复杂度是 \(O(10)\)，也就是 \(O(1)\)。
Обозначим через \(F(n)\) сумму факториалов десятичных цифр числа \(n\). В задаче 34 требуется найти все положительные целые числа, для которых выполняется \(F(n)=n\), а затем сложить нетривиальные решения. Равенства \(1=1!\) и \(2=2!\) исключаются, потому что задача интересуется числами, возникающими как настоящая сумма факториалов цифр, а не как одночленный частный случай.
Итак, нужно найти нетривиальные неподвижные точки отображения «сумма факториалов цифр» в десятичной системе. Реализации делают это полностью строго: сначала доказывают конечность диапазона поиска, затем предвычисляют десять возможных значений факториала цифры, после чего перебирают все кандидаты внутри доказанного диапазона.
Вся идея строится на трех фактах: вклад каждой десятичной цифры не превосходит \(9!\), число цифр задает нижнюю границу для самого \(n\), а факториалы цифр можно заранее посчитать в крошечной таблице и потом многократно переиспользовать.
Если десятичные цифры числа \(n\) равны \(d_1,d_2,\dots,d_k\), положим
$$F(n)=d_1!+d_2!+\cdots+d_k!.$$
Мы ищем числа, для которых \(F(n)=n\). Это уравнение на неподвижные точки, но в очень конкретном виде: каждая цифра независимо вносит свой факториальный вклад. Особенно важно правильно учитывать цифру 0, потому что \(0!=1\), а не \(0\). Именно это существенно в примере \(40585\).
Поэтому реализации один раз строят таблицу из значений \(0!,1!,\dots,9!\), используя рекуррентную формулу
$$f_0=1,\qquad f_d=d\,f_{d-1}\quad(1\le d\le 9).$$
После этого вычисление \(F(n)\) сводится к проходу по цифрам и обращениям к таблице.
Пусть \(n\) имеет ровно \(k\) десятичных цифр. Тогда каждая цифра дает вклад не больше \(9!=362{,}880\), следовательно
$$F(n)\le k\cdot 9!.$$
С другой стороны, любое \(k\)-значное число удовлетворяет неравенству
$$n\ge 10^{k-1}.$$
Значит, \(k\)-значное решение может существовать только при условии
$$10^{k-1}\le k\cdot 9!.$$
Левая часть растет по \(k\) экспоненциально, а правая лишь линейно. Поэтому начиная с некоторой длины это неравенство уже никогда не выполнится, и число десятичных решений обязано быть конечным.
В коде верхняя граница не подставлена вручную. Она выводится последовательным просмотром возможных длин числа и сравнением наименьшего числа данной длины с максимально возможной суммой факториалов цифр той же длины.
Для семи цифр еще имеем
$$7\cdot 9!=2{,}540{,}160,$$
так что все потенциальные семизначные кандидаты остаются в игре. Но для восьми цифр получается
$$8\cdot 9!=2{,}903{,}040<10^7,$$
и это сразу исключает всякое восьмизначное решение. Следовательно, любое решение обязано лежать в интервале
$$10\le n\le 7\cdot 9!=2{,}540{,}160.$$
После доказательства этой оценки полный перебор указанного промежутка становится строгим исчерпывающим поиском, а не эвристикой.
Два нетривиальных десятичных факториона проверяются напрямую:
$$145=1!+4!+5!=1+24+120,$$
$$40585=4!+0!+5!+8!+5!=24+1+120+40{,}320+120.$$
Второй пример еще раз показывает, почему \(0!=1\) нужно учитывать без ошибок. Поскольку полный просмотр всего доказанного диапазона не находит больше ни одного значения, именно эти два числа и являются всеми нетривиальными решениями в системе счисления по основанию 10.
Искомая сумма равна
$$145+40585=40{,}730.$$
Реализации на C++, Python и Java сначала итеративно строят таблицу из десяти факториальных значений. Затем они последовательно рассматривают возможные длины числа, одновременно отслеживая наименьшее число этой длины и наибольшую сумму факториалов цифр, которую такая длина может дать. Как только нижняя граница становится больше верхней, текущая длина объявляется невозможной, а предыдущая задает окончательный предел поиска.
Чтобы проверить конкретное число, программа многократно берет последнюю десятичную цифру, прибавляет к накопленной сумме уже известный факториал этой цифры и удаляет цифру из оставшегося префикса. После каждого шага накопленная сумма совпадает с суммой факториалов уже снятых цифр. Когда цифры заканчиваются, накопленная сумма в точности равна \(F(n)\), и сравнение с исходным числом завершает проверку.
Перебор начинается с \(10\), так что тривиальные однозначные случаи автоматически не рассматриваются. Каждый кандидат, удовлетворяющий \(F(n)=n\), добавляется к окончательному ответу. До полного прохода реализации также проверяют два известных нетривиальных примера \(145\) и \(40585\); эти контрольные точки подтверждают, что вычисление суммы факториалов цифр работает правильно.
Обозначим
$$U=7\cdot 9!=2{,}540{,}160.$$
Для каждого кандидата требуется один проход по его десятичным цифрам, причем у любого проверяемого числа не более семи цифр. Поэтому время работы равно
$$O(U\cdot 7)=O(U),$$
а на практике это всего лишь несколько миллионов очень простых операций над цифрами.
Дополнительная память постоянна: хранятся только десять факториальных значений и несколько счетчиков. Это \(O(10)\), то есть эквивалентно \(O(1)\).
لنرمز بـ \(F(n)\) إلى مجموع مضاريب الأرقام العشرية للعدد \(n\). تطلب المسألة 34 إيجاد جميع الأعداد الصحيحة الموجبة التي تحقق \(F(n)=n\)، ثم جمع الحلول غير التافهة فقط. ويُستبعد المثالان \(1=1!\) و\(2=2!\) لأن المطلوب هو أعداد تنتج من مجموع فعلي لمضاريب الأرقام، لا مجرد هوية من حد واحد.
إذن نحن نبحث عن النقاط الثابتة غير التافهة لتحويل «مجموع مضروب الأرقام» في الأساس العشري. وتتعامل تطبيقات C++ وPython وJava مع ذلك بطريقة كاملة: تثبت أولًا أن مجال البحث منتهٍ، ثم تحسب مسبقًا القيم العشر الممكنة \(0!\) إلى \(9!\)، ثم تفحص كل مرشح داخل المجال المثبت.
تعتمد الفكرة كلها على ثلاث ملاحظات بسيطة لكنها حاسمة: كل رقم عشري يساهم بحد أقصى مقداره \(9!\)، وعدد الخانات يفرض حدًا أدنى على \(n\)، ويمكن إعادة استخدام مضاريب الأرقام عبر جدول صغير جدًا.
إذا كانت الأرقام العشرية للعدد \(n\) هي \(d_1,d_2,\dots,d_k\)، فنعرّف
$$F(n)=d_1!+d_2!+\cdots+d_k!.$$
المطلوب هو الأعداد التي تحقق \(F(n)=n\). هذه معادلة نقاط ثابتة، لكنها شديدة المباشرة: كل رقم يضيف مساهمته عبر مضروبه بصورة مستقلة. وتبرز هنا أهمية الرقم صفر، لأن \(0!=1\) وليس \(0\). وهذه النقطة تظهر بوضوح في المثال \(40585\).
لهذا السبب تبني التطبيقات مرة واحدة جدول القيم \(0!,1!,\dots,9!\) باستخدام العلاقة التراجعية
$$f_0=1,\qquad f_d=d\,f_{d-1}\quad(1\le d\le 9).$$
بعد ذلك يصبح حساب \(F(n)\) مجرد تفكيك للعدد إلى أرقامه مع الرجوع إلى هذا الجدول.
افترض أن \(n\) مكوَّن من \(k\) خانات عشرية بالضبط. بما أن كل خانة تساهم بما لا يزيد على \(9!=362{,}880\)، فإن
$$F(n)\le k\cdot 9!.$$
ومن جهة أخرى، كل عدد مكوَّن من \(k\) خانات يحقق
$$n\ge 10^{k-1}.$$
إذن لا يمكن أن يوجد حل من \(k\) خانات إلا إذا تحقق
$$10^{k-1}\le k\cdot 9!.$$
الطرف الأيسر ينمو نموًا أسيًا مع \(k\)، بينما الطرف الأيمن ينمو خطيًا فقط. لذلك، بعد عدد معين من الخانات تصبح هذه المتباينة مستحيلة نهائيًا، وهذا يثبت أن عدد الحلول العشرية منتهٍ.
لا يضع الكود الحد الأعلى كعدد محفوظ مسبقًا، بل يشتقه أثناء التنفيذ من مقارنة منهجية بين أصغر عدد ذي طول معين وأكبر مجموع ممكن لمضاريب الأرقام عند الطول نفسه.
لسبع خانات ما زلنا نملك
$$7\cdot 9!=2{,}540{,}160,$$
ولذلك لا بد من فحص المجال الموافق حتى هذا الحد. أما عند ثماني خانات فنحصل على
$$8\cdot 9!=2{,}903{,}040<10^7,$$
وهذا يعني أن أي عدد من ثماني خانات لا يمكن أبدًا أن يساوي مجموع مضاريب أرقامه. ومن ثم فإن كل حل يجب أن يقع داخل المجال
$$10\le n\le 7\cdot 9!=2{,}540{,}160.$$
وبمجرد إثبات هذا الحد، يصبح المرور على المجال كله بحثًا شاملًا مبررًا رياضيًا، لا تخمينًا تجريبيًا.
يمكن التحقق مباشرة من العددين غير التافهين في الأساس العشري:
$$145=1!+4!+5!=1+24+120,$$
$$40585=4!+0!+5!+8!+5!=24+1+120+40{,}320+120.$$
ويوضح المثال الثاني مرة أخرى لماذا يجب التعامل مع \(0!=1\) بدقة تامة. وبما أن المسح الكامل للمجال المثبت لا يجد أي قيمة إضافية، فإن هذين العددين هما كل الحلول غير التافهة في الأساس 10.
وعليه يكون المجموع المطلوب هو
$$145+40585=40{,}730.$$
تبدأ تطبيقات C++ وPython وJava ببناء جدول المضاريب العشرة بطريقة تكرارية. بعد ذلك تمر على أطوال الأعداد الممكنة واحدًا بعد الآخر، مع تتبع أصغر عدد بذلك الطول وأكبر مجموع ممكن لمضاريب الأرقام عند الطول نفسه. وعندما يصبح الحد الأدنى أكبر من الحد الأعلى، يتبين أن هذا الطول مستحيل، ويعطي الطول السابق حد البحث النهائي.
لفحص مرشح معيّن، تأخذ الشيفرة آخر رقم عشري مرارًا، وتضيف مضروبه المحسوب مسبقًا إلى مجموع جارٍ، ثم تحذف ذلك الرقم من البادئة المتبقية. بعد كل خطوة يكون المجموع الجاري مساويًا تمامًا لمجموع مضاريب الأرقام التي أزيلت بالفعل. وعندما لا تبقى أي خانات، يصبح هذا المجموع مساويًا تمامًا لـ \(F(n)\)، ثم يُقارن مع العدد الأصلي لحسم الاختبار.
يبدأ المسح من \(10\)، ولذلك تُستبعد الحالات التافهة ذات الخانة الواحدة تلقائيًا. وكل مرشح يحقق \(F(n)=n\) يضاف إلى الجواب النهائي. وقبل بدء المسح الكامل، تتحقق التطبيقات أيضًا من المثالين المعروفين \(145\) و\(40585\) حتى تضمن أن حساب مجموع مضروب الأرقام يعمل كما ينبغي.
لنكتب
$$U=7\cdot 9!=2{,}540{,}160.$$
كل مرشح يحتاج إلى مرور واحد على أرقامه العشرية، وكل عدد مفحوص يملك في أقصى الأحوال سبع خانات. لذلك يكون زمن التنفيذ
$$O(U\cdot 7)=O(U),$$
أي بضع ملايين فقط من العمليات الرقمية البسيطة في التطبيق العملي.
أما الذاكرة الإضافية فهي ثابتة: لا يُخزَّن سوى جدول المضاريب المكوَّن من عشر قيم وبعض العدادات. وهذا يعني \(O(10)\)، أي بصورة مكافئة \(O(1)\).