A near power sum is a positive integer \(n\) with decimal digits \(a_1,\dots,a_\ell\) for which there exists an integer \(k\ge 1\) such that
$$\left|\sum_{i=1}^{\ell} a_i^k - n\right|=1.$$
The task is to find every distinct near power sum with \(n\le 10^{16}-1\) and add them together. The crucial observation is that the power sum depends only on how many times each digit occurs, not on the order of those digits.
Instead of scanning all integers below \(10^{16}\), the implementation scans digit multisets. For fixed length \(\ell\) and exponent \(k\), let \(c_d\) be the number of occurrences of digit \(d\). Then
$$c_d\in\mathbb{Z}_{\ge 0},\qquad \sum_{d=0}^{9} c_d=\ell.$$
From this count vector we define the digit-power sum
$$P_k(c_0,\dots,c_9)=\sum_{d=0}^{9} c_d d^k.$$
The whole search is built around this quantity.
If two \(\ell\)-digit numbers use the same multiset of digits, they produce the same value of \(P_k\). Therefore the ordered decimal string is not the right object to enumerate. The right object is the vector \((c_0,\dots,c_9)\), which records how many zeros, ones, twos, and so on occur.
This compresses many permutations into one state. For example, the numbers \(35\) and \(53\) correspond to the same vector with \(c_3=c_5=1\) and all other counts equal to \(0\).
If a number \(n\) with digit counts \((c_0,\dots,c_9)\) is a near power sum for exponent \(k\), then by definition
$$P_k(c_0,\dots,c_9)=n-1 \qquad \text{or} \qquad P_k(c_0,\dots,c_9)=n+1.$$
Equivalently, once the count vector and \(k\) are fixed, the only candidates are
$$n=P_k(c_0,\dots,c_9)-1,\qquad n=P_k(c_0,\dots,c_9)+1.$$
This is the key reduction. We do not need to generate every permutation of the chosen digits. We only need to test these two integers and verify whether one of them really has the same decimal digit frequencies and the same length \(\ell\).
For fixed \(\ell\), the admissible count vectors are exactly the weak compositions of \(\ell\) into \(10\) parts, so their number is
$$\binom{\ell+9}{9}.$$
A depth-first recursion can assign the count of digit \(0\), then digit \(1\), and so on, while keeping track of how many digit slots remain. When the remaining total reaches \(0\), we have one complete multiset. Because each vector is constructed once, there are no duplicate states coming from digit permutations.
The one degenerate leaf with \(c_0=\ell\) is discarded, since it corresponds only to the value \(0\), which is outside the positive search range.
The implementations only need exponents up to \(53\). The reason is that
$$2^{54}=18{,}014{,}398{,}509{,}481{,}984>10^{16}.$$
So if \(k\ge 54\), then any occurrence of a digit \(d\ge 2\) already contributes more than the maximum possible value of \(n\pm 1\). That makes the branch impossible. If only digits \(0\) and \(1\) remain, then \(P_k\le 16\), which cannot produce any new valid near power sum with matching decimal length. Hence \(1\le k\le 53\) is a complete search.
There is also a branch-level pruning rule. During the recursion, the partial sum
$$\sum_{d=0}^{m} c_d d^k$$
can only increase as more digits are assigned. Once it exceeds \(10^{16}+1\), neither \(P_k-1\) nor \(P_k+1\) can lie in the allowed range, so that entire subtree can be abandoned immediately.
The test at the leaf is exact. Given the completed multiset and exponent, compute \(P_k\), form the two candidates \(P_k-1\) and \(P_k+1\), and reject any value outside \(1\le n\le 10^{16}-1\). For each surviving candidate, recount its decimal digits. It is accepted if and only if its length is exactly \(\ell\) and its frequency table is identical to \((c_0,\dots,c_9)\).
This validation is what reconnects the multiset back to an actual number. A count vector may describe many permutations, but only the one or two numbers \(P_k\pm 1\) are relevant, and most of them fail the digit-frequency check.
Take \(\ell=2\), \(k=2\), and the multiset \(\{3,5\}\). Then \(c_3=c_5=1\) and all other counts are \(0\), so
$$P_2=3^2+5^2=9+25=34.$$
The only possible near power sums from this multiset are
$$34-1=33,\qquad 34+1=35.$$
The value \(33\) has digit counts \((0,0,0,2,0,\dots,0)\), so it fails. But \(35\) has exactly one \(3\) and one \(5\), so it is accepted.
Another simple example is \(\{5,7\}\) with \(k=2\):
$$5^2+7^2=25+49=74,$$
hence \(75\) is accepted. The implementations also contain the small checkpoint that the sum of all near power sums with at most two digits is
$$110.$$
The C++, Python, and Java implementations all follow the same mathematical search. For each exponent \(k=1,\dots,53\), they precompute the ten values \(0^k,1^k,\dots,9^k\), capping any value that already exceeds the useful range. Then, for each length \(\ell=1,\dots,16\), they run a depth-first enumeration of all digit-count vectors whose entries sum to \(\ell\).
At each completed vector, the implementation forms the digit-power sum \(P_k\), tests the two candidates \(P_k-1\) and \(P_k+1\), and recounts the decimal digits of each candidate. A value is kept only if it is positive, within the \(16\)-digit limit, has exactly \(\ell\) digits, and reproduces the same digit-frequency vector that generated \(P_k\).
Accepted values are inserted into a set, because the same near power sum could in principle be discovered for more than one exponent. After the search finishes, the distinct stored values are added. The Java implementation performs this search directly, while the Python implementation delegates the heavy numerical work to the C++ program and returns the parsed result, so the underlying algorithm is still the same across all three implementations.
Let \(D=16\) be the maximum number of digits and \(E=53\) the largest exponent that must be checked. For fixed \(\ell\), the number of digit multisets is \(\binom{\ell+9}{9}\), so the search examines
$$E\sum_{\ell=1}^{D}\binom{\ell+9}{9}$$
leaf states before pruning. Candidate validation scans at most \(\ell\) decimal digits, which yields the clean upper bound
$$O\left(E\sum_{\ell=1}^{D}\ell\binom{\ell+9}{9}\right).$$
For this problem, \(D\) and \(E\) are fixed constants, so the important practical point is not asymptotic growth but the reduction in state space: the algorithm explores digit multisets instead of almost \(10^{16}\) individual integers. The memory usage is \(O(10+D)\) for the current counts, recursion stack, and power table, plus \(O(S)\) for the set of \(S\) distinct near power sums that survive deduplication.
Eine Near-Power-Sum ist eine positive ganze Zahl \(n\) mit Dezimalziffern \(a_1,\dots,a_\ell\), für die es ein \(k\ge 1\) gibt mit
$$\left|\sum_{i=1}^{\ell} a_i^k - n\right|=1.$$
Gesucht ist die Summe aller verschiedenen solchen Zahlen mit \(n\le 10^{16}-1\). Entscheidend ist, dass die Potenzsumme nur davon abhängt, wie oft jede Ziffer vorkommt, nicht von der Reihenfolge der Ziffern.
Statt alle Zahlen unter \(10^{16}\) direkt zu durchsuchen, betrachtet die Lösung Ziffernmultimengen. Für feste Länge \(\ell\) und festen Exponenten \(k\) sei \(c_d\) die Anzahl der Vorkommen der Ziffer \(d\). Dann gilt
$$c_d\in\mathbb{Z}_{\ge 0},\qquad \sum_{d=0}^{9} c_d=\ell.$$
Daraus entsteht die Ziffern-Potenzsumme
$$P_k(c_0,\dots,c_9)=\sum_{d=0}^{9} c_d d^k.$$
Auf dieser Größe basiert die gesamte Suche.
Verwenden zwei \(\ell\)-stellige Zahlen dieselbe Ziffernmultimenge, so haben sie denselben Wert \(P_k\). Deshalb ist nicht die geordnete Dezimaldarstellung das richtige Suchobjekt, sondern der Vektor \((c_0,\dots,c_9)\), der die Häufigkeiten der Ziffern beschreibt.
So werden viele Permutationen zu einem einzigen Zustand zusammengefasst. Beispielsweise entsprechen \(35\) und \(53\) demselben Vektor mit \(c_3=c_5=1\) und allen anderen Einträgen gleich \(0\).
Ist eine Zahl \(n\) mit Ziffernanzahlen \((c_0,\dots,c_9)\) für den Exponenten \(k\) eine Near-Power-Sum, dann gilt per Definition
$$P_k(c_0,\dots,c_9)=n-1 \qquad \text{oder} \qquad P_k(c_0,\dots,c_9)=n+1.$$
Also kommen bei festem Zählvektor und festem \(k\) nur die beiden Kandidaten
$$n=P_k(c_0,\dots,c_9)-1,\qquad n=P_k(c_0,\dots,c_9)+1$$
in Frage. Genau das ist die zentrale Reduktion. Man muss nicht alle Permutationen der gewählten Ziffern erzeugen, sondern nur diese beiden Zahlen testen und prüfen, ob eine von ihnen tatsächlich dieselbe Ziffernhäufigkeit und dieselbe Länge \(\ell\) besitzt.
Für festes \(\ell\) sind die zulässigen Zählvektoren genau die schwachen Zerlegungen von \(\ell\) in \(10\) Teile. Ihre Anzahl ist
$$\binom{\ell+9}{9}.$$
Eine Tiefensuche weist zuerst der Ziffer \(0\) eine Anzahl zu, dann der Ziffer \(1\) und so weiter, wobei stets mitgeführt wird, wie viele Stellen noch zu verteilen sind. Sobald der Rest \(0\) ist, liegt eine vollständige Multimenge vor. Da jeder Vektor genau einmal konstruiert wird, entstehen keine Duplikate durch Ziffernpermutationen.
Das entartete Blatt mit \(c_0=\ell\) wird verworfen, denn es würde nur die Zahl \(0\) repräsentieren, und diese liegt außerhalb des positiven Suchbereichs.
Es genügt, Exponenten bis \(53\) zu betrachten. Denn
$$2^{54}=18{,}014{,}398{,}509{,}481{,}984>10^{16}.$$
Für \(k\ge 54\) trägt also schon ein einziges Auftreten einer Ziffer \(d\ge 2\) mehr bei als der größte mögliche Wert von \(n\pm 1\). Ein solcher Ast ist unmöglich. Bleiben nur die Ziffern \(0\) und \(1\), dann ist \(P_k\le 16\), und daraus entstehen keine neuen gültigen Near-Power-Sums mit passender Dezimallänge. Daher ist \(1\le k\le 53\) vollständig.
Zusätzlich gibt es eine Ast-Prüfung während der Rekursion. Die partielle Summe
$$\sum_{d=0}^{m} c_d d^k$$
wächst nur noch an, wenn weitere Ziffern hinzugefügt werden. Sobald sie \(10^{16}+1\) überschreitet, können weder \(P_k-1\) noch \(P_k+1\) im erlaubten Bereich liegen, also wird der gesamte Teilbaum sofort abgeschnitten.
Der Test am Blatt ist exakt. Aus der vollständigen Multimenge und dem Exponenten wird \(P_k\) berechnet; anschließend werden \(P_k-1\) und \(P_k+1\) gebildet, und alle Werte außerhalb von \(1\le n\le 10^{16}-1\) werden verworfen. Für jeden verbleibenden Kandidaten werden die Dezimalziffern erneut gezählt. Akzeptiert wird genau dann, wenn die Länge gleich \(\ell\) ist und die Häufigkeitstabelle exakt mit \((c_0,\dots,c_9)\) übereinstimmt.
Hier wird die Multimenge wieder mit einer konkreten Zahl verknüpft. Ein Zählvektor beschreibt zwar viele Permutationen, aber relevant sind nur die beiden Zahlen \(P_k\pm 1\), und die meisten bestehen die Ziffernprüfung nicht.
Nehmen wir \(\ell=2\), \(k=2\) und die Multimenge \(\{3,5\}\). Dann gilt \(c_3=c_5=1\), alle übrigen Zählwerte sind \(0\), also
$$P_2=3^2+5^2=9+25=34.$$
Die einzigen möglichen Near-Power-Sums aus dieser Multimenge sind
$$34-1=33,\qquad 34+1=35.$$
Die Zahl \(33\) hat die Ziffernanzahlen \((0,0,0,2,0,\dots,0)\) und fällt daher durch. Dagegen besitzt \(35\) genau eine \(3\) und eine \(5\), also wird sie akzeptiert.
Ein weiteres kleines Beispiel ist \(\{5,7\}\) mit \(k=2\):
$$5^2+7^2=25+49=74,$$
daher wird \(75\) akzeptiert. Die Implementierungen enthalten außerdem den kleinen Kontrollwert, dass die Summe aller Near-Power-Sums mit höchstens zwei Ziffern gleich
$$110$$
ist.
Die C++-, Python- und Java-Implementierungen folgen alle derselben mathematischen Suche. Für jeden Exponenten \(k=1,\dots,53\) werden zunächst die zehn Werte \(0^k,1^k,\dots,9^k\) vorab berechnet; alles, was den nützlichen Bereich bereits überschreitet, wird gekappt. Danach werden für jede Länge \(\ell=1,\dots,16\) per Tiefensuche alle Ziffern-Zählvektoren mit Gesamtsumme \(\ell\) erzeugt.
An jedem vollständigen Vektor bildet die Implementierung die Ziffern-Potenzsumme \(P_k\), testet die beiden Kandidaten \(P_k-1\) und \(P_k+1\) und zählt für jeden Kandidaten die Dezimalziffern nach. Ein Wert bleibt nur erhalten, wenn er positiv ist, innerhalb der \(16\)-stelligen Grenze liegt, genau \(\ell\) Stellen hat und denselben Ziffernfrequenzvektor reproduziert, der \(P_k\) erzeugt hat.
Akzeptierte Werte werden in einer Menge gespeichert, denn dieselbe Near-Power-Sum könnte prinzipiell für mehrere Exponenten auftauchen. Am Ende werden alle verschiedenen gespeicherten Werte addiert. Die Java-Implementierung führt diese Suche direkt aus; die Python-Implementierung delegiert die rechenintensive Arbeit an das C++-Programm und liefert das geparste Ergebnis zurück. Der zugrunde liegende Algorithmus ist also in allen drei Implementierungen derselbe.
Sei \(D=16\) die maximale Ziffernzahl und \(E=53\) der größte zu prüfende Exponent. Für festes \(\ell\) gibt es \(\binom{\ell+9}{9}\) Ziffernmultimengen, also untersucht die Suche vor dem Abschneiden insgesamt
$$E\sum_{\ell=1}^{D}\binom{\ell+9}{9}$$
Blattzustände. Die Validierung eines Kandidaten liest höchstens \(\ell\) Dezimalziffern, daher erhält man die saubere obere Schranke
$$O\left(E\sum_{\ell=1}^{D}\ell\binom{\ell+9}{9}\right).$$
Für dieses Problem sind \(D\) und \(E\) feste Konstanten. Praktisch entscheidend ist also die Verkleinerung des Zustandsraums: Statt fast \(10^{16}\) Einzelzahlen zu prüfen, durchsucht das Verfahren nur Ziffernmultimengen mit starker Abschneidung. Der Speicherbedarf ist \(O(10+D)\) für aktuelle Häufigkeiten, Rekursionsstack und Potenztabelle, plus \(O(S)\) für die Menge der \(S\) verschiedenen Near-Power-Sums nach der Deduplikation.
Bir near power sum, onluk basamaları \(a_1,\dots,a_\ell\) olan ve bir \(k\ge 1\) için
$$\left|\sum_{i=1}^{\ell} a_i^k - n\right|=1$$
eşitliğini sağlayan pozitif bir \(n\) sayısıdır. Amaç, \(n\le 10^{16}-1\) koşulunu sağlayan tüm farklı near power sum değerlerini bulup toplamaktır. Buradaki kritik gözlem, kuvvet toplamının basamakların sırasına değil yalnızca her rakamın kaç kez geçtiğine bağlı olmasıdır.
\(10^{16}\)'dan küçük tüm sayıları tek tek taramak yerine çözüm, rakam çokluklarını tarar. Sabit uzunluk \(\ell\) ve sabit üs \(k\) için \(c_d\), \(d\) rakamının kaç kez göründüğünü göstersin. O zaman
$$c_d\in\mathbb{Z}_{\ge 0},\qquad \sum_{d=0}^{9} c_d=\ell.$$
Bu vektörden şu rakam-kuvvet toplamını tanımlarız:
$$P_k(c_0,\dots,c_9)=\sum_{d=0}^{9} c_d d^k.$$
Bütün arama bu nicelik etrafında kuruludur.
Aynı rakam çokluğunu kullanan iki \(\ell\) basamaklı sayı, aynı \(P_k\) değerini üretir. Bu yüzden doğru arama nesnesi sıralı onluk yazım değil, \((c_0,\dots,c_9)\) frekans vektörüdür.
Böylece çok sayıda permütasyon tek bir duruma sıkışır. Örneğin \(35\) ve \(53\), \(c_3=c_5=1\) ve diğer tüm girişleri \(0\) olan aynı vektöre karşılık gelir.
Rakam adetleri \((c_0,\dots,c_9)\) olan bir \(n\) sayısı, üs \(k\) için near power sum ise tanım gereği
$$P_k(c_0,\dots,c_9)=n-1 \qquad \text{veya} \qquad P_k(c_0,\dots,c_9)=n+1$$
olmalıdır. Yani çokluk vektörü ile \(k\) sabitlenince geriye yalnızca şu iki aday kalır:
$$n=P_k(c_0,\dots,c_9)-1,\qquad n=P_k(c_0,\dots,c_9)+1.$$
Temel indirgeme budur. Seçilen rakamların tüm permütasyonlarını üretmek gerekmez; yalnızca bu iki tam sayıyı test edip gerçekten aynı rakam frekanslarına ve aynı uzunluk \(\ell\)'ye sahip olup olmadıklarını kontrol etmek yeterlidir.
Sabit \(\ell\) için uygun vektörler, \(\ell\)'nin \(10\) parçaya zayıf bölünmeleridir ve sayıları
$$\binom{\ell+9}{9}$$
kadardır. Bir derinlik öncelikli arama, önce \(0\) rakamına, sonra \(1\) rakamına ve böyle devam ederek kaç adet yerleştirileceğini seçer; aynı anda da geriye kaç basamak kaldığını tutar. Kalan toplam \(0\) olduğunda bir tam çokluk vektörü elde edilmiş olur. Her vektör yalnızca bir kez kurulduğu için permütasyonlardan gelen tekrar yoktur.
\(c_0=\ell\) olan tek yaprak ayrıca atılır; çünkü bu durum yalnızca \(0\) sayısını temsil eder ve aranan pozitif aralığın dışındadır.
Uygulamalar yalnızca \(53\)'e kadar üsleri inceler. Çünkü
$$2^{54}=18{,}014{,}398{,}509{,}481{,}984>10^{16}.$$
Dolayısıyla \(k\ge 54\) olduğunda, \(d\ge 2\) olan tek bir rakam bile \(n\pm 1\) için mümkün olan en büyük değerden daha büyük katkı yapar. Böyle bir dal imkansızdır. Geriye sadece \(0\) ve \(1\) rakamları kalırsa \(P_k\le 16\) olur; bu da eşleşen onluk uzunluğa sahip yeni bir near power sum üretemez. Bu yüzden \(1\le k\le 53\) aralığı eksiksizdir.
Bir de dal bazlı budama vardır. Özyineleme sırasında kısmi toplam
$$\sum_{d=0}^{m} c_d d^k$$
yalnızca artabilir. Bu değer \(10^{16}+1\)'i aşarsa, ne \(P_k-1\) ne de \(P_k+1\) geçerli aralıkta olabilir; dolayısıyla o alt ağaç hemen bırakılır.
Yaprak düğümdeki test tamdır. Tamamlanmış çokluk vektörü ve üs için \(P_k\) hesaplanır; sonra \(P_k-1\) ve \(P_k+1\) adayları oluşturulur ve \(1\le n\le 10^{16}-1\) dışında kalanlar elenir. Kalan her adayın onluk rakamları yeniden sayılır. Ancak uzunluğu tam olarak \(\ell\) ise ve frekans tablosu \((c_0,\dots,c_9)\) ile birebir aynıysa kabul edilir.
Bu doğrulama, çokluk vektörünü tekrar somut bir sayıya bağlayan adımdır. Tek bir vektör çok sayıda permütasyonu temsil eder, fakat gerçekte yalnızca \(P_k\pm 1\) önemlidir ve bunların büyük çoğunluğu frekans kontrolünden geçemez.
\(\ell=2\), \(k=2\) ve \(\{3,5\}\) çokluğunu alalım. Burada \(c_3=c_5=1\), diğer tüm adetler \(0\) olduğundan
$$P_2=3^2+5^2=9+25=34.$$
Bu çokluktan doğabilecek tek near power sum adayları
$$34-1=33,\qquad 34+1=35$$
olur. \(33\) sayısının rakam adetleri \((0,0,0,2,0,\dots,0)\) olduğundan başarısız olur. Buna karşılık \(35\) tam olarak bir adet \(3\) ve bir adet \(5\) içerir; dolayısıyla kabul edilir.
Bir başka küçük örnek, \(k=2\) için \(\{5,7\}\) çokluğudur:
$$5^2+7^2=25+49=74,$$
bu yüzden \(75\) kabul edilir. Uygulamalarda ayrıca en fazla iki basamaklı near power sum sayıların toplamının
$$110$$
olduğu küçük kontrol değeri bulunur.
C++, Python ve Java uygulamaları aynı matematiksel aramayı izler. Her \(k=1,\dots,53\) için önce \(0^k,1^k,\dots,9^k\) değerleri önceden hesaplanır; yararlı aralığı aşan değerler sınırın üstünde bir kaplama değeriyle tutulur. Ardından her \(\ell=1,\dots,16\) için toplamı \(\ell\) olan tüm rakam frekans vektörleri derinlik öncelikli aramayla üretilir.
Her tamamlanmış vektörde uygulama \(P_k\) toplamını kurar, \(P_k-1\) ve \(P_k+1\) adaylarını dener ve adayların onluk rakamlarını yeniden sayar. Bir değer ancak pozitifse, \(16\) basamak sınırının içindeyse, tam \(\ell\) basamaklıysa ve \(P_k\)'yi oluşturan aynı frekans vektörünü tekrar üretiyorsa tutulur.
Kabul edilen değerler bir kümeye eklenir; çünkü aynı near power sum teorik olarak birden fazla üs için bulunabilir. Arama bittikten sonra farklı değerler toplanır. Java uygulaması bu aramayı doğrudan yapar; Python uygulaması ise ağır sayısal hesabı C++ programına bırakarak ayrıştırılmış sonucu döndürür. Dolayısıyla alttaki algoritma üç dilde de aynıdır.
\(D=16\) azami basamak sayısı ve \(E=53\) kontrol edilmesi gereken en büyük üs olsun. Sabit \(\ell\) için rakam çokluğu sayısı \(\binom{\ell+9}{9}\) olduğundan, budama olmadan arama toplam
$$E\sum_{\ell=1}^{D}\binom{\ell+9}{9}$$
yaprak durumu inceler. Aday doğrulaması en fazla \(\ell\) rakam okur; bu da şu temiz üst sınırı verir:
$$O\left(E\sum_{\ell=1}^{D}\ell\binom{\ell+9}{9}\right).$$
Bu problemde \(D\) ve \(E\) sabittir. Pratikte belirleyici nokta, durum uzayının küçülmesidir: algoritma neredeyse \(10^{16}\) ayrı tam sayıyı taramak yerine rakam çokluklarını ve güçlü budamayı kullanır. Bellek kullanımı, güncel frekanslar, özyineleme yığını ve kuvvet tablosu için \(O(10+D)\), tekilleştirmeden sonra kalan \(S\) farklı near power sum için de \(O(S)\)'dir.
Un near power sum es un entero positivo \(n\) con dígitos decimales \(a_1,\dots,a_\ell\) para el cual existe un entero \(k\ge 1\) tal que
$$\left|\sum_{i=1}^{\ell} a_i^k - n\right|=1.$$
La tarea consiste en encontrar todos los valores distintos con \(n\le 10^{16}-1\) y sumarlos. La observación decisiva es que la suma de potencias depende solo de cuántas veces aparece cada dígito, no del orden de los dígitos.
En lugar de recorrer todos los enteros menores que \(10^{16}\), la solución recorre multisets de dígitos. Para longitud fija \(\ell\) y exponente fijo \(k\), sea \(c_d\) el número de veces que aparece el dígito \(d\). Entonces
$$c_d\in\mathbb{Z}_{\ge 0},\qquad \sum_{d=0}^{9} c_d=\ell.$$
Con este vector se define la suma de potencias de dígitos
$$P_k(c_0,\dots,c_9)=\sum_{d=0}^{9} c_d d^k.$$
Toda la búsqueda gira alrededor de esta cantidad.
Si dos números de \(\ell\) cifras usan el mismo multiset de dígitos, producen el mismo valor \(P_k\). Por eso el objeto correcto para enumerar no es la cadena decimal ordenada, sino el vector \((c_0,\dots,c_9)\) de frecuencias.
De este modo muchas permutaciones quedan comprimidas en un solo estado. Por ejemplo, \(35\) y \(53\) corresponden al mismo vector con \(c_3=c_5=1\) y todos los demás conteos iguales a \(0\).
Si un número \(n\) con conteos \((c_0,\dots,c_9)\) es un near power sum para cierto exponente \(k\), entonces por definición debe cumplirse
$$P_k(c_0,\dots,c_9)=n-1 \qquad \text{o} \qquad P_k(c_0,\dots,c_9)=n+1.$$
Equivalentemente, una vez fijados el multiset y \(k\), los únicos candidatos posibles son
$$n=P_k(c_0,\dots,c_9)-1,\qquad n=P_k(c_0,\dots,c_9)+1.$$
Esta es la reducción central. No hace falta generar todas las permutaciones de los dígitos elegidos. Basta con probar esos dos enteros y verificar si alguno tiene exactamente la misma frecuencia decimal y exactamente \(\ell\) cifras.
Para \(\ell\) fijo, los vectores válidos son las composiciones débiles de \(\ell\) en \(10\) partes, por lo que su número es
$$\binom{\ell+9}{9}.$$
Una búsqueda en profundidad asigna primero cuántos ceros hay, luego cuántos unos, y así sucesivamente, manteniendo cuántas posiciones quedan por repartir. Cuando el remanente llega a \(0\), ya se tiene un multiset completo. Como cada vector se construye una sola vez, no aparecen duplicados debidos a permutaciones.
La hoja degenerada con \(c_0=\ell\) se descarta, porque solo representaría al número \(0\), que queda fuera del rango positivo de la búsqueda.
Solo es necesario revisar exponentes hasta \(53\). En efecto,
$$2^{54}=18{,}014{,}398{,}509{,}481{,}984>10^{16}.$$
Por tanto, si \(k\ge 54\), una sola aparición de cualquier dígito \(d\ge 2\) ya supera el mayor valor posible de \(n\pm 1\). Esa rama es imposible. Si solo quedan los dígitos \(0\) y \(1\), entonces \(P_k\le 16\), lo cual no puede producir ningún near power sum nuevo con longitud decimal compatible. Así, \(1\le k\le 53\) cubre toda la búsqueda.
Además hay una poda durante la recursión. La suma parcial
$$\sum_{d=0}^{m} c_d d^k$$
solo puede crecer a medida que se asignan más dígitos. En cuanto supera \(10^{16}+1\), ni \(P_k-1\) ni \(P_k+1\) pueden quedar en el rango permitido, de modo que todo ese subárbol se abandona de inmediato.
La prueba en la hoja es exacta. Con el multiset completo y el exponente dados, se calcula \(P_k\), se forman los dos candidatos \(P_k-1\) y \(P_k+1\), y se rechaza cualquier valor fuera de \(1\le n\le 10^{16}-1\). Para cada candidato que sobrevive, se vuelven a contar sus dígitos decimales. Solo se acepta si su longitud es exactamente \(\ell\) y su tabla de frecuencias coincide exactamente con \((c_0,\dots,c_9)\).
Este paso vuelve a conectar el multiset con un número concreto. Un mismo vector de conteos describe muchas permutaciones, pero únicamente los dos valores \(P_k\pm 1\) son relevantes, y casi todos fallan en la comprobación de frecuencias.
Tomemos \(\ell=2\), \(k=2\), y el multiset \(\{3,5\}\). Entonces \(c_3=c_5=1\) y todos los demás conteos son \(0\), así que
$$P_2=3^2+5^2=9+25=34.$$
Los únicos near power sums posibles que salen de este multiset son
$$34-1=33,\qquad 34+1=35.$$
El número \(33\) tiene conteos \((0,0,0,2,0,\dots,0)\), luego falla. En cambio, \(35\) contiene exactamente un \(3\) y un \(5\), así que se acepta.
Otro ejemplo pequeño es \(\{5,7\}\) con \(k=2\):
$$5^2+7^2=25+49=74,$$
por lo tanto \(75\) se acepta. Las implementaciones también incluyen el pequeño punto de control de que la suma de todos los near power sums con a lo sumo dos cifras es
$$110.$$
Las implementaciones en C++, Python y Java siguen la misma búsqueda matemática. Para cada exponente \(k=1,\dots,53\), precalculan los diez valores \(0^k,1^k,\dots,9^k\), saturando cualquier valor que ya supere el rango útil. Luego, para cada longitud \(\ell=1,\dots,16\), ejecutan una enumeración en profundidad de todos los vectores de conteos cuyas entradas suman \(\ell\).
En cada vector completo, la implementación forma la suma \(P_k\), prueba los dos candidatos \(P_k-1\) y \(P_k+1\), y vuelve a contar los dígitos decimales de cada candidato. Un valor se conserva solo si es positivo, está dentro del límite de \(16\) cifras, tiene exactamente \(\ell\) dígitos y reproduce el mismo vector de frecuencias que generó \(P_k\).
Los valores aceptados se insertan en un conjunto, porque el mismo near power sum podría aparecer, en principio, para más de un exponente. Al terminar la búsqueda se suman los valores distintos almacenados. La implementación en Java realiza esta búsqueda de forma directa, mientras que la implementación en Python delega el trabajo numérico pesado al programa en C++ y devuelve el resultado ya interpretado. El algoritmo subyacente es, por tanto, el mismo en las tres implementaciones.
Sea \(D=16\) el número máximo de cifras y \(E=53\) el mayor exponente necesario. Para \(\ell\) fijo, el número de multisets de dígitos es \(\binom{\ell+9}{9}\), así que la búsqueda visita
$$E\sum_{\ell=1}^{D}\binom{\ell+9}{9}$$
estados hoja antes de la poda. La validación de cada candidato lee a lo sumo \(\ell\) cifras, lo que da la cota superior limpia
$$O\left(E\sum_{\ell=1}^{D}\ell\binom{\ell+9}{9}\right).$$
En este problema \(D\) y \(E\) son constantes fijas. Por eso, el beneficio práctico importante es la reducción del espacio de búsqueda: el algoritmo trabaja sobre multisets de dígitos en vez de recorrer casi \(10^{16}\) enteros individuales. La memoria es \(O(10+D)\) para los conteos actuales, la pila recursiva y la tabla de potencias, más \(O(S)\) para el conjunto de \(S\) near power sums distintos que sobreviven a la deduplicación.
所谓 near power sum，是指一个正整数 \(n\)，它的十进制数字为 \(a_1,\dots,a_\ell\)，并且存在某个整数 \(k\ge 1\) 使得
$$\left|\sum_{i=1}^{\ell} a_i^k - n\right|=1.$$
题目要求找出所有满足 \(n\le 10^{16}-1\) 的不同 near power sum，并把它们求和。这里最关键的观察是：数字的幂和只取决于每个数字出现了多少次，而不取决于这些数字在十进制表示中的排列顺序。
因此，程序并不枚举所有小于 \(10^{16}\) 的整数，而是枚举“数字多重集”。对固定的位数 \(\ell\) 和固定的指数 \(k\)，设 \(c_d\) 表示数字 \(d\) 出现的次数，则有
$$c_d\in\mathbb{Z}_{\ge 0},\qquad \sum_{d=0}^{9} c_d=\ell.$$
由这个计数向量定义数字幂和
$$P_k(c_0,\dots,c_9)=\sum_{d=0}^{9} c_d d^k.$$
整个搜索就是围绕这个量展开的。
如果两个 \(\ell\) 位数使用的是同一个数字多重集，那么它们对应的 \(P_k\) 完全相同。也就是说，真正值得枚举的对象不是具体的十进制排列，而是频数向量 \((c_0,\dots,c_9)\)。
这样可以把大量排列压缩成一个状态。例如，\(35\) 和 \(53\) 虽然是不同的整数，但它们都对应 \(c_3=c_5=1\)、其余计数全为 \(0\) 的同一个向量。
如果某个具有频数 \((c_0,\dots,c_9)\) 的整数 \(n\) 在指数 \(k\) 下是 near power sum，那么按照定义必然满足
$$P_k(c_0,\dots,c_9)=n-1 \qquad \text{或} \qquad P_k(c_0,\dots,c_9)=n+1.$$
换句话说，在计数向量和 \(k\) 都固定之后，唯一需要测试的候选数就是
$$n=P_k(c_0,\dots,c_9)-1,\qquad n=P_k(c_0,\dots,c_9)+1.$$
这一步是整个解法的核心压缩。我们根本不需要把该多重集的所有排列都生成出来，只需要检查这两个整数，并验证它们是否真的具有同样的十进制频数以及同样的位数 \(\ell\)。
对于固定 \(\ell\)，所有合法的计数向量正好是把 \(\ell\) 分成 \(10\) 个非负部分的弱组合，因此总数为
$$\binom{\ell+9}{9}.$$
实现上使用深度优先搜索：先决定数字 \(0\) 出现多少次，再决定数字 \(1\) 出现多少次，依次往后，同时维护还剩多少位需要分配。当剩余位数变成 \(0\) 时，就得到一个完整的数字多重集。由于每个频数向量只构造一次，因此不会出现排列导致的重复搜索。
其中 \(c_0=\ell\) 的退化情形会被直接丢弃，因为它只对应数值 \(0\)，而 \(0\) 不在题目的正整数搜索范围内。
程序只需要检查 \(1\le k\le 53\)。原因是
$$2^{54}=18{,}014{,}398{,}509{,}481{,}984>10^{16}.$$
因此一旦 \(k\ge 54\)，只要数字中出现任何一个 \(d\ge 2\)，其贡献 \(d^k\) 就已经超过 \(n\pm 1\) 可能达到的上界，所以这一分支不可能产生合法解。若只剩数字 \(0\) 和 \(1\)，则 \(P_k\le 16\)，也不可能形成新的、位数匹配的 near power sum。因此把搜索截断到 \(53\) 是完整且安全的。
此外，递归过程中还可以做单调剪枝。当前已经累加的部分和
$$\sum_{d=0}^{m} c_d d^k$$
只会随着后续数字分配而继续增大。一旦它超过 \(10^{16}+1\)，那么 \(P_k-1\) 与 \(P_k+1\) 都不可能落在允许范围内，于是整个子树都可以立刻停止搜索。
到达叶子结点时，检验是完全精确的。程序先根据完整的计数向量和指数求出 \(P_k\)，再构造两个候选值 \(P_k-1\) 与 \(P_k+1\)，并先剔除所有不在 \(1\le n\le 10^{16}-1\) 范围内的数。对于剩余候选值，再重新统计其十进制各数字出现的次数。只有当它的位数恰好等于 \(\ell\)，并且频数表与 \((c_0,\dots,c_9)\) 完全一致时，它才是真正的 near power sum。
这一验证步骤把“数字多重集”重新连接回“具体整数”。一个频数向量对应许多排列，但真正有意义的只有 \(P_k\pm 1\) 这两个数，而它们中的绝大多数都会在频数检查时被排除。
取 \(\ell=2\)、\(k=2\)，并考虑多重集 \(\{3,5\}\)。此时 \(c_3=c_5=1\)，其余频数为 \(0\)，因此
$$P_2=3^2+5^2=9+25=34.$$
由这个多重集产生的 near power sum 候选值只有
$$34-1=33,\qquad 34+1=35.$$
\(33\) 的数字频数是 \((0,0,0,2,0,\dots,0)\)，显然与 \(\{3,5\}\) 不一致，所以失败。\(35\) 则恰好包含一个 \(3\) 和一个 \(5\)，因此被接受。
另一个简单例子是 \(\{5,7\}\) 且 \(k=2\)：
$$5^2+7^2=25+49=74,$$
所以 \(75\) 会被接受。实现中还带有一个小型校验点：所有不超过两位数的 near power sum 之和为
$$110.$$
C++、Python 和 Java 三份实现都遵循同一套数学搜索。对每个指数 \(k=1,\dots,53\)，先预计算 \(0^k,1^k,\dots,9^k\) 这十个值；任何已经超出有效范围的幂值都会被截断到一个上界哨兵。随后，对每个长度 \(\ell=1,\dots,16\)，程序用深度优先搜索生成所有总和为 \(\ell\) 的数字频数向量。
在每个完整向量处，程序构造数字幂和 \(P_k\)，测试 \(P_k-1\) 与 \(P_k+1\) 两个候选值，并重新统计每个候选值的十进制数字。如果某个值是正数、没有超过 \(16\) 位限制、位数恰好为 \(\ell\)，并且重新得到的频数向量与生成 \(P_k\) 时使用的向量完全一致，那么它就被保留下来。
所有通过验证的数都放入一个集合中，因为同一个 near power sum 理论上可能在不同指数下重复出现。搜索结束后，把集合中的不同值求和即可。Java 版本直接执行这套搜索；Python 版本则把主要数值计算委托给 C++ 程序，再返回解析后的结果。因此三种实现的底层算法本质上完全相同。
记 \(D=16\) 为最大位数，\(E=53\) 为必须检查的最大指数。对固定的 \(\ell\)，数字多重集的数量为 \(\binom{\ell+9}{9}\)，因此在剪枝之前，搜索访问的叶子状态数量为
$$E\sum_{\ell=1}^{D}\binom{\ell+9}{9}.$$
每个候选值的验证最多扫描 \(\ell\) 位数字，所以可以写出清晰的上界
$$O\left(E\sum_{\ell=1}^{D}\ell\binom{\ell+9}{9}\right).$$
在本题中，\(D\) 和 \(E\) 都是固定常数，因此真正重要的是状态空间的缩减：算法枚举的是数字多重集，而不是接近 \(10^{16}\) 个单独整数。内存开销为 \(O(10+D)\)，用于当前频数、递归栈和幂表；另外还有 \(O(S)\) 用于保存去重后剩下的 \(S\) 个不同 near power sum。
Near power sum - это положительное целое число \(n\) с десятичными цифрами \(a_1,\dots,a_\ell\), для которого существует целое \(k\ge 1\), такое что
$$\left|\sum_{i=1}^{\ell} a_i^k - n\right|=1.$$
Нужно найти все различные такие числа при \(n\le 10^{16}-1\) и сложить их. Главная идея состоит в том, что сумма степеней зависит только от того, сколько раз встречается каждая цифра, а не от порядка цифр.
Вместо прямого перебора всех чисел меньше \(10^{16}\) решение перебирает мультимножества цифр. Для фиксированной длины \(\ell\) и фиксированной степени \(k\) обозначим через \(c_d\) число вхождений цифры \(d\). Тогда
$$c_d\in\mathbb{Z}_{\ge 0},\qquad \sum_{d=0}^{9} c_d=\ell.$$
По этому вектору определяется сумма степеней цифр
$$P_k(c_0,\dots,c_9)=\sum_{d=0}^{9} c_d d^k.$$
Вся конструкция поиска опирается именно на эту величину.
Если два \(\ell\)-значных числа используют одно и то же мультимножество цифр, то они дают одно и то же значение \(P_k\). Значит, перечислять нужно не все перестановки цифр, а вектор \((c_0,\dots,c_9)\), который хранит количество нулей, единиц, двоек и так далее.
Такое представление сжимает множество перестановок в одно состояние. Например, \(35\) и \(53\) соответствуют одному и тому же вектору с \(c_3=c_5=1\) и всеми остальными компонентами, равными \(0\).
Если число \(n\) с частотами \((c_0,\dots,c_9)\) является near power sum для степени \(k\), то по определению должно выполняться
$$P_k(c_0,\dots,c_9)=n-1 \qquad \text{или} \qquad P_k(c_0,\dots,c_9)=n+1.$$
Следовательно, после фиксации вектора частот и степени \(k\) возможны только два значения:
$$n=P_k(c_0,\dots,c_9)-1,\qquad n=P_k(c_0,\dots,c_9)+1.$$
Это и есть основное сокращение задачи. Не нужно строить все перестановки выбранных цифр. Достаточно проверить эти два числа и убедиться, что одно из них действительно имеет ту же длину \(\ell\) и те же десятичные частоты.
При фиксированном \(\ell\) допустимые векторы \((c_0,\dots,c_9)\) - это слабые композиции числа \(\ell\) на \(10\) частей, поэтому их число равно
$$\binom{\ell+9}{9}.$$
Поиск в глубину сначала назначает, сколько раз встречается цифра \(0\), затем цифра \(1\) и так далее, одновременно отслеживая, сколько позиций еще не распределено. Когда остаток становится равным \(0\), получается одно полное мультимножество. Так как каждый вектор строится один раз, дубликатов из-за перестановок не возникает.
Единственный вырожденный лист с \(c_0=\ell\) отбрасывается: он представлял бы только число \(0\), а оно не входит в положительный диапазон поиска.
Достаточно проверять степени только до \(53\), потому что
$$2^{54}=18{,}014{,}398{,}509{,}481{,}984>10^{16}.$$
Значит, при \(k\ge 54\) уже одно появление цифры \(d\ge 2\) дает вклад больше максимального возможного значения \(n\pm 1\). Такая ветвь невозможна. Если же остаются только цифры \(0\) и \(1\), то \(P_k\le 16\), а это не может породить новое корректное near power sum с подходящей десятичной длиной. Поэтому диапазона \(1\le k\le 53\) достаточно для полного поиска.
Кроме того, во время рекурсии действует монотонная отсечка. Частичная сумма
$$\sum_{d=0}^{m} c_d d^k$$
может только увеличиваться при добавлении новых цифр. Как только она становится больше \(10^{16}+1\), ни \(P_k-1\), ни \(P_k+1\) уже не могут лежать в допустимом диапазоне, и весь соответствующий поддерев можно сразу отбросить.
Проверка в листе точна. Для полного мультимножества и степени вычисляется \(P_k\), затем формируются кандидаты \(P_k-1\) и \(P_k+1\), а все значения вне диапазона \(1\le n\le 10^{16}-1\) сразу отбрасываются. Для каждого оставшегося кандидата заново подсчитываются десятичные цифры. Он принимается тогда и только тогда, когда его длина равна \(\ell\), а таблица частот в точности совпадает с \((c_0,\dots,c_9)\).
Именно эта проверка связывает мультимножество с конкретным числом. Один вектор частот кодирует много перестановок, но реально имеют смысл только два числа \(P_k\pm 1\), и почти все они не проходят тест частот.
Возьмем \(\ell=2\), \(k=2\) и мультимножество \(\{3,5\}\). Тогда \(c_3=c_5=1\), все остальные частоты равны \(0\), и потому
$$P_2=3^2+5^2=9+25=34.$$
Единственные возможные near power sum из этого мультимножества - это
$$34-1=33,\qquad 34+1=35.$$
Число \(33\) имеет частоты \((0,0,0,2,0,\dots,0)\), так что оно не подходит. А вот \(35\) содержит ровно одну цифру \(3\) и одну цифру \(5\), поэтому оно принимается.
Еще один маленький пример - мультимножество \(\{5,7\}\) при \(k=2\):
$$5^2+7^2=25+49=74,$$
следовательно, принимается число \(75\). В реализациях также есть небольшой контрольный результат: сумма всех near power sum, имеющих не более двух цифр, равна
$$110.$$
Реализации на C++, Python и Java следуют одному и тому же математическому поиску. Для каждой степени \(k=1,\dots,53\) сначала заранее вычисляются десять значений \(0^k,1^k,\dots,9^k\); все, что уже выходит за полезный диапазон, насыщается верхним сторожевым значением. Затем для каждой длины \(\ell=1,\dots,16\) запускается поиск в глубину по всем векторам частот, сумма компонентов которых равна \(\ell\).
В каждом полном векторе реализация строит сумму \(P_k\), проверяет двух кандидатов \(P_k-1\) и \(P_k+1\), а затем заново считает десятичные цифры каждого кандидата. Значение сохраняется только в том случае, если оно положительно, не превышает \(16\)-значный предел, имеет ровно \(\ell\) цифр и воспроизводит тот же вектор частот, из которого была получена сумма \(P_k\).
Подходящие числа помещаются в множество, поскольку одно и то же near power sum теоретически может встретиться при нескольких степенях. После завершения поиска все различные сохраненные значения суммируются. Реализация на Java выполняет этот поиск напрямую, а реализация на Python передает тяжелую численную работу программе на C++ и возвращает уже разобранный результат. Следовательно, лежащий в основе алгоритм одинаков во всех трех реализациях.
Пусть \(D=16\) - максимальное число цифр, а \(E=53\) - максимальная необходимая степень. Для фиксированного \(\ell\) число мультимножеств цифр равно \(\binom{\ell+9}{9}\), поэтому до отсечений поиск посещает
$$E\sum_{\ell=1}^{D}\binom{\ell+9}{9}$$
листовых состояний. Проверка кандидата читает не более \(\ell\) цифр, откуда получается чистая верхняя оценка
$$O\left(E\sum_{\ell=1}^{D}\ell\binom{\ell+9}{9}\right).$$
В данной задаче \(D\) и \(E\) фиксированы. Поэтому практически важно не асимптотическое поведение, а само сокращение пространства поиска: алгоритм перебирает мультимножества цифр вместо почти \(10^{16}\) отдельных чисел. Память составляет \(O(10+D)\) для текущих частот, стека рекурсии и таблицы степеней, плюс \(O(S)\) для множества из \(S\) различных near power sum после устранения дубликатов.
العدد من نوع near power sum هو عدد صحيح موجب \(n\) أرقامه العشرية هي \(a_1,\dots,a_\ell\)، ويوجد عدد صحيح \(k\ge 1\) بحيث
$$\left|\sum_{i=1}^{\ell} a_i^k - n\right|=1.$$
المطلوب هو إيجاد جميع القيم المختلفة التي تحقق ذلك مع الشرط \(n\le 10^{16}-1\)، ثم جمعها. الفكرة الحاسمة هنا أن مجموع القوى يعتمد فقط على عدد مرات ظهور كل رقم، ولا يعتمد على ترتيب الأرقام داخل الكتابة العشرية.
بدلا من فحص كل عدد أصغر من \(10^{16}\)، تبحث الخوارزمية في متعددات الأرقام. لطول ثابت \(\ell\) وأس ثابت \(k\)، ليكن \(c_d\) هو عدد مرات ظهور الرقم \(d\). عندئذ
$$c_d\in\mathbb{Z}_{\ge 0},\qquad \sum_{d=0}^{9} c_d=\ell.$$
ومن هذا المتجه نعرّف مجموع قوى الأرقام
$$P_k(c_0,\dots,c_9)=\sum_{d=0}^{9} c_d d^k.$$
كل البحث مبني على هذه الكمية.
إذا كان عددان من \(\ell\) خانات يستخدمان نفس متعدد الأرقام، فإنهما يعطيان نفس القيمة \(P_k\). لذلك لا نعدّ كل ترتيب عشري على حدة، بل نعدّ متجه التكرارات \((c_0,\dots,c_9)\) الذي يسجل عدد الأصفار والآحاد والاثنينات إلى آخره.
بهذه الطريقة تنهار كثير من التبديلات إلى حالة واحدة فقط. على سبيل المثال، العددان \(35\) و\(53\) يقابلان المتجه نفسه حيث \(c_3=c_5=1\) وجميع القيم الأخرى تساوي \(0\).
إذا كان عدد \(n\) ذو التكرارات \((c_0,\dots,c_9)\) من نوع near power sum للأس \(k\)، فلا بد أن يتحقق بالتعريف
إحدى العلاقتين الآتيتين يجب أن تكون صحيحة:
$$P_k(c_0,\dots,c_9)=n-1$$
$$P_k(c_0,\dots,c_9)=n+1.$$
وبصورة مكافئة، بعد تثبيت متجه التكرارات و\(k\)، لا يبقى إلا المرشحان
$$n=P_k(c_0,\dots,c_9)-1,\qquad n=P_k(c_0,\dots,c_9)+1.$$
هذا هو الاختزال الأساسي. لا حاجة إلى توليد جميع تبديلات الأرقام المختارة. يكفي اختبار هذين العددين والتحقق من أن أحدهما يملك فعلا نفس تكرارات الأرقام ونفس الطول \(\ell\).
عند تثبيت \(\ell\)، فإن جميع المتجهات الممكنة هي التركيبات الضعيفة للعدد \(\ell\) إلى \(10\) أجزاء، وعددها
$$\binom{\ell+9}{9}.$$
يتم ذلك ببحث عمق أولا يحدد عدد مرات ظهور الرقم \(0\)، ثم الرقم \(1\)، وهكذا، مع تتبع عدد الخانات المتبقية للتوزيع. عندما يصبح الباقي صفرا، نكون قد وصلنا إلى متعدد أرقام كامل. ولأن كل متجه يبنى مرة واحدة فقط، فلا توجد أي تكرارات ناتجة من تبديل الأرقام.
وتستبعد الورقة المنحلة التي تحقق \(c_0=\ell\)، لأنها تمثل العدد \(0\) فقط، وهذا العدد خارج مجال البحث الموجب.
يكفي فحص الأسس حتى \(53\) فقط، لأن
$$2^{54}=18{,}014{,}398{,}509{,}481{,}984>10^{16}.$$
لذلك إذا كان \(k\ge 54\)، فإن ظهور رقم واحد فقط من نوع \(d\ge 2\) يجعل المساهمة أكبر من أكبر قيمة ممكنة لـ \(n\pm 1\). عندها يصبح ذلك الفرع مستحيلا. وإذا بقيت فقط الأرقام \(0\) و\(1\)، فإن \(P_k\le 16\)، وهذا لا يولد أي near power sum جديد بطول عشري مطابق. لذلك فإن المجال \(1\le k\le 53\) يغطي جميع الحالات.
وهناك أيضا قطع على مستوى الفروع. فالمجموع الجزئي
$$\sum_{d=0}^{m} c_d d^k$$
لا يمكن إلا أن يزداد مع إضافة أرقام جديدة. فإذا تجاوز \(10^{16}+1\)، فلن يكون أي من \(P_k-1\) أو \(P_k+1\) ضمن المجال المسموح، ولذلك يمكن حذف ذلك الفرع بالكامل فوراً.
الاختبار عند الورقة دقيق تماما. بعد اكتمال متجه التكرارات ومعرفة الأس، يحسب البرنامج \(P_k\)، ثم يبني المرشحين \(P_k-1\) و\(P_k+1\)، ويستبعد مباشرة كل قيمة تقع خارج المجال \(1\le n\le 10^{16}-1\). ولكل مرشح باق، تعاد قراءة أرقامه العشرية وحساب تكرار كل رقم. ولا يقبل المرشح إلا إذا كان طوله يساوي تماما \(\ell\)، وإذا كان جدول التكرارات الناتج مطابقا تماما للمتجه \((c_0,\dots,c_9)\).
هذه الخطوة هي التي تعيد ربط متعدد الأرقام بعدد فعلي. فالمتجه الواحد يصف كثيرا من التبديلات، لكن المهم في النهاية هو العددان \(P_k\pm 1\) فقط، ومعظم هذه المرشحات تفشل عند فحص التكرارات.
لنأخذ \(\ell=2\) و\(k=2\) ومتعدد الأرقام \(\{3,5\}\). عندئذ يكون \(c_3=c_5=1\) وجميع التكرارات الأخرى \(0\)، ولذلك
$$P_2=3^2+5^2=9+25=34.$$
والمرشحان الوحيدان من هذا المتعدد هما
$$34-1=33,\qquad 34+1=35.$$
العدد \(33\) يملك تكرارات \((0,0,0,2,0,\dots,0)\)، ولذلك يفشل. أما \(35\) فيحتوي بالضبط على \(3\) واحد و\(5\) واحد، فيقبل.
وهناك مثال صغير آخر هو \(\{5,7\}\) عندما \(k=2\):
$$5^2+7^2=25+49=74,$$
ومن ثم يقبل العدد \(75\). كما تحتوي التطبيقات على نقطة تحقق صغيرة مفادها أن مجموع جميع near power sum التي لا تتجاوز خانتين يساوي
$$110.$$
تتبع تطبيقات C++ وPython وJava نفس البحث الرياضي. فلكل أس \(k=1,\dots,53\) تحسب مسبقا القيم العشر \(0^k,1^k,\dots,9^k\)، مع وضع قيمة سقفية لأي قوة تتجاوز المجال المفيد. ثم، ولكل طول \(\ell=1,\dots,16\)، ينفذ البرنامج بحثا بعمق أولا لتوليد جميع متجهات التكرارات التي مجموعها \(\ell\).
وعند كل متجه مكتمل، يبني التنفيذ مجموع القوى \(P_k\)، ويختبر المرشحين \(P_k-1\) و\(P_k+1\)، ثم يعيد عد الأرقام العشرية لكل مرشح. ولا يحتفظ بأي قيمة إلا إذا كانت موجبة، وتقع داخل حد \(16\) خانة، ولها بالضبط \(\ell\) خانات، وتعيد إنتاج متجه التكرارات نفسه الذي وُلد منه \(P_k\).
تخزن القيم المقبولة داخل مجموعة، لأن نفس near power sum قد يظهر نظريا لأكثر من أس. وبعد انتهاء البحث، تجمع القيم المختلفة المخزنة. تنفيذ Java يقوم بهذه العملية مباشرة، أما تنفيذ Python فيفوّض العمل العددي الثقيل إلى برنامج C++ ثم يعيد النتيجة بعد تحليلها. لذلك تبقى الخوارزمية الأساسية نفسها في جميع التطبيقات الثلاثة.
لتكن \(D=16\) هي أقصى عدد من الخانات، ولتكن \(E=53\) هي أكبر قيمة لازمة للأس. عند تثبيت \(\ell\)، يكون عدد متعددات الأرقام الممكنة هو \(\binom{\ell+9}{9}\)، ولذلك يزور البحث قبل القطع
$$E\sum_{\ell=1}^{D}\binom{\ell+9}{9}$$
حالات ورقية. والتحقق من كل مرشح يقرأ في أسوأ الأحوال \(\ell\) خانة عشرية، ومن هنا نحصل على الحد الأعلى الواضح
$$O\left(E\sum_{\ell=1}^{D}\ell\binom{\ell+9}{9}\right).$$
في هذه المسألة، \(D\) و\(E\) ثابتان. لذلك فالميزة العملية الأساسية ليست في صيغة أسيمبتوطية مجردة، بل في تقليص فضاء البحث نفسه: الخوارزمية تعد متعددات الأرقام بدلا من المرور على ما يقارب \(10^{16}\) عددا منفردا. أما الذاكرة فهي \(O(10+D)\) للمتجه الحالي ومكدس الاستدعاء وجدول القوى، بالإضافة إلى \(O(S)\) لمجموعة القيم المختلفة وعددها \(S\) بعد إزالة التكرار.