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 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.

  • $\begingroup$ What is the range of $n$ ? $\endgroup$ – Yves Daoust Jul 22 '14 at 12:11
  • $\begingroup$ $\le 10^{18}$ ${}{}{}$ $\endgroup$ – saadtaame Jul 22 '14 at 12:12
  • 1
    $\begingroup$ link.springer.com/article/10.1007%2FBF01228507 $\endgroup$ – gammatester Jul 22 '14 at 12:16
  • 1
    $\begingroup$ Such a (fast) procedure is briefly needed at the beginning of the AKS algorithm showing "PRIMES is in P". $\endgroup$ – hardmath Jul 22 '14 at 12:23
  • 1
    $\begingroup$ 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. $\endgroup$ – 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).


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)
(23, 5)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.