We want to count all pairs \((b,n)\) for which \(b^n\) is an \(n\)-digit positive integer. In decimal language, the number of digits of the power must match the exponent itself.
The search is much smaller than it first appears. No base \(b \ge 10\) can work, and for each fixed base \(b \in \{1,\dots,9\}\) the valid exponents form a short initial interval. Summing those intervals gives the final total \(49\).
Let \(d(x)\) denote the number of decimal digits of a positive integer \(x\). The problem asks for the number of pairs \((b,n)\) with \(d(b^n)=n\).
If \(b \ge 10\), then \(b^n \ge 10^n\). Any number at least \(10^n\) has at least \(n+1\) digits, so it cannot be an \(n\)-digit number. Therefore every valid pair must satisfy
$$1 \le b \le 9.$$
This is the first decisive simplification: instead of infinitely many bases, there are only nine candidates.
For every positive integer \(x\),
$$d(x)=\lfloor \log_{10} x \rfloor + 1,$$
which is equivalent to
$$10^{d(x)-1} \le x \lt 10^{d(x)}.$$
So \(b^n\) has exactly \(n\) digits if and only if
$$10^{n-1} \le b^n \lt 10^n.$$
Taking base-10 logarithms gives
$$n-1 \le n\log_{10} b \lt n.$$
Because \(b \le 9\), we already know \(\log_{10} b \lt 1\), so the right-hand inequality is automatic. The real condition is the left-hand side:
$$n-1 \le n\log_{10} b.$$
Rearranging the inequality above yields
$$n(1-\log_{10} b) \le 1,$$
hence
$$n \le \frac{1}{1-\log_{10} b}.$$
Therefore, for a fixed base \(b\), the valid exponents are exactly
$$1 \le n \le \left\lfloor \frac{1}{1-\log_{10} b} \right\rfloor.$$
This shows that each base contributes a finite number of powers. It also explains the recurrence used by the implementation: if we define
$$a_0=1,\qquad a_{n+1}=b\,a_n,$$
then \(a_n=b^n\) for every \(n\), so repeated multiplication walks through all candidate powers of that base in order.
The counts by base are
$$1,1,1,2,3,4,6,10,21 \quad \text{for } b=1,2,3,4,5,6,7,8,9,$$
and their sum is
$$1+1+1+2+3+4+6+10+21=49.$$
We can also fix \(n\) first. From \(10^{n-1} \le b^n\) we obtain
$$10^{(n-1)/n} \le b,$$
so the valid bases are
$$b \in \left\{\left\lceil 10^{(n-1)/n} \right\rceil,\left\lceil 10^{(n-1)/n} \right\rceil+1,\dots,9\right\}.$$
Hence the number of valid bases for exponent \(n\) is
$$10-\left\lceil 10^{(n-1)/n} \right\rceil,$$
provided that the lower bound does not exceed \(9\). The largest possible exponent comes from the largest base \(9\):
$$n \le \left\lfloor \frac{1}{1-\log_{10} 9} \right\rfloor = 21.$$
So \(9^{21}\) is the last successful boundary case, while \(9^{22}\) already falls short: it has only 21 digits, not 22.
For \(n=5\), the lower bound is \(10^{4/5} \approx 6.31\). The admissible integer bases are \(7,8,9\), and indeed
$$7^5=16807,\qquad 8^5=32768,\qquad 9^5=59049,$$
all of which have five digits.
For base \(7\), the fixed-base formula gives
$$\left\lfloor \frac{1}{1-\log_{10} 7} \right\rfloor = 6.$$
That means \(7^1\) through \(7^6\) qualify, but \(7^7=823543\) has only six digits, so the run stops permanently there. The same boundary logic at the top end says that base \(9\) contributes exactly 21 valid powers.
The C++, Python, and Java implementations loop over bases \(1\) through \(9\). That range is complete because the mathematical argument above rules out every larger base before any computation starts.
For one chosen base, the implementation starts from \(1\) and multiplies by the base once per iteration. After the \(n\)-th multiplication, the current value is exactly \(b^n\). Converting that integer to decimal text gives the exact digit count, so there is no floating-point rounding risk near the boundary cases.
This is why the C++ and Java versions use arbitrary-precision integers, while Python relies on its built-in unbounded integer arithmetic.
Whenever the current digit count equals the current exponent, the total answer increases by one. As soon as the digit count becomes smaller than the exponent, the inner loop stops for that base. The proof above shows that this is safe: valid exponents for a fixed base form an initial segment \(1,2,\dots,k\), so after the first failure there can never be another success for the same base.
The implementations also include a checkpoint based on \(9^{21}\). That value has 21 digits, so it verifies the final successful boundary before the search necessarily dies out.
There are only 9 outer iterations, one for each possible base. The inner loop for a base stops immediately after the first exponent that fails, and the global search ends by exponent 22. Therefore the total running time is \(O(1)\) for this problem.
Space usage is also \(O(1)\) aside from the current big integer being multiplied. Even that object stays tiny here: the relevant boundary value \(9^{21}\) has only 21 decimal digits.
Gesucht ist die Anzahl aller Paare \((b,n)\), für die \(b^n\) eine positive ganze Zahl mit genau \(n\) Dezimalziffern ist. Die Ziffernzahl der Potenz muss also exakt mit dem Exponenten übereinstimmen.
Das Problem ist viel kleiner, als es zunächst aussieht. Keine Basis \(b \ge 10\) kann funktionieren, und für jede feste Basis \(b \in \{1,\dots,9\}\) bilden die gültigen Exponenten nur ein kurzes Anfangsintervall. Deren Gesamtzahl ist \(49\).
Sei \(d(x)\) die Anzahl der Dezimalziffern einer positiven ganzen Zahl \(x\). Dann suchen wir genau die Paare \((b,n)\) mit \(d(b^n)=n\).
Für \(b \ge 10\) gilt \(b^n \ge 10^n\). Jede Zahl, die mindestens \(10^n\) ist, besitzt mindestens \(n+1\) Ziffern und kann daher nicht genau \(n\)-stellig sein. Also muss für jedes gültige Paar gelten:
$$1 \le b \le 9.$$
Damit schrumpft die Suche sofort von unendlich vielen Basen auf nur neun Kandidaten.
Für jede positive ganze Zahl \(x\) gilt
$$d(x)=\lfloor \log_{10} x \rfloor + 1,$$
äquivalent zu
$$10^{d(x)-1} \le x \lt 10^{d(x)}.$$
Damit besitzt \(b^n\) genau dann \(n\) Ziffern, wenn
$$10^{n-1} \le b^n \lt 10^n.$$
Nach dem Logarithmieren erhält man
$$n-1 \le n\log_{10} b \lt n.$$
Da \(b \le 9\) ist, gilt automatisch \(\log_{10} b \lt 1\). Die entscheidende Bedingung ist also
$$n-1 \le n\log_{10} b.$$
Die obige Ungleichung lässt sich umformen zu
$$n(1-\log_{10} b) \le 1,$$
also
$$n \le \frac{1}{1-\log_{10} b}.$$
Für eine feste Basis \(b\) sind die zulässigen Exponenten daher genau
$$1 \le n \le \left\lfloor \frac{1}{1-\log_{10} b} \right\rfloor.$$
Jede Basis trägt also nur endlich viele Potenzen bei. Genau dieselbe Struktur steckt in der Implementierung: Definiert man rekursiv
$$a_0=1,\qquad a_{n+1}=b\,a_n,$$
so folgt induktiv \(a_n=b^n\). Wiederholte Multiplikation durch \(b\) erzeugt also die Kandidaten in der richtigen Reihenfolge.
Die Beiträge der einzelnen Basen sind
$$1,1,1,2,3,4,6,10,21 \quad \text{für } b=1,2,3,4,5,6,7,8,9,$$
und damit insgesamt
$$1+1+1+2+3+4+6+10+21=49.$$
Man kann stattdessen \(n\) festhalten. Aus \(10^{n-1} \le b^n\) folgt
$$10^{(n-1)/n} \le b,$$
also sind die zulässigen Basen
$$b \in \left\{\left\lceil 10^{(n-1)/n} \right\rceil,\left\lceil 10^{(n-1)/n} \right\rceil+1,\dots,9\right\}.$$
Die Anzahl gültiger Basen zum Exponenten \(n\) ist daher
$$10-\left\lceil 10^{(n-1)/n} \right\rceil,$$
sofern die Untergrenze höchstens \(9\) ist. Der größtmögliche Exponent entsteht bei der größten Basis \(9\):
$$n \le \left\lfloor \frac{1}{1-\log_{10} 9} \right\rfloor = 21.$$
Damit ist \(9^{21}\) der letzte erfolgreiche Randfall, während \(9^{22}\) schon nur noch 21 Ziffern besitzt.
Für \(n=5\) ist die Untergrenze \(10^{4/5} \approx 6{,}31\). Also kommen genau die Basen \(7,8,9\) infrage, und tatsächlich sind
$$7^5=16807,\qquad 8^5=32768,\qquad 9^5=59049,$$
allesamt fünfstellig.
Für die Basis \(7\) liefert die Formel
$$\left\lfloor \frac{1}{1-\log_{10} 7} \right\rfloor = 6.$$
Also funktionieren \(7^1\) bis \(7^6\), aber \(7^7=823543\) hat nur sechs Ziffern und scheidet endgültig aus. Dasselbe Randargument zeigt oben, dass Basis \(9\) genau 21 gültige Potenzen beiträgt.
Die Implementierungen in C++, Python und Java iterieren nur über die Basen \(1\) bis \(9\). Dieser Bereich ist vollständig, weil alle größeren Basen bereits mathematisch ausgeschlossen sind.
Für eine feste Basis startet die Implementierung bei \(1\) und multipliziert in jeder Schleifenrunde einmal mit der Basis. Nach der \(n\)-ten Multiplikation ist der aktuelle Wert also exakt \(b^n\). Durch Umwandlung in eine Dezimaldarstellung erhält man die Ziffernzahl ohne jedes Gleitkomma-Randproblem.
Darum verwenden die C++- und Java-Versionen Ganzzahlen mit beliebiger Präzision; Python besitzt diese Eigenschaft bereits eingebaut.
Immer wenn die aktuelle Ziffernzahl gleich dem aktuellen Exponenten ist, wird der Zähler erhöht. Sobald die Ziffernzahl kleiner als der Exponent wird, bricht die innere Schleife für diese Basis ab. Das ist korrekt, weil die zulässigen Exponenten zu einer festen Basis immer ein Anfangsintervall \(1,2,\dots,k\) bilden. Nach dem ersten Fehlschlag kann es also keinen späteren Treffer mehr geben.
Zusätzlich prüfen die Implementierungen den Grenzfall \(9^{21}\). Diese Potenz hat 21 Ziffern und bestätigt damit die letzte erfolgreiche Grenze der Suche.
Es gibt nur 9 äußere Iterationen, nämlich eine pro möglicher Basis. Die innere Schleife endet jeweils sofort nach dem ersten ungültigen Exponenten, und global ist spätestens bei Exponent 22 Schluss. Die Laufzeit ist für dieses Problem daher \(O(1)\).
Auch der Speicherbedarf ist \(O(1)\), abgesehen von der jeweils aktuellen großen Ganzzahl. Selbst diese bleibt hier sehr klein: Der relevante Grenzwert \(9^{21}\) besitzt nur 21 Dezimalziffern.
Aradığımız şey, \(b^n\) sayısının hem pozitif bir \(n\)-basamaklı tamsayı hem de bir \(n\). kuvvet olduğu tüm \((b,n)\) çiftlerinin sayısıdır. Başka bir deyişle, kuvvetin basamak sayısı üs ile tam olarak aynı olmalıdır.
Problem ilk bakışta sonsuz görünebilir, fakat aslında çok küçüktür. \(b \ge 10\) olan hiçbir taban çalışamaz; ayrıca sabit bir \(b \in \{1,\dots,9\}\) için uygun üsler kısa bir başlangıç aralığı oluşturur. Bu katkıların toplamı \(49\) eder.
\(d(x)\) ile pozitif bir tamsayı \(x\)'in ondalık basamak sayısını gösterelim. O zaman problem, \(d(b^n)=n\) koşulunu sağlayan \((b,n)\) çiftlerini saymaktır.
Eğer \(b \ge 10\) ise \(b^n \ge 10^n\) olur. \(10^n\)'e eşit ya da daha büyük her sayı en az \(n+1\) basamağa sahiptir; dolayısıyla tam olarak \(n\) basamaklı olamaz. Bu yüzden her geçerli çift için
$$1 \le b \le 9$$
olmak zorundadır. Böylece sonsuz taban kümesi bir anda dokuz adaya iner.
Her pozitif tamsayı \(x\) için
$$d(x)=\lfloor \log_{10} x \rfloor + 1$$
ve buna eşdeğer olarak
$$10^{d(x)-1} \le x \lt 10^{d(x)}$$
yazabiliriz. Bu nedenle \(b^n\) sayısının tam olarak \(n\) basamaklı olması için ve ancak bunun için
$$10^{n-1} \le b^n \lt 10^n$$
gereklidir. On tabanında logaritma alınca
$$n-1 \le n\log_{10} b \lt n$$
elde edilir. \(b \le 9\) olduğundan \(\log_{10} b \lt 1\) zaten doğrudur; belirleyici kısım sol eşitsizliktir:
$$n-1 \le n\log_{10} b.$$
Yukarıdaki eşitsizlik şu biçime dönüştürülür:
$$n(1-\log_{10} b) \le 1,$$
dolayısıyla
$$n \le \frac{1}{1-\log_{10} b}.$$
Böylece sabit bir \(b\) için geçerli üsler tam olarak
$$1 \le n \le \left\lfloor \frac{1}{1-\log_{10} b} \right\rfloor$$
aralığını oluşturur. Bu, her tabanın yalnızca sonlu sayıda katkı verdiğini gösterir. Aynı yapı doğrudan uygulamada da vardır: sabit bir \(b\) için
$$a_0=1,\qquad a_{n+1}=b\,a_n$$
şeklinde bir dizi tanımlarsak tümevarımla \(a_n=b^n\) elde ederiz. Yani art arda \(b\) ile çarpmak, o tabanın tüm aday kuvvetlerini sırayla üretir.
Taban bazında katkılar
$$1,1,1,2,3,4,6,10,21 \quad \text{ve sırasıyla } b=1,2,3,4,5,6,7,8,9$$
olur; toplam ise
$$1+1+1+2+3+4+6+10+21=49$$
eder.
İstersek önce \(n\)'i sabit tutabiliriz. \(10^{n-1} \le b^n\) eşitsizliğinden
$$10^{(n-1)/n} \le b$$
çıkar; dolayısıyla geçerli tabanlar
$$b \in \left\{\left\lceil 10^{(n-1)/n} \right\rceil,\left\lceil 10^{(n-1)/n} \right\rceil+1,\dots,9\right\}$$
şeklindedir. Buna göre sabit \(n\) için taban sayısı
$$10-\left\lceil 10^{(n-1)/n} \right\rceil$$
olur; tabii alt sınır 9'u aşmıyorsa. En büyük mümkün üs, en büyük taban olan \(9\)'dan gelir:
$$n \le \left\lfloor \frac{1}{1-\log_{10} 9} \right\rfloor = 21.$$
Bu yüzden \(9^{21}\) son başarılı sınır örneğidir; \(9^{22}\) ise yalnızca 21 basamaklıdır ve artık başarısızdır.
\(n=5\) için alt sınır \(10^{4/5} \approx 6.31\) olur. Bu durumda uygun tam sayı tabanlar yalnızca \(7,8,9\)'dur ve gerçekten de
$$7^5=16807,\qquad 8^5=32768,\qquad 9^5=59049$$
sayılarının her biri beş basamaklıdır.
Taban \(7\) için sabit-taban formülü
$$\left\lfloor \frac{1}{1-\log_{10} 7} \right\rfloor = 6$$
sonucunu verir. Yani \(7^1\) ile \(7^6\) arasında başarı vardır; fakat \(7^7=823543\) yalnızca altı basamaklı olduğu için aralık orada kalıcı olarak biter. Aynı mantık, taban \(9\)'un tam 21 uygun üs verdiğini de açıklar.
C++, Python ve Java uygulamaları yalnızca \(1\) ile \(9\) arasındaki tabanları gezer. Bunun yeterli olmasının nedeni, daha büyük tabanların matematiksel olarak baştan elenmiş olmasıdır.
Seçilen her taban için uygulama \(1\)'den başlar ve her adımda bir kez daha tabanla çarpar. \(n\). çarpmadan sonra eldeki değer tam olarak \(b^n\)'dir. Bu tam sayı ondalık yazıya çevrilip uzunluğu alınarak basamak sayısı bulunur; böylece sınır durumlarında kayan nokta hatası oluşmaz.
Bu yüzden C++ ve Java sürümleri keyfi büyüklükte tamsayı kullanır; Python ise bunu yerleşik olarak sağlar.
Geçerli toplam, basamak sayısı mevcut üsse eşit olduğunda bir artırılır. Basamak sayısı üsten küçük olur olmaz o taban için iç döngü durur. Bunun doğru olmasının nedeni, sabit bir taban için geçerli üslerin her zaman \(1,2,\dots,k\) biçiminde bir başlangıç aralığı oluşturmasıdır; ilk başarısızlıktan sonra aynı taban için tekrar başarı gelmez.
Uygulamalarda ayrıca \(9^{21}\) üzerinden bir sınır kontrolü bulunur. Bu sayı 21 basamaklıdır ve aramanın son başarılı kenar durumunu doğrular.
Dış döngü yalnızca 9 kez çalışır; her biri bir tabana karşılık gelir. İç döngü ise son başarılı üsten hemen sonraki ilk başarısızlıkta biter ve tüm arama en geç üs 22'de sona erer. Dolayısıyla bu problem için çalışma süresi \(O(1)\)'dir.
Bellek kullanımı da, eldeki büyük tamsayı dışında, \(O(1)\)'dir. Üstelik burada o tamsayı da küçüktür: kritik sınır değeri olan \(9^{21}\) yalnızca 21 ondalık basamağa sahiptir.
Queremos contar todos los pares \((b,n)\) tales que \(b^n\) sea un entero positivo de exactamente \(n\) dígitos. Dicho de otro modo, el número de dígitos de la potencia debe coincidir con el exponente.
La búsqueda real es muy pequeña. Ninguna base \(b \ge 10\) puede funcionar y, para cada base fija \(b \in \{1,\dots,9\}\), los exponentes válidos forman solo un intervalo inicial corto. Al sumar esas contribuciones se obtiene el total final \(49\).
Sea \(d(x)\) el número de dígitos decimales del entero positivo \(x\). Entonces el problema consiste en contar los pares \((b,n)\) para los cuales \(d(b^n)=n\).
Si \(b \ge 10\), entonces \(b^n \ge 10^n\). Cualquier número al menos igual a \(10^n\) tiene como mínimo \(n+1\) dígitos, así que no puede tener exactamente \(n\) dígitos. Por lo tanto, todo par válido debe satisfacer
$$1 \le b \le 9.$$
Esta es la primera gran reducción: de infinitas bases posibles pasamos a solo nueve candidatas.
Para todo entero positivo \(x\),
$$d(x)=\lfloor \log_{10} x \rfloor + 1,$$
lo cual es equivalente a
$$10^{d(x)-1} \le x \lt 10^{d(x)}.$$
Por eso, \(b^n\) tiene exactamente \(n\) dígitos si y solo si
$$10^{n-1} \le b^n \lt 10^n.$$
Al tomar logaritmos en base 10 obtenemos
$$n-1 \le n\log_{10} b \lt n.$$
Como ya sabemos que \(b \le 9\), la desigualdad de la derecha es automática porque \(\log_{10} b \lt 1\). La condición decisiva es la de la izquierda:
$$n-1 \le n\log_{10} b.$$
Reordenando esa desigualdad se obtiene
$$n(1-\log_{10} b) \le 1,$$
y por tanto
$$n \le \frac{1}{1-\log_{10} b}.$$
Así, para una base fija \(b\), los exponentes válidos son exactamente
$$1 \le n \le \left\lfloor \frac{1}{1-\log_{10} b} \right\rfloor.$$
Esto demuestra que cada base aporta solo un número finito de potencias. También explica la recurrencia que mantiene la implementación: si definimos
$$a_0=1,\qquad a_{n+1}=b\,a_n,$$
entonces \(a_n=b^n\) para todo \(n\). Multiplicar repetidamente por la base recorre todos los candidatos de esa base en orden exacto.
Las contribuciones por base son
$$1,1,1,2,3,4,6,10,21 \quad \text{para } b=1,2,3,4,5,6,7,8,9,$$
y su suma es
$$1+1+1+2+3+4+6+10+21=49.$$
También puede fijarse primero \(n\). A partir de \(10^{n-1} \le b^n\) se deduce
$$10^{(n-1)/n} \le b,$$
de modo que las bases válidas son
$$b \in \left\{\left\lceil 10^{(n-1)/n} \right\rceil,\left\lceil 10^{(n-1)/n} \right\rceil+1,\dots,9\right\}.$$
Por consiguiente, el número de bases válidas para un exponente \(n\) es
$$10-\left\lceil 10^{(n-1)/n} \right\rceil,$$
siempre que ese umbral no supere \(9\). El mayor exponente posible proviene de la mayor base, \(9\):
$$n \le \left\lfloor \frac{1}{1-\log_{10} 9} \right\rfloor = 21.$$
Eso explica por qué \(9^{21}\) es el último caso exitoso y \(9^{22}\) ya no sirve: tiene 21 dígitos, no 22.
Para \(n=5\), el umbral inferior es \(10^{4/5} \approx 6.31\). Las únicas bases enteras admisibles son \(7,8,9\), y en efecto
$$7^5=16807,\qquad 8^5=32768,\qquad 9^5=59049,$$
todas con cinco dígitos.
Para la base \(7\), la fórmula de base fija da
$$\left\lfloor \frac{1}{1-\log_{10} 7} \right\rfloor = 6.$$
Eso significa que \(7^1\) hasta \(7^6\) cuentan, pero \(7^7=823543\) tiene solo seis dígitos y a partir de ahí ya no puede volver a aparecer un acierto. El mismo razonamiento en el borde superior muestra que la base \(9\) aporta exactamente 21 potencias válidas.
Las implementaciones en C++, Python y Java recorren únicamente las bases \(1\) a \(9\). Ese rango es completo porque la demostración matemática descarta todas las bases mayores antes de comenzar a calcular.
Para cada base, la implementación parte de \(1\) y multiplica por la base una vez por iteración. Tras la \(n\)-ésima multiplicación, el valor actual es exactamente \(b^n\). Al convertir ese entero a texto decimal se obtiene el número exacto de dígitos, sin riesgo de errores de redondeo en coma flotante.
Por eso las versiones de C++ y Java usan enteros de precisión arbitraria, mientras que Python se apoya en sus enteros grandes integrados.
Cada vez que el número de dígitos coincide con el exponente actual, se incrementa el total. En cuanto el número de dígitos pasa a ser menor que el exponente, el bucle interior termina para esa base. La justificación es la prueba anterior: para una base fija, los exponentes válidos forman siempre un segmento inicial \(1,2,\dots,k\), así que después del primer fallo no puede aparecer otro acierto.
Además, las implementaciones incluyen una comprobación con \(9^{21}\). Ese valor tiene 21 dígitos y confirma el último caso válido en la frontera.
Solo hay 9 iteraciones exteriores, una por cada base posible. El bucle interior se detiene justo después del primer exponente inválido, y toda la búsqueda termina antes de llegar al exponente 22. Por tanto, el tiempo de ejecución es \(O(1)\) en este problema.
El espacio también es \(O(1)\), aparte del entero grande actual. Incluso ese entero sigue siendo pequeño aquí: el valor límite relevante \(9^{21}\) tiene solo 21 dígitos decimales.
我们要统计所有满足 \((b,n)\) 的配对，使得 \(b^n\) 恰好是一个 \(n\) 位正整数。也就是说，这个幂的十进制位数必须与指数本身完全相同。
这个问题看起来像是在无限多个幂里搜索，但实际规模很小。任何 \(b \ge 10\) 的底数都不可能成功；而对每个固定底数 \(b \in \{1,\dots,9\}\)，可行的指数只会形成一个很短的起始区间。把这些区间的长度加起来，最终答案就是 \(49\)。
记 \(d(x)\) 为正整数 \(x\) 的十进制位数。题目要求的就是满足 \(d(b^n)=n\) 的所有 \((b,n)\) 对。
如果 \(b \ge 10\)，那么 \(b^n \ge 10^n\)。任何不小于 \(10^n\) 的整数都至少有 \(n+1\) 位，因此不可能恰好有 \(n\) 位。于是每一个合法解都必须满足
$$1 \le b \le 9.$$
这是第一步关键压缩：候选底数从无限多个直接缩减为 9 个。
对任意正整数 \(x\)，都有
$$d(x)=\lfloor \log_{10} x \rfloor + 1,$$
等价地说，
$$10^{d(x)-1} \le x \lt 10^{d(x)}.$$
因此，\(b^n\) 恰好有 \(n\) 位，当且仅当
$$10^{n-1} \le b^n \lt 10^n.$$
取以 10 为底的对数后得到
$$n-1 \le n\log_{10} b \lt n.$$
由于这里已经知道 \(b \le 9\)，于是 \(\log_{10} b \lt 1\) 自动成立，所以真正起决定作用的是左边的不等式：
$$n-1 \le n\log_{10} b.$$
把上式整理一下，可以得到
$$n(1-\log_{10} b) \le 1,$$
也就是
$$n \le \frac{1}{1-\log_{10} b}.$$
所以，对固定底数 \(b\) 而言，所有合法指数恰好是
$$1 \le n \le \left\lfloor \frac{1}{1-\log_{10} b} \right\rfloor.$$
这说明每个底数只会贡献有限多个幂。它也揭示了实现里的核心递推：如果定义
$$a_0=1,\qquad a_{n+1}=b\,a_n,$$
那么由归纳法立刻有 \(a_n=b^n\)。也就是说，对同一个底数不断乘一次 \(b\)，就会按顺序精确地走过全部候选幂。
按底数分别计算，可得贡献数列
$$1,1,1,2,3,4,6,10,21 \quad \text{对应 } b=1,2,3,4,5,6,7,8,9,$$
总和为
$$1+1+1+2+3+4+6+10+21=49.$$
也可以反过来先固定 \(n\)。由 \(10^{n-1} \le b^n\) 可推出
$$10^{(n-1)/n} \le b,$$
因此合法底数就是
$$b \in \left\{\left\lceil 10^{(n-1)/n} \right\rceil,\left\lceil 10^{(n-1)/n} \right\rceil+1,\dots,9\right\}.$$
于是，对固定指数 \(n\)，合法底数个数等于
$$10-\left\lceil 10^{(n-1)/n} \right\rceil,$$
前提是这个下界没有超过 \(9\)。最大可能的指数来自最大的底数 \(9\)：
$$n \le \left\lfloor \frac{1}{1-\log_{10} 9} \right\rfloor = 21.$$
这正好解释了为什么 \(9^{21}\) 是最后一个成功边界，而 \(9^{22}\) 已经失败了，因为它只有 21 位而不是 22 位。
先看 \(n=5\)。此时下界是 \(10^{4/5} \approx 6.31\)，所以只有底数 \(7,8,9\) 有可能。确实，
$$7^5=16807,\qquad 8^5=32768,\qquad 9^5=59049,$$
它们全都是 5 位数。
再看固定底数 \(7\)。公式给出
$$\left\lfloor \frac{1}{1-\log_{10} 7} \right\rfloor = 6.$$
这意味着 \(7^1\) 到 \(7^6\) 都满足条件，而 \(7^7=823543\) 只有 6 位，所以从这里开始就再也不可能恢复成功。最高端的边界同理说明：底数 \(9\) 恰好贡献 21 个合法幂。
C++、Python 和 Java 实现都只遍历底数 \(1\) 到 \(9\)。之所以足够，是因为更大的底数已经被上面的数学证明完全排除。
对于某个固定底数，实现从 \(1\) 开始，每次循环再乘一次该底数。第 \(n\) 次乘法结束后，当前值就精确等于 \(b^n\)。随后把这个整数转成十进制字符串并读取长度，就能得到准确位数，不会遇到浮点边界误差。
这也是为什么 C++ 和 Java 版本使用任意精度整数，而 Python 直接依赖语言内建的大整数能力。
当当前位数与当前指数相等时，答案就加一。一旦当前位数小于当前指数，该底数的内层循环立即停止。上面的证明已经说明这是安全的：对固定底数来说，合法指数总是一个前缀区间 \(1,2,\dots,k\)，因此第一次失败之后不可能再出现新的成功。
实现里还包含一个以 \(9^{21}\) 为核心的检查点。这个值正好有 21 位，用来验证搜索中的最后一个成功边界。
外层循环只有 9 次，每次对应一个可能的底数。内层循环会在最后一个合法指数之后的第一次失败处立刻结束，而整个搜索在指数 22 之前就已经终止。因此，这道题的时间复杂度是 \(O(1)\)。
空间复杂度同样是 \(O(1)\)，唯一额外对象只是当前正在维护的大整数。即便如此，它在本题中也很小，因为关键边界值 \(9^{21}\) 只有 21 个十进制数字。
Нужно подсчитать все пары \((b,n)\), для которых число \(b^n\) является положительным целым и имеет ровно \(n\) десятичных цифр. Иначе говоря, длина записи степени должна совпадать с показателем степени.
На первый взгляд задача выглядит бесконечной, но на деле она очень мала. Ни одно основание \(b \ge 10\) не подходит, а для каждого фиксированного \(b \in \{1,\dots,9\}\) допустимые показатели образуют лишь короткий начальный отрезок. Сумма всех таких вкладов равна \(49\).
Обозначим через \(d(x)\) число десятичных цифр положительного целого \(x\). Тогда задача сводится к подсчету всех пар \((b,n)\), для которых \(d(b^n)=n\).
Если \(b \ge 10\), то \(b^n \ge 10^n\). Любое число не меньше \(10^n\) имеет как минимум \(n+1\) цифр, а значит, не может быть ровно \(n\)-значным. Следовательно, для любого допустимого решения необходимо
$$1 \le b \le 9.$$
Это сразу сокращает пространство поиска с бесконечного множества оснований до девяти кандидатов.
Для любого положительного целого \(x\) верно
$$d(x)=\lfloor \log_{10} x \rfloor + 1,$$
что эквивалентно записи
$$10^{d(x)-1} \le x \lt 10^{d(x)}.$$
Поэтому число \(b^n\) имеет ровно \(n\) цифр тогда и только тогда, когда
$$10^{n-1} \le b^n \lt 10^n.$$
После логарифмирования получаем
$$n-1 \le n\log_{10} b \lt n.$$
Поскольку \(b \le 9\), правая часть выполняется автоматически, ведь \(\log_{10} b \lt 1\). Значимой остается левая часть:
$$n-1 \le n\log_{10} b.$$
Перепишем это условие так:
$$n(1-\log_{10} b) \le 1,$$
то есть
$$n \le \frac{1}{1-\log_{10} b}.$$
Значит, при фиксированном основании \(b\) все допустимые показатели задаются формулой
$$1 \le n \le \left\lfloor \frac{1}{1-\log_{10} b} \right\rfloor.$$
Отсюда видно, что каждое основание дает лишь конечное число подходящих степеней. Здесь же появляется и рекуррентный объект, который поддерживает реализация: если определить
$$a_0=1,\qquad a_{n+1}=b\,a_n,$$
то по индукции \(a_n=b^n\). То есть последовательное умножение на \(b\) перебирает все степени данного основания в точном порядке.
Вклады по основаниям равны
$$1,1,1,2,3,4,6,10,21 \quad \text{для } b=1,2,3,4,5,6,7,8,9,$$
а их сумма составляет
$$1+1+1+2+3+4+6+10+21=49.$$
Можно зафиксировать сначала \(n\). Из неравенства \(10^{n-1} \le b^n\) следует
$$10^{(n-1)/n} \le b,$$
поэтому допустимые основания имеют вид
$$b \in \left\{\left\lceil 10^{(n-1)/n} \right\rceil,\left\lceil 10^{(n-1)/n} \right\rceil+1,\dots,9\right\}.$$
Число допустимых оснований для данного \(n\) равно
$$10-\left\lceil 10^{(n-1)/n} \right\rceil,$$
если только нижняя граница не превышает \(9\). Максимально возможный показатель приходит от максимального основания \(9\):
$$n \le \left\lfloor \frac{1}{1-\log_{10} 9} \right\rfloor = 21.$$
Именно поэтому \(9^{21}\) является последним успешным граничным случаем, а \(9^{22}\) уже не подходит: у него 21 цифра, а не 22.
Пусть \(n=5\). Тогда нижняя граница равна \(10^{4/5} \approx 6.31\), так что подходят только основания \(7,8,9\). И действительно,
$$7^5=16807,\qquad 8^5=32768,\qquad 9^5=59049,$$
и все эти числа пятизначные.
Для основания \(7\) формула для фиксированного основания дает
$$\left\lfloor \frac{1}{1-\log_{10} 7} \right\rfloor = 6.$$
Значит, подходят \(7^1,\dots,7^6\), но \(7^7=823543\) имеет только шесть цифр, и после этого успех уже невозможен. Тот же граничный аргумент сверху показывает, что основание \(9\) дает ровно 21 подходящую степень.
Реализации на C++, Python и Java перебирают только основания от \(1\) до \(9\). Этого достаточно, потому что все большие основания уже исключены математическим рассуждением.
Для каждого выбранного основания вычисление стартует с \(1\) и на каждой итерации еще раз умножает текущее значение на это основание. После \(n\)-го умножения в памяти находится ровно \(b^n\). Затем это число переводится в десятичную строку, и ее длина дает точное число цифр без каких-либо пограничных ошибок с плавающей точкой.
Именно поэтому версии на C++ и Java используют целые числа произвольной длины, а версия на Python опирается на встроенные большие целые.
Если текущее число цифр совпадает с текущим показателем, общий счетчик увеличивается на единицу. Как только число цифр становится меньше показателя, внутренний цикл для данного основания завершается. Это корректно, потому что допустимые показатели для фиксированного основания всегда образуют начальный отрезок \(1,2,\dots,k\); после первого неуспеха нового успеха уже быть не может.
Кроме того, реализации содержат проверку на значении \(9^{21}\). Эта степень имеет 21 цифру и подтверждает последний успешный граничный случай.
Внешний цикл выполняется всего 9 раз, по одному разу для каждого возможного основания. Внутренний цикл заканчивается сразу после первого неподходящего показателя, а вся процедура прекращается еще до показателя 22. Поэтому время работы для этой задачи равно \(O(1)\).
Память также имеет порядок \(O(1)\), если не считать текущее большое целое число. Но и оно здесь невелико: важнейшее граничное значение \(9^{21}\) содержит только 21 десятичную цифру.
المطلوب هو عد جميع الأزواج \((b,n)\) التي يكون فيها \(b^n\) عددًا صحيحًا موجبًا مكوّنًا من \(n\) أرقام بالضبط. أي إن عدد أرقام القوة يجب أن يساوي الأس نفسه.
رغم أن المسألة تبدو كأنها بحث في عدد لا نهائي من القوى، فإنها صغيرة جدًا فعليًا. لا يمكن لأي قيمة أساس \(b \ge 10\) أن تنجح، ولكل أساس ثابت \(b \in \{1,\dots,9\}\) تشكل الأسس المقبولة مقطعًا ابتدائيًا قصيرًا فقط. مجموع هذه المساهمات يساوي \(49\).
لنرمز بعدد الأرقام العشرية للعدد الصحيح الموجب \(x\) بالرمز \(d(x)\). عندئذ تصبح المسألة هي عد جميع الأزواج \((b,n)\) التي تحقق \(d(b^n)=n\).
إذا كان \(b \ge 10\)، فإن \(b^n \ge 10^n\). وكل عدد لا يقل عن \(10^n\) يملك على الأقل \(n+1\) رقمًا، ولذلك لا يمكن أن يكون ذا \(n\) أرقام بالضبط. إذن كل حل صالح لا بد أن يحقق
$$1 \le b \le 9.$$
وهذه أول خطوة حاسمة، لأنها تختزل عدد القواعد المرشحة من اللانهاية إلى تسع قيم فقط.
لكل عدد صحيح موجب \(x\) لدينا
$$d(x)=\lfloor \log_{10} x \rfloor + 1,$$
وهو مكافئ للصيغة
$$10^{d(x)-1} \le x \lt 10^{d(x)}.$$
ومن ثم فإن \(b^n\) يملك \(n\) أرقام بالضبط إذا وفقط إذا تحقق
$$10^{n-1} \le b^n \lt 10^n.$$
وبأخذ اللوغاريتم العشري نحصل على
$$n-1 \le n\log_{10} b \lt n.$$
وبما أن \(b \le 9\)، فإن \(\log_{10} b \lt 1\) محقق تلقائيًا؛ لذلك تبقى المتباينة اليسرى هي الشرط الفعلي:
$$n-1 \le n\log_{10} b.$$
يمكن إعادة ترتيب المتباينة السابقة على الصورة
$$n(1-\log_{10} b) \le 1,$$
ومنها
$$n \le \frac{1}{1-\log_{10} b}.$$
إذن، بالنسبة إلى أساس ثابت \(b\)، تكون جميع الأسس الصحيحة المقبولة هي
$$1 \le n \le \left\lfloor \frac{1}{1-\log_{10} b} \right\rfloor.$$
وهذا يبيّن أن كل أساس يساهم بعدد منته من القوى فقط. كما أنه يوضح المتتالية التي تعتمد عليها البرمجة: إذا عرفنا
$$a_0=1,\qquad a_{n+1}=b\,a_n,$$
فإننا نحصل بالاستقراء على \(a_n=b^n\) لكل \(n\). أي إن الضرب المتكرر في \(b\) يولّد جميع القوى المرشحة لذلك الأساس بالترتيب الصحيح تمامًا.
مساهمات القواعد عند \(b=1,2,3,4,5,6,7,8,9\) هي
$$1,1,1,2,3,4,6,10,21.$$
ومجموعها
$$1+1+1+2+3+4+6+10+21=49.$$
يمكن أيضًا تثبيت \(n\) أولًا. من المتباينة \(10^{n-1} \le b^n\) نستنتج
$$10^{(n-1)/n} \le b,$$
ولذلك تكون قيم الأساس المقبولة هي
$$b \in \left\{\left\lceil 10^{(n-1)/n} \right\rceil,\left\lceil 10^{(n-1)/n} \right\rceil+1,\dots,9\right\}.$$
ومن ثم فإن عدد القواعد المقبولة للأس \(n\) يساوي
$$10-\left\lceil 10^{(n-1)/n} \right\rceil,$$
ما دام الحد الأدنى لا يتجاوز \(9\). وأكبر أس ممكن يأتي من أكبر أساس، وهو \(9\):
$$n \le \left\lfloor \frac{1}{1-\log_{10} 9} \right\rfloor = 21.$$
وهذا يفسر لماذا تعد \(9^{21}\) آخر حالة ناجحة على الحد، بينما تفشل \(9^{22}\) لأنها تملك 21 رقمًا فقط لا 22.
عندما \(n=5\)، يكون الحد الأدنى \(10^{4/5} \approx 6.31\). إذن القواعد الصحيحة الوحيدة الممكنة هي \(7,8,9\)، وفعلاً
$$7^5=16807,\qquad 8^5=32768,\qquad 9^5=59049,$$
وجميعها مكوّنة من خمسة أرقام.
أما إذا ثبتنا الأساس \(7\)، فإن الصيغة تعطي
$$\left\lfloor \frac{1}{1-\log_{10} 7} \right\rfloor = 6.$$
وهذا يعني أن \(7^1\) حتى \(7^6\) صالحة، لكن \(7^7=823543\) يملك ستة أرقام فقط، ومن تلك اللحظة لا يمكن أن تظهر حالة ناجحة جديدة لهذا الأساس. والمنطق الحدّي نفسه يبين أن الأساس \(9\) يساهم في 21 قوة صالحة بالضبط.
تنفذ تطبيقات C++ وPython وJava المرور على القواعد من \(1\) إلى \(9\) فقط. وهذا كاف تمامًا لأن البرهان الرياضي استبعد كل أساس أكبر قبل البدء في الحساب.
لكل أساس ثابت، يبدأ التنفيذ من القيمة \(1\)، ثم يضرب في الأساس مرة واحدة في كل دورة. بعد الضربة رقم \(n\) تصبح القيمة الحالية مساوية تمامًا لـ \(b^n\). ثم تُحوَّل هذه القيمة إلى صيغة عشرية ويؤخذ طولها للحصول على عدد الأرقام بدقة كاملة، من دون أي مخاطرة بأخطاء التقريب العائم قرب الحدود.
ولهذا السبب تستخدم نسختا C++ وJava أعدادًا صحيحة ذات دقة غير محدودة، بينما تستفيد Python من دعمها المدمج للأعداد الكبيرة.
كلما ساوى عدد الأرقام الأس الحالي زيدت الإجابة بمقدار واحد. وحين يصبح عدد الأرقام أصغر من الأس، تتوقف الحلقة الداخلية لذلك الأساس فورًا. وصحة هذا التوقف مضمونة لأن الأسس المقبولة لأساس ثابت تشكل دائمًا مقطعًا ابتدائيًا من الشكل \(1,2,\dots,k\)؛ لذلك لا يمكن أن يظهر نجاح جديد بعد أول فشل.
كما تحتوي التطبيقات على نقطة تحقق باستخدام \(9^{21}\). هذه القيمة تملك 21 رقمًا، ولذلك تؤكد آخر حالة ناجحة على الحد قبل انتهاء البحث.
الحلقة الخارجية تعمل 9 مرات فقط، مرة لكل أساس ممكن. أما الحلقة الداخلية فتتوقف مباشرة بعد أول أس غير صالح، وينتهي البحث كله قبل الوصول إلى الأس 22. لذلك فإن زمن التنفيذ في هذه المسألة هو \(O(1)\).
واستهلاك الذاكرة هو أيضًا \(O(1)\)، باستثناء العدد الكبير الجاري تحديثه. وحتى هذا العدد يظل صغيرًا هنا، لأن القيمة الحدية المهمة \(9^{21}\) لا تتجاوز 21 رقمًا عشريًا.