# Finding all possible pairs of integers $(a,b)$ such that $a^b=n$.

Given a large integer $n$ (could be as large as $10^{18}$), how can I find all possible pairs of integers $(a,b)$ such that

$$a^b=n.$$

A fast algorithm is preferable.

The question How to quickly identify perfect powers concerns quick computations by hand, which are not going to solve the present problem.

• What is the range of $n$ ? – Yves Daoust Jul 22 '14 at 12:11
• $\le 10^{18}$ ${}{}{}$ – saadtaame Jul 22 '14 at 12:12
• link.springer.com/article/10.1007%2FBF01228507 – gammatester Jul 22 '14 at 12:16
• Such a (fast) procedure is briefly needed at the beginning of the AKS algorithm showing "PRIMES is in P". – hardmath Jul 22 '14 at 12:23
• This question should not be considered a duplicate. Given the requirement that $n$ can be large, efficiency becomes an important issue, which is not addressed in the other question/answers. – Yves Daoust Jul 23 '14 at 22:42

First check if $n=2^b$, then basically look for prime powers, i.e. check if $n=a^b$ with $b$ prime up to $b = \lfloor \log n / \log 3 \rfloor\;$ (this is just 37 for $n=10^{18}).\;$ There are fast checks for $b=2$ and you can use tables mod m for small primes e.g. check $a^3 \equiv n \pmod {61}$ etc. For larger primes compute the $b'$th root with Newton.

PS: The Bach/Sorensen paper is available as a Technical Report from http://research.cs.wisc.edu/techreports/1989/TR852.pdf

My suggestion:

Try the small values of $b$ (say up to $5$ or $4$) by direct integer root extraction/powering (test $\lfloor n^{\frac1b}\rfloor ^b=n$ ?)

And for the larger exponents, precompute all possible powers in a hash table. For the sixth power, you will need $1000$ entries. For the seventh, $373$, for the eighth, $178$... You can stop at $b=60,$ as $2^{60}>10^{18}.$ About $2000$ entries in total (about $6000$ if you also store the fifth powers).

Your numbers comfortably fit in a $64$ bits integer, so the only difficulty could be to compute the $b^{th}$ roots. You can just convert to double precision floating-point for this operation, as the truncation error will be tiny (much less than $1$, but mind the rounding). Revert to integer for the powerings.

At worse, a search will cost $4\ [3]$ "$pow$" calls for the roots ($2^{nd}$ to $5^{th}\ [4^{th}]$), $4\ [3]$ powerings ($8\ [5]$ integer multiplies in total) and a hash table lookup. Peanuts.

Here is Python code that implements the method (returns only one solution; can be improved to return all of them).

Initialization

from math import *

# Square
def Sqr(a):
return a * a

# Fill the table of powers for a^b <= 10^18, b >= 5 (5702 entries)
# The pow function is used to avoid overflow, but exact powers are stored
Powers= {}
a= 2
while pow(a, 5) <= 1.e18:
a_b= a * Sqr(Sqr(a))
b= 5
while pow(a, b) <= 1.e18:
Powers[a_b]= (a, b)
a_b*= a
b+= 1
a+= 1

Power test

# Returns (a, b) such that a^b = n, or None
def IsPower(n):
# Test small powers
a= int(round(pow(n, 0.5)))
if Sqr(a) == n:
return (a, 2)

a= int(round(pow(n, 1. / 3)))
if a * Sqr(a) == n:
return (a, 3)

a= int(round(pow(n, 0.25)))
if Sqr(Sqr(a)) == n:
return (a, 4)

# Lookup large powers
if n in Powers:
return Powers[n]

Sample output

print IsPower(4)
print IsPower(125)
print IsPower(94143178827)
print IsPower(42)
print IsPower(6436343)
print IsPower(6436343643634364)

(2, 2)
(5, 3)
(3, 23)
None
(23, 5)
None