We seek all integers \(n \ge 2\) whose decimal expansion \(n=\sum_{i=0}^{k-1} a_i 10^i\) also satisfies
$$n = F_5(n),\qquad F_5(n)=\sum_{i=0}^{k-1} a_i^5.$$
So the task is to find the fixed points of the fifth-power digit map, excluding the trivial case \(1\). For \(p=5\), there are exactly six such numbers: \(4150\), \(4151\), \(54748\), \(92727\), \(93084\), and \(194979\). Their sum is \(443839\).
The mathematical core is not a closed-form formula. The real work is proving that only finitely many candidates can exist and then turning the check for each candidate into a tiny digit-by-digit computation.
The C++, Python, and Java implementations are written for a general exponent \(p \ge 2\) and then run with \(p=5\). The central object is the digit-power map
$$F_p(n)=\sum_{i=0}^{k-1} a_i^p,$$
where \(a_0,a_1,\dots,a_{k-1}\) are the decimal digits of \(n\). Problem 30 asks for the fixed points of \(F_5\).
If \(n\) has digits \(a_{k-1}\dots a_1 a_0\), then \(n\) is a solution exactly when
$$n=a_0^5+a_1^5+\cdots+a_{k-1}^5.$$
This is already problem-specific enough to guide the algorithm: nothing about the positions of the digits matters except the digits themselves, and each digit contributes independently through its fifth power.
Let \(n\) be a \(k\)-digit number. Then \(n \ge 10^{k-1}\). On the other hand, each digit is at most 9, so the largest possible fifth-power digit sum for a \(k\)-digit number is
$$F_5(n)\le k\cdot 9^5.$$
Therefore, if
$$10^{k-1} \gt k\cdot 9^5,$$
then no \(k\)-digit number can satisfy \(F_5(n)=n\). The left-hand side is the smallest possible \(k\)-digit number, while the right-hand side is the largest sum of fifth powers its digits could ever produce. Once the inequality turns true, every longer length is impossible as well.
Now compute the critical quantities:
$$9^5=59049.$$
For six digits, the largest possible sum is
$$6\cdot 59049=354294,$$
and six-digit numbers begin at \(100000\), so six-digit solutions are still possible. For seven digits, however,
$$7\cdot 59049=413343 \lt 10^6=1000000.$$
That proves there are no seven-digit solutions. Hence every valid number lies in the finite interval
$$2 \le n \le 6\cdot 9^5 = 354294.$$
The lower bound starts at 2 because the problem convention excludes 1.
Write any positive integer as \(n=10q+r\) with \(0\le r\le 9\). Then the digit-power map satisfies
$$F_p(n)=F_p(q)+r^p.$$
This identity is exactly what the implementations use. Repeatedly taking the last digit \(r\), adding \(r^p\), and replacing \(n\) by \(q=\lfloor n/10\rfloor\) strips the decimal expansion from right to left. After each iteration, the running total already equals the contribution of the digits removed so far, while the remaining quotient still holds all unprocessed digits. That loop invariant makes the correctness of the computation immediate.
Because there are only ten possible digits, the values \(0^5,1^5,\dots,9^5\) are precomputed once. For the fifth-power case, the table is
$$[0,1,32,243,1024,3125,7776,16807,24576,59049].$$
Take \(n=194979\). Its digits are \(1,9,4,9,7,9\), so
$$F_5(194979)=1^5+9^5+4^5+9^5+7^5+9^5.$$
Substituting the actual values gives
$$1+59049+1024+59049+16807+59049=194979.$$
So \(194979\) is indeed a fixed point of \(F_5\). The same direct computation confirms the other five solutions.
The implementation first builds a ten-entry lookup table containing \(d^p\) for \(d=0,1,\dots,9\). This is the only place where exponentiation is performed; the main scan uses only table lookups, addition, modulo 10, and integer division.
Instead of hard-coding the fact that the fifth-power case stops at six digits, the implementation searches for the first digit length \(k\) with
$$10^{k-1} \gt k\cdot 9^p.$$
Once that impossible length appears, the search ceiling is \((k-1)\cdot 9^p\). For \(p=5\), this produces the bound \(354294\) automatically.
Every integer from 2 up to the derived upper bound is tested. For each one, the implementation strips digits from right to left, accumulates the corresponding precomputed powers, and compares the resulting sum with the original integer. Whenever the two values match, that integer is added to the final total.
Before printing the default fifth-power answer, the implementations also verify the same machinery on the fourth-power variant. The known total there is \(19316\), so matching that value provides a compact built-in checkpoint.
If \(U\) is the derived upper bound, then the running time is \(O(U\log_{10} U)\), because each candidate is processed once and each inner-loop iteration removes one decimal digit. The extra space usage is \(O(1)\): the lookup table has only ten entries, and the remaining storage is a handful of integers.
For Problem 30 specifically, \(U=354294\) and every candidate has at most 6 digits, so the total work is on the order of \(354294\times 6 \approx 2.1\times 10^6\) digit steps. That is why a direct exhaustive scan is not merely acceptable here; it is the natural consequence of the bound.
Gesucht sind alle ganzen Zahlen \(n \ge 2\), deren Dezimaldarstellung \(n=\sum_{i=0}^{k-1} a_i 10^i\) zugleich
$$n = F_5(n),\qquad F_5(n)=\sum_{i=0}^{k-1} a_i^5$$
erfüllt. Man sucht also die Fixpunkte der Abbildung, die eine Zahl auf die Summe der fünften Potenzen ihrer Ziffern abbildet. Für \(p=5\) gibt es genau sechs solche Zahlen: \(4150\), \(4151\), \(54748\), \(92727\), \(93084\) und \(194979\). Ihre Summe ist \(443839\).
Der mathematische Kern ist keine geschlossene Formel, sondern eine saubere Schranke für alle möglichen Kandidaten. Danach bleibt nur noch eine kurze und vollständig begründete Überprüfung jeder Zahl im endlichen Suchbereich.
Die C++-, Python- und Java-Implementierungen sind für einen allgemeinen Exponenten \(p \ge 2\) formuliert und werden hier mit \(p=5\) ausgeführt. Das zentrale Objekt ist die Ziffernpotenz-Abbildung
$$F_p(n)=\sum_{i=0}^{k-1} a_i^p,$$
wobei \(a_0,a_1,\dots,a_{k-1}\) die Dezimalziffern von \(n\) sind. Problem 30 fragt nach den Fixpunkten von \(F_5\).
Hat \(n\) die Ziffern \(a_{k-1}\dots a_1 a_0\), dann ist \(n\) genau dann eine Lösung, wenn
$$n=a_0^5+a_1^5+\cdots+a_{k-1}^5.$$
Diese Gleichung ist bereits die ganze Struktur des Problems: Entscheidend sind nur die Ziffern selbst, und jede Ziffer trägt unabhängig über ihre fünfte Potenz bei.
Sei \(n\) eine \(k\)-stellige Zahl. Dann gilt \(n \ge 10^{k-1}\). Andererseits ist jede Ziffer höchstens 9, also
$$F_5(n)\le k\cdot 9^5.$$
Damit folgt: Wenn
$$10^{k-1} \gt k\cdot 9^5,$$
dann kann keine \(k\)-stellige Zahl die Gleichung \(F_5(n)=n\) erfüllen. Die linke Seite ist die kleinste mögliche \(k\)-stellige Zahl, die rechte Seite die größtmögliche Summe fünfter Potenzen ihrer Ziffern. Sobald diese Ungleichung für eine Stellenzahl wahr ist, sind auch alle längeren Zahlen ausgeschlossen.
Nun setzt man die relevanten Werte ein:
$$9^5=59049.$$
Für sechs Stellen ist die maximale Ziffernsumme
$$6\cdot 59049=354294,$$
und sechsstellige Zahlen beginnen bei \(100000\), also sind sechsstellige Lösungen noch möglich. Für sieben Stellen gilt dagegen
$$7\cdot 59049=413343 \lt 10^6=1000000.$$
Damit sind siebenstellige Lösungen unmöglich. Also liegt jede gültige Zahl im Bereich
$$2 \le n \le 6\cdot 9^5 = 354294.$$
Die Untergrenze beginnt bei 2, weil die 1 nach Aufgaben-Konvention nicht mitgezählt wird.
Schreibe eine positive ganze Zahl als \(n=10q+r\) mit \(0\le r\le 9\). Dann erfüllt die Ziffernpotenz-Abbildung
$$F_p(n)=F_p(q)+r^p.$$
Genau diese Identität verwenden die Implementierungen. In jedem Schleifendurchlauf wird die letzte Ziffer \(r\) abgetrennt, ihr \(p\)-te Potenz addiert und \(n\) durch den Quotienten \(q=\lfloor n/10\rfloor\) ersetzt. Nach jedem Schritt enthält die laufende Summe exakt den Beitrag der bereits entfernten Ziffern, während der Quotient alle noch nicht verarbeiteten Ziffern trägt. Diese Invariante erklärt unmittelbar, warum die Rechnung korrekt ist.
Da es nur zehn mögliche Ziffern gibt, werden die Werte \(0^5,1^5,\dots,9^5\) genau einmal vorab berechnet. Im fünften-Potenzen-Fall ist die Tabelle
$$[0,1,32,243,1024,3125,7776,16807,24576,59049].$$
Betrachte \(n=194979\). Seine Ziffern sind \(1,9,4,9,7,9\), also
$$F_5(194979)=1^5+9^5+4^5+9^5+7^5+9^5.$$
Mit den konkreten Werten ergibt sich
$$1+59049+1024+59049+16807+59049=194979.$$
Damit ist \(194979\) tatsächlich ein Fixpunkt von \(F_5\). Dieselbe direkte Kontrolle bestätigt auch die übrigen fünf Zahlen.
Die Implementierung legt zunächst eine Nachschlagetabelle mit den zehn Werten \(d^p\) für \(d=0,1,\dots,9\) an. Nur an dieser Stelle wird potenziert; die Hauptsuche arbeitet danach ausschließlich mit Tabellenzugriffen, Addition, Modulo 10 und Ganzzahldivision.
Statt die Schranke für \(p=5\) fest einzubauen, sucht die Implementierung die erste Stellenzahl \(k\), für die
$$10^{k-1} \gt k\cdot 9^p$$
gilt. Sobald diese unmögliche Länge gefunden ist, lautet die echte Suchobergrenze \((k-1)\cdot 9^p\). Für \(p=5\) ergibt sich so automatisch \(354294\).
Danach wird jede Zahl von 2 bis zur berechneten Obergrenze getestet. Die Implementierung zerlegt die Zahl ziffernweise von rechts nach links, summiert die vorberechneten Potenzen und vergleicht die Summe mit der ursprünglichen Zahl. Bei Übereinstimmung wird die Zahl zur Gesamtsumme addiert.
Bevor standardmäßig die fünfte Potenz ausgegeben wird, prüfen die Implementierungen dieselbe Logik auch für den Fall \(p=4\). Dort ist die bekannte Gesamtsumme \(19316\); das dient als kompakter eingebauter Test.
Bezeichnet \(U\) die abgeleitete Obergrenze, dann beträgt die Laufzeit \(O(U\log_{10} U)\), weil jede Kandidatenzahl genau einmal verarbeitet wird und jeder Schleifendurchlauf eine Dezimalziffer entfernt. Der zusätzliche Speicherbedarf ist \(O(1)\): Die Nachschlagetabelle hat nur zehn Einträge, dazu kommen einige wenige Ganzzahlen.
Für Problem 30 konkret ist \(U=354294\), und jede Kandidatenzahl besitzt höchstens 6 Ziffern. Der Gesamtaufwand liegt also in der Größenordnung von \(354294\times 6 \approx 2.1\times 10^6\) Ziffernschritten. Genau deshalb ist eine direkte vollständige Suche hier nicht nur praktikabel, sondern die natürliche Folge der Schrankenabschätzung.
Aranan sayılar, onluk açılımı \(n=\sum_{i=0}^{k-1} a_i 10^i\) olan ve aynı zamanda
$$n = F_5(n),\qquad F_5(n)=\sum_{i=0}^{k-1} a_i^5$$
eşitliğini sağlayan \(n \ge 2\) tam sayılarıdır. Yani problem, basamaklarının beşinci kuvvetleri toplamı kendisine eşit olan sabit noktaları arar. \(p=5\) için tam olarak altı çözüm vardır: \(4150\), \(4151\), \(54748\), \(92727\), \(93084\) ve \(194979\). Bunların toplamı \(443839\)'dur.
Buradaki asıl matematiksel iş, kapalı bir formül bulmak değil, aramanın neden sonlu olduğunu kanıtlamak ve ardından her adayı çok küçük bir basamak hesabına indirgemektir.
C++, Python ve Java uygulamaları aslında \(p \ge 2\) için genel bir sürüm çözer; Problem 30'da yalnızca \(p=5\) kullanılır. Temel nesne şu basamak-kuvvet dönüşümüdür:
$$F_p(n)=\sum_{i=0}^{k-1} a_i^p,$$
burada \(a_0,a_1,\dots,a_{k-1}\), \(n\)'nin onluk basamaklarıdır. Sorulan şey, \(F_5\)'in sabit noktalarını bulmaktır.
Eğer \(n\) sayısının basamakları \(a_{k-1}\dots a_1 a_0\) ise, çözüm olma koşulu tam olarak
$$n=a_0^5+a_1^5+\cdots+a_{k-1}^5$$
eşitliğidir. Bu denklem problemin bütün yapısını verir: basamakların konumlarından çok, hangi basamakların bulunduğu önemlidir ve her basamak bağımsız olarak kendi beşinci kuvveti kadar katkı yapar.
\(n\), \(k\) basamaklı bir sayı olsun. O zaman \(n \ge 10^{k-1}\) olur. Öte yandan her basamak en fazla 9 olduğundan
$$F_5(n)\le k\cdot 9^5.$$
Dolayısıyla eğer
$$10^{k-1} \gt k\cdot 9^5,$$
ise hiçbir \(k\) basamaklı sayı \(F_5(n)=n\) koşulunu sağlayamaz. Sol taraf en küçük \(k\) basamaklı sayıyı, sağ taraf ise böyle bir sayının ulaşabileceği en büyük beşinci kuvvet toplamını temsil eder. Bu eşitsizlik bir kez doğru olduğunda, daha uzun bütün uzunluklar da otomatik olarak imkansız hale gelir.
Şimdi kritik sayıları yerine koyalım:
$$9^5=59049.$$
Altı basamak için en büyük olası toplam
$$6\cdot 59049=354294$$
olur ve altı basamaklı sayılar \(100000\)'den başladığı için altı basamaklı çözümler hâlâ mümkündür. Fakat yedi basamak için
$$7\cdot 59049=413343 \lt 10^6=1000000$$
elde edilir. Bu da yedi basamaklı çözüm olamayacağını gösterir. Demek ki her çözüm şu aralıkta bulunmak zorundadır:
$$2 \le n \le 6\cdot 9^5 = 354294.$$
Alt sınırın 2 olması, problem tanımı gereği 1'in dışarıda bırakılmasındandır.
Her pozitif tam sayı \(n=10q+r\) biçiminde yazılabilir; burada \(0\le r\le 9\). O zaman basamak-kuvvet dönüşümü
$$F_p(n)=F_p(q)+r^p$$
özelliğini sağlar. Uygulamalar tam olarak bu özdeşliği kullanır. Her adımda son basamak \(r\) alınır, \(r^p\) toplama eklenir ve sayı \(q=\lfloor n/10\rfloor\) ile değiştirilir. Böylece her yinelemeden sonra biriken toplam, şimdiye kadar koparılan basamakların katkısına tam olarak eşit olur; kalan bölüm ise henüz işlenmemiş basamakları taşır. Kodun doğruluğunu açıklayan temel invariant budur.
Yalnızca on farklı basamak bulunduğu için \(0^5,1^5,\dots,9^5\) değerleri bir kez önceden hesaplanır. Beşinci kuvvet durumunda tablo şöyledir:
$$[0,1,32,243,1024,3125,7776,16807,24576,59049].$$
\(n=194979\) sayısını ele alalım. Basamakları \(1,9,4,9,7,9\) olduğundan
$$F_5(194979)=1^5+9^5+4^5+9^5+7^5+9^5.$$
Gerçek değerleri yazarsak
$$1+59049+1024+59049+16807+59049=194979$$
elde edilir. Yani \(194979\), gerçekten \(F_5\)'in bir sabit noktasıdır. Aynı doğrudan kontrol öteki beş çözüm için de geçerlidir.
Uygulama önce \(d=0,1,\dots,9\) için \(d^p\) değerlerini içeren on elemanlı bir tablo kurar. Üs alma yalnızca burada yapılır; ana tarama artık sadece tablo erişimi, toplama, mod 10 ve tamsayı bölme kullanır.
Beşinci kuvvet için sınırı sabit yazmak yerine, uygulama
$$10^{k-1} \gt k\cdot 9^p$$
eşitsizliğini sağlayan ilk basamak sayısını arar. Bu imkansız uzunluk bulunduğunda, gerçek arama tavanı \((k-1)\cdot 9^p\) olur. \(p=5\) için bu yöntem otomatik olarak \(354294\) değerini üretir.
Daha sonra 2'den hesaplanan üst sınıra kadar her tam sayı test edilir. Uygulama sayıyı sağdan sola basamaklarına ayırır, ilgili önhesaplanmış kuvvetleri toplar ve çıkan sonucu özgün sayıyla karşılaştırır. Eşitlik varsa sayı son toplamın içine eklenir.
Varsayılan olarak beşinci kuvvet sonucunu yazmadan önce, aynı mekanizma \(p=4\) için de sınanır. O durumda bilinen toplam \(19316\)'dır; bu değer yerleşik bir kontrol noktası görevi görür.
\(U\) türetilen üst sınır olsun. O zaman çalışma süresi \(O(U\log_{10} U)\) olur; çünkü her aday tam bir kez işlenir ve iç döngünün her adımı bir onluk basamağı siler. Ek bellek kullanımı \(O(1)\)'dir: sadece on elemanlı tablo ve birkaç tamsayı gerekir.
Problem 30 özelinde \(U=354294\) ve her adayın en fazla 6 basamağı vardır. Toplam iş miktarı yaklaşık \(354294\times 6 \approx 2.1\times 10^6\) basamak adımı mertebesindedir. Bu yüzden doğrudan tam tarama, burada sadece kabul edilebilir değil, sınır argümanının doğal sonucudur.
Se buscan todos los enteros \(n \ge 2\) cuya expansión decimal \(n=\sum_{i=0}^{k-1} a_i 10^i\) también satisface
$$n = F_5(n),\qquad F_5(n)=\sum_{i=0}^{k-1} a_i^5.$$
En otras palabras, hay que encontrar los puntos fijos del mapa que reemplaza un número por la suma de las quintas potencias de sus dígitos, excluyendo el caso trivial \(1\). Para \(p=5\) aparecen exactamente seis números: \(4150\), \(4151\), \(54748\), \(92727\), \(93084\) y \(194979\). Su suma es \(443839\).
La parte verdaderamente matemática no es una fórmula cerrada, sino demostrar que el conjunto de candidatos es finito y convertir la verificación de cada candidato en una cuenta decimal muy corta.
Las implementaciones en C++, Python y Java están escritas para un exponente general \(p \ge 2\) y luego se ejecutan con \(p=5\). El objeto central es la aplicación
$$F_p(n)=\sum_{i=0}^{k-1} a_i^p,$$
donde \(a_0,a_1,\dots,a_{k-1}\) son los dígitos decimales de \(n\). El Problema 30 pide los puntos fijos de \(F_5\).
Si \(n\) tiene dígitos \(a_{k-1}\dots a_1 a_0\), entonces \(n\) es solución exactamente cuando
$$n=a_0^5+a_1^5+\cdots+a_{k-1}^5.$$
Eso ya determina la estructura del problema: solo importan los dígitos, y cada uno contribuye de manera independiente a través de su quinta potencia.
Sea \(n\) un número de \(k\) cifras. Entonces \(n \ge 10^{k-1}\). Además, como cada dígito es a lo sumo 9, se tiene
$$F_5(n)\le k\cdot 9^5.$$
Por lo tanto, si
$$10^{k-1} \gt k\cdot 9^5,$$
ningún número de \(k\) cifras puede satisfacer \(F_5(n)=n\). El lado izquierdo es el menor entero con \(k\) cifras y el derecho es la mayor suma de quintas potencias que esas cifras podrían producir. Una vez que la desigualdad se cumple, todas las longitudes mayores quedan descartadas automáticamente.
Ahora sustituimos los valores relevantes:
$$9^5=59049.$$
Para seis cifras, la suma máxima posible es
$$6\cdot 59049=354294,$$
y los números de seis cifras empiezan en \(100000\), así que aún puede haber soluciones de seis cifras. Para siete cifras, en cambio,
$$7\cdot 59049=413343 \lt 10^6=1000000.$$
Eso demuestra que no existen soluciones de siete cifras. En consecuencia, toda solución debe estar en el intervalo
$$2 \le n \le 6\cdot 9^5 = 354294.$$
El límite inferior comienza en 2 porque, por convenio del problema, el 1 no se cuenta.
Cualquier entero positivo puede escribirse como \(n=10q+r\), con \(0\le r\le 9\). Entonces el mapa de potencias de dígitos cumple
$$F_p(n)=F_p(q)+r^p.$$
Las implementaciones usan exactamente esta identidad. En cada iteración toman el último dígito \(r\), suman \(r^p\) y sustituyen \(n\) por \(q=\lfloor n/10\rfloor\). Después de cada paso, la suma acumulada coincide con la contribución de los dígitos ya retirados, mientras que el cociente restante contiene todos los dígitos aún no procesados. Ese invariante explica la corrección del bucle.
Como solo hay diez dígitos posibles, los valores \(0^5,1^5,\dots,9^5\) se precalculan una sola vez. Para \(p=5\), la tabla es
$$[0,1,32,243,1024,3125,7776,16807,24576,59049].$$
Tómese \(n=194979\). Sus dígitos son \(1,9,4,9,7,9\), de modo que
$$F_5(194979)=1^5+9^5+4^5+9^5+7^5+9^5.$$
Al sustituir los valores concretos se obtiene
$$1+59049+1024+59049+16807+59049=194979.$$
Así, \(194979\) es realmente un punto fijo de \(F_5\). La misma comprobación directa valida también los otros cinco números.
La implementación construye primero una tabla de diez entradas con los valores \(d^p\) para \(d=0,1,\dots,9\). La exponenciación ocurre solo aquí; el recorrido principal usa únicamente accesos a la tabla, sumas, módulo 10 y divisiones enteras.
En lugar de fijar a mano el caso de cinco potencias, la implementación busca la primera longitud \(k\) para la cual
$$10^{k-1} \gt k\cdot 9^p.$$
Una vez encontrada esa longitud imposible, el techo real de búsqueda es \((k-1)\cdot 9^p\). Para \(p=5\), este procedimiento produce automáticamente \(354294\).
Luego se examina cada entero desde 2 hasta la cota calculada. Para cada candidato, la implementación va quitando dígitos de derecha a izquierda, suma las potencias precalculadas y compara el resultado con el número original. Si coinciden, el candidato se añade al total final.
Antes de imprimir el resultado por defecto para la quinta potencia, las implementaciones también verifican el mismo mecanismo en el caso \(p=4\). Allí el total conocido es \(19316\), y ese valor sirve como punto de control interno.
Si \(U\) denota la cota superior deducida, el tiempo de ejecución es \(O(U\log_{10} U)\), porque cada candidato se procesa una vez y cada iteración del bucle interno elimina un dígito decimal. El espacio adicional es \(O(1)\): solo se necesita una tabla de diez entradas y unas pocas variables enteras.
En el Problema 30, \(U=354294\) y cada candidato tiene como máximo 6 dígitos, así que el trabajo total es del orden de \(354294\times 6 \approx 2.1\times 10^6\) pasos de dígitos. Por eso un barrido exhaustivo directo no solo es viable, sino la consecuencia natural de la cota matemática.
我们要找出所有满足 \(n \ge 2\) 的整数，使它们的十进制展开 \(n=\sum_{i=0}^{k-1} a_i 10^i\) 同时满足
$$n = F_5(n),\qquad F_5(n)=\sum_{i=0}^{k-1} a_i^5.$$
也就是说，题目要求寻找“各位数字的五次幂之和”这个映射的所有不动点，并且按题意排除 \(1\)。在 \(p=5\) 的情况下，恰好有六个解：\(4150\)、\(4151\)、\(54748\)、\(92727\)、\(93084\) 和 \(194979\)，它们的总和是 \(443839\)。
这道题的关键并不是某个神奇公式，而是先证明候选范围一定是有限的，然后把每个候选数的检验变成一个非常短的十进制拆位过程。
C++、Python 和 Java 的实现其实都支持一般的指数 \(p \ge 2\)，这里只是取默认值 \(p=5\)。核心对象是下面这个数字幂映射：
$$F_p(n)=\sum_{i=0}^{k-1} a_i^p,$$
其中 \(a_0,a_1,\dots,a_{k-1}\) 是 \(n\) 的十进制数字。第 30 题要求的正是 \(F_5\) 的不动点。
如果 \(n\) 的十进制数字是 \(a_{k-1}\dots a_1 a_0\)，那么 \(n\) 成为解当且仅当
$$n=a_0^5+a_1^5+\cdots+a_{k-1}^5.$$
这个方程已经把问题的结构说明得很清楚了：真正重要的是数字本身，而不是它们在式子中的位置；每一位都独立地通过自己的五次幂贡献到总和中。
设 \(n\) 是一个 \(k\) 位数，那么一定有 \(n \ge 10^{k-1}\)。另一方面，每一位数字都不超过 9，因此
$$F_5(n)\le k\cdot 9^5.$$
于是只要
$$10^{k-1} \gt k\cdot 9^5,$$
就不可能存在任何 \(k\) 位解满足 \(F_5(n)=n\)。因为左边是最小的 \(k\) 位整数，右边却是一个 \(k\) 位数在“数字五次幂和”意义下能够达到的最大值。一旦某个位数已经不可能，更长的位数当然也全部不可能。
先计算关键数值：
$$9^5=59049.$$
如果 \(n\) 有 6 位，那么数字五次幂和的最大值是
$$6\cdot 59049=354294,$$
而 6 位数从 \(100000\) 开始，所以 6 位解仍然有可能存在。可是到了 7 位时，
$$7\cdot 59049=413343 \lt 10^6=1000000.$$
这就说明 7 位解根本不可能出现。于是所有解都被压缩到有限区间
$$2 \le n \le 6\cdot 9^5 = 354294.$$
下界从 2 开始，是因为题目约定不把 \(1\) 算作答案。
任意正整数都可以写成 \(n=10q+r\)，其中 \(0\le r\le 9\)。这时数字幂映射满足
$$F_p(n)=F_p(q)+r^p.$$
实现代码正是依靠这条恒等式。每次取出末位数字 \(r\)，把 \(r^p\) 加入当前和，再把 \(n\) 改写成商 \(q=\lfloor n/10\rfloor\)。这样反复进行时，循环中的一个自然不变量是：当前累计和恰好等于已经剥离出的那些数字的 \(p\) 次幂之和，而剩下的商包含全部尚未处理的数字。这正是代码正确性的直接理由。
由于十进制数字只有 10 种可能，\(0^5,1^5,\dots,9^5\) 可以一次性预先算好。对五次幂问题，这张表就是
$$[0,1,32,243,1024,3125,7776,16807,24576,59049].$$
看 \(n=194979\)。它的数字是 \(1,9,4,9,7,9\)，所以
$$F_5(194979)=1^5+9^5+4^5+9^5+7^5+9^5.$$
把具体数值代进去，得到
$$1+59049+1024+59049+16807+59049=194979.$$
因此 \(194979\) 的确是 \(F_5\) 的一个不动点。其余五个解也都可以用同样的直接检验确认。
实现首先构造一个长度为 10 的查找表，存放 \(d^p\)（其中 \(d=0,1,\dots,9\)）。真正的幂运算只在这里出现一次；主循环之后只需要查表、加法、模 10 和整数除法。
实现并没有把五次幂情形下的上界硬编码进去，而是寻找第一个满足
$$10^{k-1} \gt k\cdot 9^p$$
的位数 \(k\)。一旦这个“不可能位数”出现，真正的搜索上界就是 \((k-1)\cdot 9^p\)。在 \(p=5\) 时，这个过程自动得到 \(354294\)。
随后，从 2 到计算出的上界，每个整数都被检查一次。程序不断从右向左剥离数字，累加相应的预计算幂值，最后把得到的和与原数比较。如果二者相等，这个数就被加入最终总和。
在输出默认的五次幂答案之前，实现还会先用 \(p=4\) 的已知结果验证同一套逻辑。这个已知总和是 \(19316\)，因此它充当了一个很紧凑的正确性检查点。
若把推导出的上界记为 \(U\)，运行时间就是 \(O(U\log_{10} U)\)，因为每个候选数只处理一次，而内层循环每一步都会删去一个十进制数字。额外空间是 \(O(1)\)：除了一张 10 项查找表，只需要少量整数变量。
对第 30 题而言，\(U=354294\)，并且每个候选数最多只有 6 位，因此总工作量大约是 \(354294\times 6 \approx 2.1\times 10^6\) 次数字处理。这说明直接穷举并不是“勉强可行”，而是由数学上界自然推出的最直接方案。
Нужно найти все целые числа \(n \ge 2\), чья десятичная запись \(n=\sum_{i=0}^{k-1} a_i 10^i\) одновременно удовлетворяет
$$n = F_5(n),\qquad F_5(n)=\sum_{i=0}^{k-1} a_i^5.$$
Иначе говоря, требуется найти все неподвижные точки отображения, которое заменяет число суммой пятых степеней его цифр, исключая тривиальный случай \(1\). При \(p=5\) существует ровно шесть таких чисел: \(4150\), \(4151\), \(54748\), \(92727\), \(93084\) и \(194979\). Их сумма равна \(443839\).
Главная математика здесь не в поиске закрытой формулы, а в том, чтобы строго ограничить множество кандидатов и затем свести проверку каждого кандидата к очень короткому разбору цифр.
Реализации на C++, Python и Java написаны для общего показателя \(p \ge 2\), а затем запускаются при \(p=5\). Центральный объект задачи — отображение
$$F_p(n)=\sum_{i=0}^{k-1} a_i^p,$$
где \(a_0,a_1,\dots,a_{k-1}\) — десятичные цифры числа \(n\). Задача 30 просит найти неподвижные точки \(F_5\).
Если цифры числа \(n\) равны \(a_{k-1}\dots a_1 a_0\), то \(n\) является решением тогда и только тогда, когда
$$n=a_0^5+a_1^5+\cdots+a_{k-1}^5.$$
Эта формула уже полностью задает структуру задачи: важны сами цифры, а не их смысл как величины целиком, и каждая цифра независимо вносит вклад через свою пятую степень.
Пусть \(n\) — \(k\)-значное число. Тогда обязательно \(n \ge 10^{k-1}\). С другой стороны, каждая цифра не превосходит 9, поэтому
$$F_5(n)\le k\cdot 9^5.$$
Следовательно, если
$$10^{k-1} \gt k\cdot 9^5,$$
то ни одно \(k\)-значное число не может удовлетворять равенству \(F_5(n)=n\). Левая часть — это наименьшее \(k\)-значное число, а правая — максимально возможная сумма пятых степеней его цифр. Как только неравенство стало истинным для некоторой длины, все большие длины исключаются автоматически.
Теперь подставим реальные значения:
$$9^5=59049.$$
Для шести цифр максимальная сумма равна
$$6\cdot 59049=354294,$$
а шестизначные числа начинаются с \(100000\), так что шестизначные решения еще возможны. Но для семи цифр уже
$$7\cdot 59049=413343 \lt 10^6=1000000.$$
Это доказывает, что семизначных решений не существует. Значит, каждое решение лежит в конечном интервале
$$2 \le n \le 6\cdot 9^5 = 354294.$$
Нижняя граница начинается с 2, потому что число \(1\) по условию не включается в ответ.
Любое положительное целое можно представить в виде \(n=10q+r\), где \(0\le r\le 9\). Тогда отображение суммы степеней цифр удовлетворяет формуле
$$F_p(n)=F_p(q)+r^p.$$
Именно эту формулу используют реализации. На каждом шаге берется последняя цифра \(r\), к текущей сумме добавляется \(r^p\), а само число заменяется на \(q=\lfloor n/10\rfloor\). После каждой итерации накопленная сумма уже равна вкладу снятых цифр, а оставшееся частное содержит все еще не обработанные цифры. Этот инвариант и объясняет корректность цикла.
Поскольку возможных цифр только десять, значения \(0^5,1^5,\dots,9^5\) вычисляются один раз заранее. Для случая \(p=5\) таблица имеет вид
$$[0,1,32,243,1024,3125,7776,16807,24576,59049].$$
Возьмем \(n=194979\). Его цифры — \(1,9,4,9,7,9\), поэтому
$$F_5(194979)=1^5+9^5+4^5+9^5+7^5+9^5.$$
Подставляя конкретные значения, получаем
$$1+59049+1024+59049+16807+59049=194979.$$
Следовательно, \(194979\) действительно является неподвижной точкой \(F_5\). Точно такой же прямой проверкой подтверждаются и остальные пять решений.
Сначала строится таблица из десяти значений \(d^p\) для \(d=0,1,\dots,9\). Возведение в степень выполняется только на этом этапе; основной перебор затем использует лишь обращения к таблице, сложение, взятие по модулю 10 и целочисленное деление.
Вместо жестко заданного предела для пятой степени реализация ищет первую длину \(k\), для которой выполняется
$$10^{k-1} \gt k\cdot 9^p.$$
Как только такая невозможная длина найдена, реальная граница поиска равна \((k-1)\cdot 9^p\). При \(p=5\) этот процесс автоматически дает \(354294\).
Далее проверяется каждое целое число от 2 до вычисленной верхней границы. Реализация последовательно снимает цифры справа налево, прибавляет соответствующие заранее вычисленные степени и сравнивает полученную сумму с исходным числом. При совпадении число добавляется к окончательному итогу.
Перед выводом ответа для пятой степени реализации дополнительно проверяют ту же схему на случае \(p=4\). Там известная сумма равна \(19316\), и это служит компактной контрольной точкой.
Если обозначить найденную верхнюю границу через \(U\), то время работы равно \(O(U\log_{10} U)\), потому что каждый кандидат обрабатывается один раз, а каждая итерация внутреннего цикла удаляет одну десятичную цифру. Дополнительная память составляет \(O(1)\): нужна только таблица из десяти значений и несколько целочисленных переменных.
Для задачи 30 имеем \(U=354294\), а у каждого кандидата не более 6 цифр, так что суммарная работа порядка \(354294\times 6 \approx 2.1\times 10^6\) шагов по цифрам. Именно поэтому прямой полный перебор здесь не просто допустим, а естественно вытекает из оценки сверху.
نبحث عن جميع الأعداد الصحيحة \(n \ge 2\) التي إذا كُتبت على الصورة العشرية \(n=\sum_{i=0}^{k-1} a_i 10^i\)، فإنها تحقق أيضًا
$$n = F_5(n),\qquad F_5(n)=\sum_{i=0}^{k-1} a_i^5.$$
أي إن المطلوب هو إيجاد نقاط الثبات للدالة التي تستبدل العدد بمجموع القوى الخامسة لأرقامه العشرية، مع استبعاد الحالة البديهية \(1\). في حالة \(p=5\) توجد ستة أعداد فقط تحقق ذلك: \(4150\)، \(4151\)، \(54748\)، \(92727\)، \(93084\)، و\(194979\). ومجموعها هو \(443839\).
الفكرة الرياضية الأساسية ليست صيغة مغلقة، بل إثبات أن عدد المرشحين محدود أصلًا، ثم تحويل فحص كل مرشح إلى عملية قصيرة جدًا تعتمد على تفكيك العدد إلى أرقامه.
التنفيذات في C++ وPython وJava مكتوبة لحالة عامة يكون فيها الأس \(p \ge 2\)، ثم تُشغَّل هنا مع \(p=5\). الكائن الرياضي المركزي هو الدالة
$$F_p(n)=\sum_{i=0}^{k-1} a_i^p,$$
حيث تمثل \(a_0,a_1,\dots,a_{k-1}\) الأرقام العشرية للعدد \(n\). ومسألة 30 تطلب نقاط الثبات للدالة \(F_5\).
إذا كانت أرقام العدد \(n\) هي \(a_{k-1}\dots a_1 a_0\)، فإن \(n\) يكون حلًا إذا وفقط إذا تحقق
$$n=a_0^5+a_1^5+\cdots+a_{k-1}^5.$$
هذه المعادلة تكشف بنية المسألة بالكامل: الذي يهم هو الأرقام نفسها، وكل رقم يساهم بشكل مستقل من خلال قوته الخامسة.
إذا كان \(n\) عددًا مكوَّنًا من \(k\) خانات، فلدينا بالضرورة \(n \ge 10^{k-1}\). ومن جهة أخرى، بما أن كل رقم لا يزيد على 9، فإن
$$F_5(n)\le k\cdot 9^5.$$
ومن ثم إذا تحقق
$$10^{k-1} \gt k\cdot 9^5,$$
فلا يمكن لأي عدد ذي \(k\) خانات أن يحقق \(F_5(n)=n\). فالطرف الأيسر هو أصغر عدد مكوَّن من \(k\) خانات، بينما الطرف الأيمن هو أكبر مجموع ممكن للقوى الخامسة لأرقامه. وبمجرد أن تصبح هذه المتباينة صحيحة لطول معين، تصبح جميع الأطوال الأكبر مستحيلة أيضًا.
لنحسب القيم الأساسية:
$$9^5=59049.$$
بالنسبة إلى ست خانات، يكون أكبر مجموع ممكن هو
$$6\cdot 59049=354294,$$
وبما أن الأعداد ذات الست خانات تبدأ من \(100000\)، فما زالت الحلول ذات الست خانات ممكنة. أما عند سبع خانات فنحصل على
$$7\cdot 59049=413343 \lt 10^6=1000000.$$
وهذا يثبت استحالة وجود أي حل مكوَّن من سبع خانات. لذلك لا بد أن يقع كل حل في المجال
$$2 \le n \le 6\cdot 9^5 = 354294.$$
ويبدأ الحد الأدنى من 2 لأن المسألة تستبعد العدد \(1\) اصطلاحًا.
يمكن كتابة أي عدد صحيح موجب على الصورة \(n=10q+r\) حيث \(0\le r\le 9\). وعندها تحقق دالة مجموع قوى الأرقام العلاقة
$$F_p(n)=F_p(q)+r^p.$$
وهذه بالضبط هي العلاقة التي تعتمد عليها التنفيذات. ففي كل خطوة يُؤخذ الرقم الأخير \(r\)، وتُضاف \(r^p\) إلى المجموع الجاري، ثم يُستبدل العدد بالقيمة \(q=\lfloor n/10\rfloor\). بعد كل دورة، يكون المجموع المتراكم مساويًا لمساهمة الأرقام التي أزيلت بالفعل، بينما يحمل خارج القسمة ما تبقى من الأرقام غير المعالجة. وهذا هو الثابت الأساسي الذي يبرر صحة الحلقة.
ولأن الأرقام الممكنة عشرة فقط، فإن القيم \(0^5,1^5,\dots,9^5\) تُحسب مرة واحدة مسبقًا. وفي حالة \(p=5\) تكون الجدول
$$[0,1,32,243,1024,3125,7776,16807,24576,59049].$$
لنأخذ \(n=194979\). أرقامه هي \(1,9,4,9,7,9\)، ولذلك
$$F_5(194979)=1^5+9^5+4^5+9^5+7^5+9^5.$$
وبالتعويض بالقيم الفعلية نحصل على
$$1+59049+1024+59049+16807+59049=194979.$$
إذن \(194979\) هو فعلًا نقطة ثبات للدالة \(F_5\). والطريقة نفسها تؤكد الحلول الخمسة الأخرى أيضًا.
يبني التنفيذ أولًا جدولًا من عشرة عناصر يحتوي على القيم \(d^p\) عندما يكون \(d=0,1,\dots,9\). ولا يحدث رفع للأس في أثناء المسح الرئيسي؛ فبعد ذلك يقتصر العمل على الرجوع إلى الجدول، والجمع، وأخذ باقي القسمة على 10، والقسمة الصحيحة.
بدلًا من تثبيت الحد الخاص بالقوة الخامسة يدويًا، يبحث التنفيذ عن أول طول \(k\) يحقق
$$10^{k-1} \gt k\cdot 9^p.$$
وحين يظهر هذا الطول المستحيل، يصبح الحد الأعلى الحقيقي للبحث هو \((k-1)\cdot 9^p\). وعند \(p=5\) يعطي هذا الإجراء القيمة \(354294\) تلقائيًا.
بعد ذلك يُفحص كل عدد صحيح من 2 حتى الحد الأعلى المحسوب. يقوم التنفيذ بنزع الأرقام من اليمين إلى اليسار، وجمع القوى المحسوبة مسبقًا، ثم مقارنة الناتج بالعدد الأصلي. وإذا تساوى الطرفان، يضاف ذلك العدد إلى المجموع النهائي.
قبل طباعة الناتج الافتراضي للقوة الخامسة، تتحقق التنفيذات من المنطق نفسه عند الحالة \(p=4\). وفي هذه الحالة يكون المجموع المعروف \(19316\)، ولذلك يعمل هذا الرقم كاختبار داخلي مدمج.
إذا رمزنا إلى الحد الأعلى المشتق بالرمز \(U\)، فإن زمن التنفيذ يساوي \(O(U\log_{10} U)\)، لأن كل مرشح يُعالج مرة واحدة، وكل دورة في الحلقة الداخلية تزيل رقمًا عشريًا واحدًا. أما الذاكرة الإضافية فهي \(O(1)\): جدول من عشرة عناصر وبعض المتغيرات الصحيحة فقط.
في المسألة 30 تحديدًا، لدينا \(U=354294\)، وكل مرشح يحوي في الأكثر 6 خانات، ولذلك يكون حجم العمل الإجمالي في حدود \(354294\times 6 \approx 2.1\times 10^6\) خطوة رقمية. ولهذا فإن المسح المباشر الكامل ليس مجرد حل مقبول، بل هو النتيجة الطبيعية للحد الرياضي.