Let \(\operatorname{digitSum}(N)\) denote the sum of the decimal digits of \(N\). We want the increasing sequence of integers \(N\) with at least two digits such that
$$N=\operatorname{digitSum}(N)^k,\qquad k\ge 2,\qquad N\ge 10.$$
The task is to determine the 30th term of that sequence. Typical examples are \(81=9^2\), \(512=8^3\), \(2401=7^4\), and \(4913=17^3\). The important feature is that the base is not chosen freely: it is forced to be the digit sum of the final number.
A brute-force scan over all integers is the wrong viewpoint, because almost every number fails immediately. The implementations instead reverse the logic: they iterate over plausible digit sums \(s\), generate the power chain \(s^2,s^3,s^4,\dots\), and keep only the values whose digit sum comes back to \(s\).
The whole solution is a bounded search over digit sums. Once the correct search space is identified, the rest is just a complete enumeration of short power chains.
If a number \(N\) belongs to the sequence, then its defining base is
$$s=\operatorname{digitSum}(N).$$
So every valid term has the form \(N=s^k\) for some \(k\ge 2\). That means the real objects of interest are not arbitrary integers, but the chains of powers attached to possible digit sums. The search therefore starts at \(s=2\): \(s=1\) would only produce the one-digit value \(1\), which is excluded.
For a fixed \(s\), the candidates are exactly
$$s^2,\ s^3,\ s^4,\ \dots$$
No other numbers can possibly qualify for that same digit sum, because the defining equation already pins down the base.
Suppose we only care about valid terms up to a ceiling \(B\). Let \(d(x)\) be the number of decimal digits of \(x\). Then any \(N\le B\) satisfies
$$\operatorname{digitSum}(N)\le 9\,d(N)\le 9\,d(B).$$
Therefore every valid term below \(B\) must come from a base in the finite range
$$2\le s\le 9\,d(B).$$
This is the key invariant used by the implementations. One version computes that upper bound directly from the current ceiling. The fixed-ceiling versions use hard-coded safe ranges derived from the same idea, so the mathematics is identical even though the literal constant differs slightly.
For each candidate digit sum \(s\), the implementations do not recompute \(s^k\) from scratch. They use the recurrence
$$v_2=s^2,\qquad v_{k+1}=s\,v_k\quad (k\ge 2).$$
Because \(s\ge 2\), this chain is strictly increasing. So once a term exceeds the current ceiling \(B\), every later exponent is also too large, and that base can be abandoned permanently. This gives a complete and duplicate-free scan of all powers of \(s\) below the ceiling.
The completeness argument is short and decisive: if \(N\le B\) is valid, then its base is exactly \(s=\operatorname{digitSum}(N)\), and when that \(s\) is scanned, the recurrence eventually reaches \(s^k=N\) before the loop stops.
Take \(s=8\). The chain begins
$$8^2=64,\qquad 8^3=512,\qquad 8^4=4096,\qquad 8^5=32768.$$
The corresponding digit sums are
$$\operatorname{digitSum}(64)=10,\qquad \operatorname{digitSum}(512)=8,\qquad \operatorname{digitSum}(4096)=19,\qquad \operatorname{digitSum}(32768)=26.$$
So \(512\) is accepted, while the neighboring powers are rejected. The same pattern appears for other bases: \(17^2=289\) fails because its digit sum is \(19\), but \(17^3=4913\) succeeds because \(4+9+1+3=17\). This is why the search must test each power on the chain, not just the base itself.
The natural search order is by digit sum \(s\), but the sequence in the problem is ordered by the numerical value of the final numbers. Those two orders do not match. A hit from a larger base can easily lie between hits produced by smaller bases.
So the implementations collect every valid value under the chosen ceiling, keep the collection deduplicated, and then read it in sorted order. The adaptive C++ version starts from a modest ceiling and multiplies it by 10 until at least the requested index is present. The Python and Java versions choose a single large ceiling near \(10^{18}\), which is sufficient for the 30th term. In both cases, once all hits below the ceiling have been generated, the required element is obtained by ordinary sorting and indexing.
The C++, Python, and Java implementations all use the same core loop: iterate over candidate digit sums \(s\), start at \(s^2\), repeatedly multiply by \(s\), and after each multiplication compute the digit sum by stripping decimal digits with repeated division by 10. A value is recorded only if it has at least two digits and its digit sum is exactly \(s\).
The main difference is how the outer ceiling is managed. The C++ implementation is written for a general requested index, so it regenerates the full list under an initial ceiling and then raises that ceiling by powers of 10 until enough terms exist. The Python and Java implementations solve the specific 30th-term query directly under a single large ceiling. In the fixed-width languages, the repeated multiplication step is also guarded against overflow; the Python version relies on built-in arbitrary-precision integers even though the actual search still stays within the chosen bound.
Accepted values are stored in a deduplicated container and then read in increasing order. The C++ implementation also includes a small checkpoint that the second term is \(512\), which matches the worked example and confirms that the enumeration is behaving correctly before the requested index is returned.
Let \(B\) be the search ceiling and let \(D=d(B)\) be its decimal digit count. There are \(O(D)\) candidate bases, because \(s\le 9D\). For a fixed base \(s\), the number of generated powers is
$$\#\{k\ge 2:s^k\le B\}=\max\!\left(0,\left\lfloor \log_s B\right\rfloor-1\right),$$
which is at most \(O(D)\). So the total number of tested powers is \(O(D^2)\).
Each test computes a digit sum over at most \(D\) decimal digits, so the overall work is \(O(D^3)\) in decimal-digit operations, or simply “tiny” for the concrete limits used here. Memory usage is \(O(m)\), where \(m\) is the number of accepted terms stored before the final lookup. The adaptive-ceiling version may repeat the bounded search a few times, but each repeat only changes the ceiling by one decimal order of magnitude, so the practical overhead remains small.
Sei \(\operatorname{digitSum}(N)\) die Summe der Dezimalziffern von \(N\). Gesucht ist die aufsteigend sortierte Folge aller Zahlen \(N\) mit mindestens zwei Stellen, für die gilt
$$N=\operatorname{digitSum}(N)^k,\qquad k\ge 2,\qquad N\ge 10.$$
Bestimmt werden soll das 30. Folgenglied. Frühe Beispiele sind \(81=9^2\), \(512=8^3\), \(2401=7^4\) und \(4913=17^3\). Der entscheidende Punkt ist, dass die Basis nicht frei gewählt wird: Sie muss genau der Ziffernsumme der fertigen Zahl entsprechen.
Eine rohe Durchmusterung aller Zahlen wäre daher unnötig teuer. Die Implementierungen drehen den Blickwinkel um: Sie laufen über plausible Ziffernsummen \(s\), erzeugen die Potenzkette \(s^2,s^3,s^4,\dots\) und behalten nur diejenigen Werte, deren Ziffernsumme wieder bei \(s\) landet.
Die gesamte Lösung ist eine beschränkte Suche über mögliche Ziffernsummen. Sobald dieser Zustandsraum richtig gewählt ist, bleibt nur noch eine vollständige Enumeration kurzer Potenzketten.
Gehört eine Zahl \(N\) zur Folge, dann ist ihre Basis notwendig
$$s=\operatorname{digitSum}(N).$$
Jeder gültige Term hat also die Form \(N=s^k\) mit \(k\ge 2\). Damit sind die eigentlichen mathematischen Objekte nicht beliebige ganze Zahlen, sondern die Potenzketten zu möglichen Ziffernsummen. Die Suche beginnt folglich bei \(s=2\): Für \(s=1\) entstünde nur die einstellige Zahl \(1\), die ausgeschlossen ist.
Für festes \(s\) sind die Kandidaten genau
$$s^2,\ s^3,\ s^4,\ \dots$$
Andere Zahlen können für dieselbe Ziffernsumme nicht funktionieren, weil die definierende Gleichung die Basis bereits vollständig vorgibt.
Nehmen wir an, wir interessieren uns nur für gültige Terme bis zu einer Schranke \(B\). Sei \(d(x)\) die Anzahl der Dezimalstellen von \(x\). Dann gilt für jedes \(N\le B\)
$$\operatorname{digitSum}(N)\le 9\,d(N)\le 9\,d(B).$$
Also muss jeder gültige Term unterhalb von \(B\) von einer Basis aus dem endlichen Bereich
$$2\le s\le 9\,d(B)$$
stammen. Genau diese Abschätzung ist die zentrale Invariante der Programme. Eine Implementierung berechnet die obere Grenze direkt aus der aktuellen Schranke, die Versionen mit fester Obergrenze verwenden einen leicht großzügigeren konstanten Bereich, aber dieselbe mathematische Idee.
Für jede Kandidatenbasis \(s\) werden die Potenzen nicht neu ausgerechnet, sondern rekursiv fortgesetzt:
$$v_2=s^2,\qquad v_{k+1}=s\,v_k\quad (k\ge 2).$$
Da \(s\ge 2\) gilt, ist diese Kette streng wachsend. Sobald also ein Wert die aktuelle Schranke \(B\) überschreitet, sind auch alle späteren Exponenten zu groß, und diese Basis kann endgültig beendet werden. So erhält man eine vollständige und überschneidungsfreie Durchmusterung aller Potenzen von \(s\) unterhalb der Schranke.
Der Vollständigkeitsbeweis ist kurz: Ist \(N\le B\) gültig, dann ist seine Basis genau \(s=\operatorname{digitSum}(N)\), und wenn diese Basis durchlaufen wird, erscheint \(s^k=N\) zwangsläufig, bevor die Schleife stoppt.
Nehmen wir \(s=8\). Die Kette beginnt mit
$$8^2=64,\qquad 8^3=512,\qquad 8^4=4096,\qquad 8^5=32768.$$
Die zugehörigen Ziffernsummen sind
$$\operatorname{digitSum}(64)=10,\qquad \operatorname{digitSum}(512)=8,\qquad \operatorname{digitSum}(4096)=19,\qquad \operatorname{digitSum}(32768)=26.$$
Also wird \(512\) akzeptiert, während die benachbarten Potenzen verworfen werden. Dasselbe Muster sieht man bei anderen Basen: \(17^2=289\) scheitert, weil die Ziffernsumme \(19\) ist, aber \(17^3=4913\) funktioniert, weil \(4+9+1+3=17\). Deshalb muss wirklich jede Potenz einer Basis geprüft werden.
Die natürliche Suchreihenfolge läuft über die Ziffernsumme \(s\), doch die gesuchte Folge ist nach den Zahlenwerten sortiert. Diese beiden Ordnungen stimmen nicht überein. Ein Treffer mit größerer Basis kann leicht zwischen Treffern kleinerer Basen liegen.
Darum sammeln die Implementierungen alle gültigen Werte unter der gewählten Schranke, halten die Sammlung duplikatfrei und lesen sie danach in numerisch sortierter Reihenfolge aus. Die adaptive C++-Version startet mit einer kleinen Schranke und vervielfacht sie mit 10, bis mindestens der gewünschte Index vorhanden ist. Die Python- und Java-Versionen verwenden direkt eine große Schranke nahe \(10^{18}\), die für den 30. Term ausreicht. In beiden Fällen entsteht die Antwort ganz gewöhnlich durch Sortierung und Indexzugriff.
Die Implementierungen in C++, Python und Java benutzen dieselbe Kernschleife: Sie iterieren über Kandidaten für die Ziffernsumme \(s\), starten bei \(s^2\), multiplizieren wiederholt mit \(s\) und berechnen nach jedem Schritt die Ziffernsumme durch fortgesetztes Teilen durch 10. Ein Wert wird nur dann gespeichert, wenn er mindestens zweistellig ist und seine Ziffernsumme genau \(s\) ergibt.
Der Hauptunterschied liegt im Umgang mit der äußeren Schranke. Die C++-Implementierung ist auf einen allgemeinen angeforderten Index ausgelegt; sie erzeugt daher zunächst alle Treffer unter einer kleinen Grenze und erhöht diese Grenze dann um Zehnerpotenzen, bis genügend Terme vorhanden sind. Die Python- und Java-Versionen lösen direkt die konkrete Anfrage nach dem 30. Term unter einer einzigen großen Schranke. In den Sprachen mit fester Wortbreite wird außerdem die wiederholte Multiplikation gegen Überlauf abgesichert; Python benutzt eingebaute Ganzzahlen beliebiger Länge, obwohl die eigentliche Suche trotzdem innerhalb der gewählten Grenze bleibt.
Gefundene Werte werden in einer duplikatfreien Struktur gesammelt und anschließend aufsteigend gelesen. Die C++-Version enthält zusätzlich einen kleinen Kontrollpunkt, der bestätigt, dass der zweite Term gleich \(512\) ist. Damit wird die Enumeration vor der endgültigen Ausgabe noch einmal gegen ein bekanntes Beispiel abgesichert.
Sei \(B\) die Suchschranke und \(D=d(B)\) ihre Dezimalstellenzahl. Dann gibt es \(O(D)\) Kandidatenbasen, weil \(s\le 9D\). Für eine feste Basis \(s\) ist die Anzahl erzeugter Potenzen
$$\#\{k\ge 2:s^k\le B\}=\max\!\left(0,\left\lfloor \log_s B\right\rfloor-1\right),$$
also höchstens \(O(D)\). Damit werden insgesamt \(O(D^2)\) Potenzen getestet.
Jeder Test berechnet eine Ziffernsumme über höchstens \(D\) Dezimalstellen. Daraus folgt ein Gesamtaufwand von \(O(D^3)\) in Dezimalziffer-Operationen, praktisch also ein sehr kleiner Aufwand für die hier benutzten Grenzen. Der Speicherverbrauch ist \(O(m)\), wobei \(m\) die Zahl der gespeicherten Treffer bezeichnet. Die adaptive Variante wiederholt die beschränkte Suche zwar einige Male, aber jede Wiederholung erhöht die Grenze nur um eine Dezimalordnung, sodass der praktische Mehrfaktor klein bleibt.
\(\operatorname{digitSum}(N)\) ile \(N\) sayısının onluk tabandaki basamak toplamını gösterelim. İstenen dizi, en az iki basamaklı olup
$$N=\operatorname{digitSum}(N)^k,\qquad k\ge 2,\qquad N\ge 10$$
koşulunu sağlayan tüm sayıların artan sıradaki halidir. Görev, bu dizinin 30. terimini bulmaktır. İlk örnekler arasında \(81=9^2\), \(512=8^3\), \(2401=7^4\) ve \(4913=17^3\) bulunur. Buradaki kritik nokta, tabanın serbest olmamasıdır; taban, son sayının basamak toplamı olmak zorundadır.
Bu yüzden tüm sayıları tek tek gezmek doğru yaklaşım değildir. Uygulamalar mantığı ters çevirir: olası basamak toplamı \(s\) seçilir, \(s^2,s^3,s^4,\dots\) kuvvet zinciri üretilir ve yalnızca basamak toplamı tekrar \(s\) olan değerler tutulur.
Tüm çözüm, basamak toplamları üzerinde sınırlı bir arama yapmaya dayanır. Doğru arama uzayı seçildikten sonra geriye sadece kısa kuvvet zincirlerini eksiksiz dolaşmak kalır.
Eğer \(N\) dizideyse, tanım gereği onun tabanı
$$s=\operatorname{digitSum}(N)$$
olmak zorundadır. Dolayısıyla her geçerli terim \(N=s^k\) biçimindedir ve \(k\ge 2\) olur. Yani asıl matematiksel nesneler rastgele tamsayılar değil, olası basamak toplamlarına bağlı kuvvet zincirleridir. Arama \(s=2\) ile başlar; \(s=1\) yalnızca tek basamaklı \(1\) sayısını üretir ve bu sayı problem koşuluna uymaz.
Sabit bir \(s\) için adaylar tam olarak
$$s^2,\ s^3,\ s^4,\ \dots$$
şeklindedir. Tanım zaten tabanı belirlediği için aynı basamak toplamı için başka hiçbir sayı aday olamaz.
Sadece \(B\) üst sınırına kadar olan geçerli terimleri aradığımızı düşünelim. \(d(x)\), \(x\)'in onluk sistemdeki basamak sayısı olsun. O zaman her \(N\le B\) için
$$\operatorname{digitSum}(N)\le 9\,d(N)\le 9\,d(B)$$
eşitsizliği geçerlidir. Demek ki \(B\) altındaki her geçerli terim, şu sonlu aralıktaki bir tabandan gelmek zorundadır:
$$2\le s\le 9\,d(B).$$
Kodun dayandığı temel değişmez budur. Bir uygulama bu üst sınırı mevcut tavandan doğrudan hesaplar; sabit tavan kullanan sürümler ise aynı fikre karşılık gelen biraz daha gevşek sabit aralıklar seçer.
Her aday taban \(s\) için kuvvetler baştan hesaplanmaz; şu yineleme kullanılır:
$$v_2=s^2,\qquad v_{k+1}=s\,v_k\quad (k\ge 2).$$
\(s\ge 2\) olduğundan bu zincir sıkı biçimde artandır. Bu yüzden bir terim mevcut sınır \(B\)'yi geçtiği anda, daha büyük üslerin de sınır altında kalması imkansızdır ve o taban için arama bitirilir. Böylece \(s\)'nin sınır altındaki tüm kuvvetleri eksiksiz ve tekrarsız biçimde taranmış olur.
Doğruluk gerekçesi de nettir: Eğer \(N\le B\) geçerliyse, onun tabanı tam olarak \(s=\operatorname{digitSum}(N)\)'dir ve bu \(s\) işlendiğinde yineleme kaçınılmaz olarak \(s^k=N\) değerine ulaşır.
\(s=8\) alalım. Zincir şöyle başlar:
$$8^2=64,\qquad 8^3=512,\qquad 8^4=4096,\qquad 8^5=32768.$$
Bunların basamak toplamları ise
$$\operatorname{digitSum}(64)=10,\qquad \operatorname{digitSum}(512)=8,\qquad \operatorname{digitSum}(4096)=19,\qquad \operatorname{digitSum}(32768)=26$$
olur. Yani \(512\) kabul edilir, komşu kuvvetler ise elenir. Aynı durum başka tabanlarda da görülür: \(17^2=289\) başarısızdır çünkü basamak toplamı \(19\)'dur; fakat \(17^3=4913\) geçerlidir çünkü \(4+9+1+3=17\). Bu nedenle iyi bir tabanın tüm kuvvetleri otomatik olarak işe yarar gibi bir kural yoktur; her kuvvet ayrı kontrol edilmelidir.
Aramanın doğal sırası taban \(s\) üzerindendir, fakat problemdeki dizi son sayıların büyüklüğüne göre sıralanır. Bu iki sıra çakışmaz. Büyük bir tabandan gelen bir değer, daha küçük tabanlardan gelen iki değerin arasına rahatlıkla girebilir.
Bu yüzden uygulamalar seçilen sınır altındaki bütün geçerli değerleri toplar, bunları tekrarsız biçimde saklar ve sonra sayısal olarak sıralar. Uyarlamalı C++ sürümü önce küçük bir sınırla başlar, yeterli terim yoksa sınırı 10 ile çarpar. Python ve Java sürümleri ise doğrudan \(10^{18}\) civarında büyük bir sınır seçer. Her iki yaklaşımda da cevap, elde edilen sıralı listenin ilgili indeksinden okunur.
C++, Python ve Java uygulamalarının çekirdeği aynıdır: aday basamak toplamı \(s\) üzerinde dolaşılır, \(s^2\)'den başlanır, her adımda \(s\) ile yeniden çarpılır ve her ara değerin basamak toplamı 10'a bölme yöntemiyle hesaplanır. Yalnızca en az iki basamaklı olup basamak toplamı tekrar \(s\) veren değerler kaydedilir.
Asıl fark dış sınırın yönetimindedir. C++ uygulaması genel bir indeks isteğini desteklediği için önce küçük bir tavanda tüm adayları üretir, ardından yeterli terim bulunana kadar bu tavanı 10'un kuvvetleriyle büyütür. Python ve Java uygulamaları ise doğrudan büyük bir tavanda 30. terimi hedefler. Sabit kelime uzunluğu kullanan dillerde tekrar eden çarpma adımı taşmayı önleyecek şekilde korunur; Python ise yerleşik büyük tamsayıları kullanır, fakat gerçek arama yine seçilen üst sınırın içinde kalır.
Bulunan değerler tekrarsız bir yapıda tutulur ve sonunda artan sırayla okunur. C++ uygulaması ayrıca ikinci terimin \(512\) olduğunu kontrol eden küçük bir doğrulama adımı içerir. Böylece nihai indeks okunmadan önce sayımın bilinen örnekle uyumlu olduğu görülür.
\(B\) arama sınırı ve \(D=d(B)\) onun basamak sayısı olsun. \(s\le 9D\) olduğundan aday taban sayısı \(O(D)\)'dir. Sabit bir \(s\) için üretilen kuvvet sayısı
$$\#\{k\ge 2:s^k\le B\}=\max\!\left(0,\left\lfloor \log_s B\right\rfloor-1\right)$$
olur ve bu da en fazla \(O(D)\)'dir. Dolayısıyla toplam denenmiş kuvvet sayısı \(O(D^2)\) olur.
Her deneme en fazla \(D\) basamak üzerinde basamak toplamı hesabı yaptığı için toplam iş yükü, onluk basamak işlemleri cinsinden \(O(D^3)\)'tür. Buradaki sınırlar çok küçük olduğu için pratikte bu maliyet son derece düşüktür. Bellek kullanımı, son seçimden önce tutulan geçerli terim sayısı \(m\) için \(O(m)\)'dir. Uyarlamalı sınır kullanan sürüm aramayı birkaç kez tekrarlasa da, her tekrar yalnızca sınırı bir onluk mertebe artırdığı için ek maliyet küçüktür.
Denotemos por \(\operatorname{digitSum}(N)\) la suma de las cifras decimales de \(N\). Buscamos la sucesión creciente de enteros \(N\) con al menos dos cifras tales que
$$N=\operatorname{digitSum}(N)^k,\qquad k\ge 2,\qquad N\ge 10.$$
La meta es obtener el término número 30. Entre los primeros ejemplos están \(81=9^2\), \(512=8^3\), \(2401=7^4\) y \(4913=17^3\). La observación decisiva es que la base no es libre: queda forzada por la propia suma de dígitos del número final.
Por eso no conviene recorrer todos los enteros. Las implementaciones invierten el razonamiento: eligen una suma de dígitos candidata \(s\), generan la cadena \(s^2,s^3,s^4,\dots\) y solo conservan aquellos valores cuya suma de dígitos vuelve a ser \(s\).
Toda la solución es una búsqueda acotada sobre posibles sumas de dígitos. Una vez elegido correctamente ese espacio de estados, lo único que queda es enumerar por completo cadenas cortas de potencias.
Si un número \(N\) pertenece a la sucesión, entonces su base debe ser
$$s=\operatorname{digitSum}(N).$$
Así, todo término válido tiene la forma \(N=s^k\) con \(k\ge 2\). Los objetos matemáticos relevantes ya no son enteros arbitrarios, sino las cadenas de potencias asociadas a sumas de dígitos posibles. La búsqueda empieza en \(s=2\): con \(s=1\) solo aparecería el valor de una cifra \(1\), que queda fuera del problema.
Para un \(s\) fijo, los candidatos son exactamente
$$s^2,\ s^3,\ s^4,\ \dots$$
No hay otros números que puedan funcionar para esa misma suma de dígitos, porque la ecuación definitoria ya determina por completo la base.
Supongamos que solo queremos términos válidos hasta una cota \(B\). Sea \(d(x)\) el número de cifras decimales de \(x\). Entonces, para cualquier \(N\le B\),
$$\operatorname{digitSum}(N)\le 9\,d(N)\le 9\,d(B).$$
Por lo tanto, cualquier término válido por debajo de \(B\) debe venir de una base dentro del rango finito
$$2\le s\le 9\,d(B).$$
Esa es la invariante central usada por el algoritmo. Una implementación calcula esa cota a partir de la cota numérica actual; las versiones con límite fijo emplean intervalos constantes un poco más holgados, pero la justificación matemática es la misma.
Para cada base candidata \(s\), las potencias no se recalculan desde cero. Se usa la recurrencia
$$v_2=s^2,\qquad v_{k+1}=s\,v_k\quad (k\ge 2).$$
Como \(s\ge 2\), la cadena es estrictamente creciente. Por eso, una vez que un término supera la cota \(B\), todos los exponentes posteriores también quedan fuera del rango y esa base puede abandonarse definitivamente. Así se obtiene un barrido completo y sin repeticiones de todas las potencias de \(s\) por debajo de la cota.
La corrección se resume en una frase: si \(N\le B\) es válido, entonces su base exacta es \(s=\operatorname{digitSum}(N)\), y al recorrer esa base la recurrencia terminará produciendo \(s^k=N\) antes de detenerse.
Tomemos \(s=8\). La cadena empieza con
$$8^2=64,\qquad 8^3=512,\qquad 8^4=4096,\qquad 8^5=32768.$$
Sus sumas de cifras son
$$\operatorname{digitSum}(64)=10,\qquad \operatorname{digitSum}(512)=8,\qquad \operatorname{digitSum}(4096)=19,\qquad \operatorname{digitSum}(32768)=26.$$
Así, \(512\) se acepta y las potencias vecinas se rechazan. El mismo fenómeno aparece con otras bases: \(17^2=289\) falla porque su suma de cifras es \(19\), mientras que \(17^3=4913\) sí entra en la sucesión porque \(4+9+1+3=17\). No existe una regla más simple del tipo “si una base sirve una vez, ya sirve siempre”; por eso cada potencia debe comprobarse explícitamente.
El recorrido natural del algoritmo va por bases \(s\), pero la sucesión pedida está ordenada por el valor numérico final. Esas dos órdenes no coinciden. Un acierto procedente de una base mayor puede caer entre aciertos producidos por bases menores.
Por eso las implementaciones reúnen todos los valores válidos bajo la cota elegida, los mantienen sin duplicados y luego los leen en orden creciente. La versión adaptativa en C++ comienza con una cota modesta y la multiplica por 10 hasta que ya hay suficientes términos. Las versiones en Python y Java usan directamente una cota grande cercana a \(10^{18}\), suficiente para el término 30. En ambos casos la respuesta sale de ordenar e indexar la colección final.
Las implementaciones en C++, Python y Java comparten el mismo bucle esencial: iteran por posibles sumas de dígitos \(s\), empiezan en \(s^2\), multiplican repetidamente por \(s\) y, tras cada multiplicación, calculan la suma de cifras eliminando dígitos decimales mediante divisiones sucesivas por 10. Un valor solo se registra si tiene al menos dos cifras y su suma de cifras coincide exactamente con \(s\).
La diferencia principal está en la gestión de la cota externa. La implementación en C++ está escrita para un índice solicitado en general; por eso regenera la lista bajo una cota inicial y luego aumenta esa cota en potencias de 10 hasta tener suficientes términos. Las versiones en Python y Java resuelven directamente la consulta del término 30 con una única cota grande. En los lenguajes de ancho fijo, la multiplicación repetida también se protege contra desbordamientos; Python utiliza enteros de precisión arbitraria, aunque la búsqueda real siga limitada por la cota elegida.
Los valores aceptados se guardan en una estructura sin duplicados y luego se leen en orden creciente. La versión en C++ añade además una comprobación pequeña: verifica que el segundo término sea \(512\). Esa verificación coincide con el ejemplo conocido y sirve como control rápido antes de devolver el índice pedido.
Sea \(B\) la cota de búsqueda y \(D=d(B)\) su número de cifras decimales. Hay \(O(D)\) bases candidatas, porque \(s\le 9D\). Para una base fija \(s\), el número de potencias generadas es
$$\#\{k\ge 2:s^k\le B\}=\max\!\left(0,\left\lfloor \log_s B\right\rfloor-1\right),$$
que está acotado por \(O(D)\). En consecuencia, el número total de potencias comprobadas es \(O(D^2)\).
Cada comprobación calcula una suma de cifras sobre a lo sumo \(D\) dígitos, de modo que el coste total es \(O(D^3)\) en operaciones sobre dígitos decimales, algo muy pequeño para las cotas concretas que se usan aquí. La memoria es \(O(m)\), donde \(m\) es la cantidad de aciertos almacenados antes de extraer el elemento final. La versión con cota adaptativa repite la búsqueda varias veces, pero cada repetición solo aumenta la cota en un orden decimal, así que el sobrecoste práctico sigue siendo bajo.
记 \(\operatorname{digitSum}(N)\) 为整数 \(N\) 的十进制数位和。题目要求把所有满足下面条件、且至少有两位的正整数按从小到大排列：
$$N=\operatorname{digitSum}(N)^k,\qquad k\ge 2,\qquad N\ge 10.$$
我们要找的是这个序列的第 30 项。前面的典型例子有 \(81=9^2\)、\(512=8^3\)、\(2401=7^4\)、\(4913=17^3\)。关键点在于：这里的底数不是额外自由选择的，它必须恰好等于最终结果本身的数位和。
因此，直接从所有整数里暴力筛选并不是好思路。真正高效的做法是反过来想：先枚举可能的数位和 \(s\)，再生成对应的幂链 \(s^2,s^3,s^4,\dots\)，最后只保留那些数位和重新回到 \(s\) 的值。
整个解法本质上是“在有限的候选数位和范围内，完整枚举每一条幂链”。一旦这个搜索空间被正确识别出来，问题就不再神秘。
如果一个数 \(N\) 属于目标序列，那么它的底数必然是
$$s=\operatorname{digitSum}(N).$$
于是每个合法项都可以写成 \(N=s^k\)，其中 \(k\ge 2\)。这说明我们真正要处理的不是“所有整数”，而是由可能的数位和 \(s\) 所定义的幂链。搜索从 \(s=2\) 开始就够了，因为 \(s=1\) 只会产生单个一位数 \(1\)，而题目明确要求至少两位。
对固定的 \(s\) 来说，候选值恰好就是
$$s^2,\ s^3,\ s^4,\ \dots$$
不会再有别的数能和这同一个数位和 \(s\) 对应，因为定义式已经把底数完全锁定了。
假设我们现在只关心不超过某个上界 \(B\) 的合法项。设 \(d(x)\) 表示 \(x\) 的十进制位数。那么对于任何 \(N\le B\)，都有
$$\operatorname{digitSum}(N)\le 9\,d(N)\le 9\,d(B).$$
所以，所有不超过 \(B\) 的合法项，其底数一定落在下面这个有限范围内：
$$2\le s\le 9\,d(B).$$
这正是程序使用的核心不变量。C++ 实现会根据当前上界直接计算这个范围；Python 和 Java 的固定上界版本则采用基于同一思想的安全常数范围。写法略有不同，但数学依据完全一致。
对每个候选底数 \(s\)，程序并不会反复从头计算 \(s^k\)，而是使用递推关系
$$v_2=s^2,\qquad v_{k+1}=s\,v_k\quad (k\ge 2).$$
由于 \(s\ge 2\)，这条链严格递增。于是只要某一项已经超过当前上界 \(B\)，后面的指数就不可能重新回到范围内，这条链可以立刻结束。这样就能对给定 \(s\) 的所有幂做一次完整、无遗漏、无回头的扫描。
正确性也很直接：如果 \(N\le B\) 是合法项，那么它的底数一定就是 \(s=\operatorname{digitSum}(N)\)。当程序枚举到这个 \(s\) 时，递推链最终一定会走到 \(s^k=N\)，而且发生在终止条件之前。
以 \(s=8\) 为例，幂链前几项是
$$8^2=64,\qquad 8^3=512,\qquad 8^4=4096,\qquad 8^5=32768.$$
它们的数位和分别是
$$\operatorname{digitSum}(64)=10,\qquad \operatorname{digitSum}(512)=8,\qquad \operatorname{digitSum}(4096)=19,\qquad \operatorname{digitSum}(32768)=26.$$
因此只有 \(512\) 会被接受，旁边的幂都会被排除。再看另一个底数：\(17^2=289\) 的数位和是 \(19\)，所以无效；但 \(17^3=4913\) 的数位和正好是 \(17\)，所以有效。这个例子说明，不能靠“这个底数之前成功过一次”之类的粗糙规则来判断，每个幂都必须真正计算一次数位和。
程序自然的遍历顺序是先按底数 \(s\) 分组，再沿着各自的幂链向上走；但题目要的序列顺序却是最终数值的大小顺序。这两种顺序并不一致。来自较大底数的一项，完全可能插在若干较小底数产生的项之间。
所以实现都会把当前上界下找到的所有合法值先收集起来，保证不重复，再按数值排序。自适应的 C++ 版本从较小上界开始，不够就把上界乘以 10 重新生成；Python 和 Java 则直接取一个接近 \(10^{18}\) 的固定上界，足以覆盖第 30 项。无论哪种策略，只要“当前上界以下的全部合法值”已经生成完毕，取排序后列表中的对应位置就是答案。
C++、Python 和 Java 三个实现的核心循环完全一致：遍历候选数位和 \(s\)，从 \(s^2\) 开始，不断乘以 \(s\)，并在每一步用“对 10 取模再整除 10”的方式计算当前值的数位和。只有当这个值至少有两位，且数位和正好等于 \(s\) 时，它才会被记录下来。
实现之间的主要差别在于外层上界如何管理。C++ 版本支持一般的目标序号，因此会先在一个较小的上界下生成全部候选，如果数量还不够，就把上界提高一个十进制数量级后重新做一遍。Python 和 Java 版本则直接针对第 30 项，在一个很大的固定上界下完成全部枚举。固定字长语言中的乘法步骤还会额外防止溢出；Python 虽然有任意精度整数，但搜索本身仍然被限制在选定的上界之内。
所有命中的值都会进入去重后的容器，再按递增顺序读取。C++ 版本还加入了一个很小的检查点：先验证第二项确实是 \(512\)。这与已知示例一致，可以在输出最终结果之前快速确认枚举逻辑没有跑偏。
设搜索上界为 \(B\)，它的十进制位数为 \(D=d(B)\)。由于 \(s\le 9D\)，候选底数个数是 \(O(D)\)。对固定的底数 \(s\)，需要生成的幂的数量为
$$\#\{k\ge 2:s^k\le B\}=\max\!\left(0,\left\lfloor \log_s B\right\rfloor-1\right),$$
这最多是 \(O(D)\)。因此，总共被检查的幂的数量是 \(O(D^2)\)。
每次检查都要在至多 \(D\) 个十进制数字上计算数位和，所以总体代价是按十进制数字操作计的 \(O(D^3)\)。对于这里使用的上界，这个工作量非常小。内存复杂度是 \(O(m)\)，其中 \(m\) 是在最终取第 30 项之前实际保存下来的命中数量。自适应上界版本虽然可能重复运行几轮，但每轮只把上界提高一个十进制数量级，因此额外开销很有限。
Обозначим через \(\operatorname{digitSum}(N)\) сумму десятичных цифр числа \(N\). Нужно рассмотреть возрастающую последовательность всех чисел \(N\), имеющих как минимум две цифры и удовлетворяющих условию
$$N=\operatorname{digitSum}(N)^k,\qquad k\ge 2,\qquad N\ge 10.$$
Требуется найти ее 30-й элемент. Среди первых примеров находятся \(81=9^2\), \(512=8^3\), \(2401=7^4\) и \(4913=17^3\). Главная особенность задачи в том, что основание степени здесь не выбирается отдельно: оно обязано совпадать с суммой цифр итогового числа.
Поэтому наивный перебор всех натуральных чисел неэффективен. Реальные реализации делают наоборот: они перебирают возможные суммы цифр \(s\), строят цепочку степеней \(s^2,s^3,s^4,\dots\) и оставляют только те значения, у которых сумма цифр снова равна \(s\).
Вся идея сводится к ограниченному поиску по возможным суммам цифр. Как только это пространство поиска выбрано правильно, задача превращается в полное перечисление коротких цепочек степеней.
Если число \(N\) входит в искомую последовательность, то его основание обязано быть равно
$$s=\operatorname{digitSum}(N).$$
Следовательно, любой допустимый элемент имеет вид \(N=s^k\) при \(k\ge 2\). Поэтому интерес представляют не произвольные числа, а цепочки степеней, связанные с возможными суммами цифр. Перебор начинается с \(s=2\): при \(s=1\) получается только однозначное число \(1\), которое условием исключено.
Для фиксированного \(s\) все кандидаты имеют вид
$$s^2,\ s^3,\ s^4,\ \dots$$
Других чисел с тем же самым определяющим основанием здесь быть не может, потому что исходное уравнение уже полностью фиксирует базу степени.
Пусть нас интересуют только допустимые элементы, не превосходящие некоторой границы \(B\). Обозначим через \(d(x)\) число десятичных цифр числа \(x\). Тогда для любого \(N\le B\) выполняется
$$\operatorname{digitSum}(N)\le 9\,d(N)\le 9\,d(B).$$
Отсюда следует, что каждый допустимый элемент ниже \(B\) обязан происходить из основания из конечного диапазона
$$2\le s\le 9\,d(B).$$
Это и есть основная инварианта алгоритма. Одна реализация вычисляет этот предел напрямую из текущей границы, а версии с фиксированной границей используют немного более свободные константы, но обосновываются тем же самым рассуждением.
Для каждой кандидатной суммы цифр \(s\) степени не пересчитываются заново. Используется рекурсия
$$v_2=s^2,\qquad v_{k+1}=s\,v_k\quad (k\ge 2).$$
Так как \(s\ge 2\), эта цепочка строго возрастает. Значит, как только очередное значение превысило текущую границу \(B\), все последующие показатели тоже выходят за пределы диапазона, и данное основание можно сразу завершить. Это дает полный и непересекающийся перебор всех степеней \(s\) ниже границы.
Доказательство полноты очень короткое: если \(N\le B\) допустимо, то его основание в точности равно \(s=\operatorname{digitSum}(N)\), и при переборе этого \(s\) рекурсия неизбежно дойдет до \(s^k=N\) до того, как сработает условие остановки.
Возьмем \(s=8\). Начало цепочки таково:
$$8^2=64,\qquad 8^3=512,\qquad 8^4=4096,\qquad 8^5=32768.$$
Их суммы цифр равны
$$\operatorname{digitSum}(64)=10,\qquad \operatorname{digitSum}(512)=8,\qquad \operatorname{digitSum}(4096)=19,\qquad \operatorname{digitSum}(32768)=26.$$
Поэтому \(512\) принимается, а соседние степени отбрасываются. Тот же эффект виден и на другом основании: \(17^2=289\) не подходит, потому что сумма цифр равна \(19\), а \(17^3=4913\) подходит, поскольку \(4+9+1+3=17\). Значит, нельзя заменить проверку какой-то простой эвристикой наподобие “если основание однажды сработало, дальше будет так же”; каждую степень надо действительно проверять.
Естественный порядок перебора идет по основаниям \(s\), но искомая последовательность упорядочена по самим значениям чисел. Эти два порядка не совпадают. Удачное значение от большего основания вполне может оказаться между числами, полученными от меньших оснований.
Именно поэтому реализации сначала собирают все допустимые значения ниже выбранной границы, хранят их без повторов, а затем читают в возрастающем порядке. Адаптивная версия на C++ начинает с умеренной границы и умножает ее на 10, пока не будет накоплено достаточно членов. Версии на Python и Java сразу берут большую границу порядка \(10^{18}\), которой хватает для 30-го элемента. В обоих случаях ответ извлекается обычной сортировкой и выбором нужного индекса.
Реализации на C++, Python и Java используют один и тот же основной цикл: перебирают кандидатные суммы цифр \(s\), начинают с \(s^2\), затем многократно умножают на \(s\) и после каждого шага вычисляют сумму цифр, последовательно извлекая десятичные цифры делением на 10. Значение записывается только тогда, когда у него не меньше двух цифр и его сумма цифр в точности равна \(s\).
Главное различие связано с управлением внешней границей поиска. Реализация на C++ написана для общего запрашиваемого индекса, поэтому сначала строит весь список под небольшой границей, а затем увеличивает ее степенями 10, пока элементов не станет достаточно. Реализации на Python и Java сразу решают конкретный запрос на 30-й элемент под одной большой границей. В языках с фиксированной разрядностью повторное умножение дополнительно защищено от переполнения; Python использует встроенные целые произвольной длины, хотя сам поиск все равно ограничен выбранным потолком.
Подходящие значения складываются в контейнер без дубликатов и затем читаются по возрастанию. В версии на C++ есть еще и маленькая проверка: она убеждается, что второй элемент последовательности равен \(512\). Это совпадает с известным примером и служит быстрым контролем корректности перечисления перед окончательной выдачей результата.
Пусть \(B\) — граница поиска, а \(D=d(B)\) — число ее десятичных цифр. Так как \(s\le 9D\), количество кандидатных оснований равно \(O(D)\). Для фиксированного основания \(s\) число генерируемых степеней равно
$$\#\{k\ge 2:s^k\le B\}=\max\!\left(0,\left\lfloor \log_s B\right\rfloor-1\right),$$
то есть не превосходит \(O(D)\). Следовательно, суммарно проверяется \(O(D^2)\) степеней.
Каждая проверка вычисляет сумму цифр числа длины не более \(D\), поэтому общий объем работы составляет \(O(D^3)\) в операциях над десятичными цифрами. Для используемых здесь границ это очень мало. Память равна \(O(m)\), где \(m\) — число найденных допустимых элементов, сохраненных перед окончательным извлечением ответа. Адаптивная версия повторяет ограниченный поиск несколько раз, но каждая новая попытка увеличивает границу лишь на один десятичный порядок, поэтому практический перерасход остается небольшим.
لنرمز بـ \(\operatorname{digitSum}(N)\) إلى مجموع الأرقام العشرية للعدد \(N\). المطلوب هو ترتيب جميع الأعداد \(N\) ذات الرقمين على الأقل تصاعديًا بحيث تحقق الشرط
$$N=\operatorname{digitSum}(N)^k,\qquad k\ge 2,\qquad N\ge 10.$$
ثم استخراج الحد الثلاثين من هذه السلسلة. من الأمثلة المبكرة \(81=9^2\) و\(512=8^3\) و\(2401=7^4\) و\(4913=17^3\). الفكرة الجوهرية هنا أن الأساس ليس اختيارًا مستقلًا؛ بل يجب أن يساوي مجموع أرقام العدد نفسه.
لهذا السبب، فإن المرور على جميع الأعداد واحدًا واحدًا ليس هو المنظور الصحيح. ما تفعله الحلول هو عكس التفكير: تختار قيمة محتملة لمجموع الأرقام \(s\)، ثم تولد سلسلة القوى \(s^2,s^3,s^4,\dots\)، وبعد ذلك تحتفظ فقط بالقيم التي يعود مجموع أرقامها إلى \(s\) نفسه.
الحل كله عبارة عن بحث محدود على مجاميع الأرقام الممكنة. وما إن يتم تحديد فضاء البحث الصحيح، حتى تتحول المسألة إلى تعداد كامل لسلاسل قوى قصيرة.
إذا كان العدد \(N\) ينتمي إلى السلسلة المطلوبة، فلابد أن يكون أساسه هو
$$s=\operatorname{digitSum}(N).$$
وبالتالي فإن كل حد صحيح يكتب على الصورة \(N=s^k\) حيث \(k\ge 2\). معنى ذلك أن العناصر الرياضية الأساسية هنا ليست أعدادًا عشوائية، بل سلاسل القوى المرتبطة بقيم \(s\) الممكنة. ولهذا يبدأ البحث من \(s=2\)، لأن \(s=1\) لا يولد إلا العدد الأحادي \(1\)، وهو مستبعد من نص المسألة.
ولكل \(s\) ثابتة، فإن المرشحات الممكنة هي بالضبط
$$s^2,\ s^3,\ s^4,\ \dots$$
ولا توجد أعداد أخرى يمكن أن تنجح مع نفس مجموع الأرقام هذا، لأن المعادلة الأصلية حددت الأساس بالكامل.
افترض أننا لا نهتم إلا بالحدود الصحيحة التي لا تتجاوز سقفًا عدديًا \(B\). ولتكن \(d(x)\) هي عدد الأرقام العشرية في \(x\). عندئذٍ فإن أي عدد \(N\le B\) يحقق
$$\operatorname{digitSum}(N)\le 9\,d(N)\le 9\,d(B).$$
إذًا أي حد صحيح تحت \(B\) لابد أن يأتي من أساس ضمن المجال المنتهي
$$2\le s\le 9\,d(B).$$
هذه هي الثابتة الأساسية التي يعتمد عليها الكود. إحدى التنفيذات تحسب هذا الحد مباشرة من السقف الحالي، بينما تستخدم النسخ ذات السقف الثابت مجالًا عدديًا أوسع قليلًا مبنيًا على الفكرة نفسها، ولذلك تبقى الحجة الرياضية واحدة.
لكل أساس مرشح \(s\)، لا يعاد حساب \(s^k\) من الصفر في كل مرة، بل تستخدم العلاقة
$$v_2=s^2,\qquad v_{k+1}=s\,v_k\quad (k\ge 2).$$
وبما أن \(s\ge 2\)، فهذه السلسلة متزايدة تمامًا. لذلك، متى تجاوز حد ما السقف \(B\)، يصبح من المستحيل على أي أس أعلى أن يعود إلى المجال، ويمكن إنهاء هذه السلسلة فورًا. وبهذه الطريقة نحصل على مسح كامل بلا تكرار لكل قوى \(s\) الواقعة تحت السقف.
وبرهان الاكتمال مباشر جدًا: إذا كان \(N\le B\) حدًا صحيحًا، فإن أساسه بالضبط هو \(s=\operatorname{digitSum}(N)\)، وعند مرور البرنامج على هذا \(s\) فإن العلاقة التكرارية ستصل حتمًا إلى \(s^k=N\) قبل أن تتوقف.
لنأخذ \(s=8\). بداية السلسلة هي
$$8^2=64,\qquad 8^3=512,\qquad 8^4=4096,\qquad 8^5=32768.$$
ومجاميع الأرقام المقابلة هي
$$\operatorname{digitSum}(64)=10,\qquad \operatorname{digitSum}(512)=8,\qquad \operatorname{digitSum}(4096)=19,\qquad \operatorname{digitSum}(32768)=26.$$
إذن \(512\) يُقبل، بينما تُرفض القوى المجاورة له. ويظهر النمط نفسه مع أسس أخرى: \(17^2=289\) يفشل لأن مجموع أرقامه \(19\)، بينما \(17^3=4913\) ينجح لأن \(4+9+1+3=17\). وهذا يوضح أن النجاح لا ينتقل تلقائيًا من قوة إلى أخرى؛ بل يجب فحص كل قوة فعليًا.
الترتيب الطبيعي للبحث يكون بحسب الأساس \(s\)، لكن السلسلة المطلوبة في المسألة مرتبة بحسب القيم النهائية نفسها. وهذان الترتيبان لا يتطابقان. فقد يقع عنصر ناجح آتٍ من أساس أكبر بين عناصر نتجت عن أسس أصغر.
لهذا السبب تجمع التنفيذات كل القيم الصحيحة تحت السقف المختار، وتحفظها دون تكرار، ثم تقرأها بترتيب تصاعدي. النسخة التكيفية في ++C تبدأ بسقف صغير ثم تضربه في 10 حتى يصبح عدد العناصر كافيًا. أما نسختا Python وJava فتستخدمان سقفًا كبيرًا ثابتًا قريبًا من \(10^{18}\) وهو كافٍ للوصول إلى الحد الثلاثين. وفي الحالتين تُستخرج الإجابة من القائمة المرتبة النهائية.
التنفيذات في C++ وPython وJava تتبع الحلقة الأساسية نفسها: تمر على قيم \(s\) المحتملة، تبدأ من \(s^2\)، ثم تضرب تكراريًا في \(s\)، وبعد كل خطوة تحسب مجموع الأرقام عبر استخراج الأرقام العشرية بقسمة متتابعة على 10. ولا يُسجل أي عدد إلا إذا كان ذا رقمين على الأقل وكان مجموع أرقامه يساوي \(s\) بالضبط.
الاختلاف الرئيسي يظهر في إدارة السقف الخارجي. تنفيذ C++ مكتوب ليستقبل رتبة مطلوبة بشكل عام، لذلك يولد القائمة تحت سقف أولي ثم يرفع هذا السقف بقوى العشرة حتى يجد عددًا كافيًا من الحدود. أما تنفيذا Python وJava فيعالجان مباشرة طلب الحد الثلاثين تحت سقف كبير واحد. وفي اللغات ذات العرض الثابت تُحمى خطوة الضرب التكراري كذلك من فيضان القيم؛ أما Python فتستخدم أعدادًا صحيحة ذات دقة غير محدودة، رغم أن البحث الفعلي يظل محصورًا في السقف المختار.
تُجمع القيم المقبولة في بنية تمنع التكرار، ثم تُقرأ بترتيب متزايد. وتضيف نسخة C++ أيضًا فحصًا صغيرًا يؤكد أن الحد الثاني هو \(512\). هذا يتفق مع المثال المعروف ويعطي تحققًا سريعًا من صحة التعداد قبل إخراج الجواب النهائي.
إذا كان سقف البحث هو \(B\)، ولتكن \(D=d(B)\) هي عدد أرقامه العشرية، فإن عدد الأسس المرشحة يساوي \(O(D)\) لأن \(s\le 9D\). وبالنسبة إلى أساس ثابت \(s\)، فإن عدد القوى المولدة يساوي
$$\#\{k\ge 2:s^k\le B\}=\max\!\left(0,\left\lfloor \log_s B\right\rfloor-1\right),$$
وهو في أقصى الأحوال \(O(D)\). لذلك يكون عدد القوى التي تُفحص إجمالًا من رتبة \(O(D^2)\).
كل فحص يحتاج إلى حساب مجموع الأرقام لعدد طوله في الأكثر \(D\) خانة عشرية، ومن ثم يكون العمل الكلي \(O(D^3)\) عند القياس بعدد عمليات التعامل مع الخانات العشرية. وبالنسبة إلى الحدود المستخدمة هنا، فهذه الكلفة صغيرة جدًا عمليًا. أما الذاكرة فهي \(O(m)\)، حيث \(m\) هو عدد الحدود الصحيحة التي تحفظ قبل استخراج النتيجة النهائية. والنسخة ذات السقف التكيفي قد تعيد البحث عدة مرات، لكن كل إعادة تزيد السقف بمقدار مرتبة عشرية واحدة فقط، لذا يظل العبء الإضافي محدودًا.