The module sympy
library has two functions that could be useful here, integer_nthroot
and perfect_power
.
The first computes the integer part of the n-th root of a number, and also whether it is the exact result (so True
would mean it's a perfect cube). It will do so using integer arithmetic which should be faster and more precise than computations with float
s (viz, x**(1/3) = exp(1/3*log(x))
).
The function perfect_power
should choose the best way to determine whether a number is a perfect power. It will probably check whether all prime divisors p of "number" occur to a power (called the p-valuation of the number, or in sympy
, the multiplicity
) that have a common greatest divisor g, i.e., all the exponents are a multiple of g. If (and only if) that g is a multiple of 3 you have a perfect cube. Most candidates will be ruled out checking this for the fist few primes, starting with p=2 where you just have to check the number of trailing zero bits, cf. the sympy
function trailing()
.
Obviously this is unnecessarily general for your case: if it finds that the 2-valuation is 10 (= 2*5), it will go on to compute the 3-valuation, say it's 2, then so far we have a commen divisor of 2, and it will go on with the 5-valuation and so on, until the gcd is 1. But we could already stop when we see that 10 isn't a multiple of 3.
So you could do the same thing and stop as soons as the p-valuation isn't a multiple of 3: (Since we want to avoid unnecessary factorization, we don't use factorint
which would make it )
import sympy
def is_cube(n: int) -> bool:
if t := sympy.trailing(n): # 2-valuation
if t % 3: return False
n >>= t # remove the powers of 2
p = 3
while n >= p**3:
if m: = sympy.multiplicity(p, n):
if m % 3: return False
n //= p**m # make the number smaller
if n == 1: return True
p = sympy.nextprime(p)
return False
You start checking for 2 (then 3, 5...) which is extremely fast (the 2-valuation is just the number of trailing zero bits) and will immediately rule out most of the candidates, so only in very few cases you'll have to go up to larger primes. There are also other checks that could be made before searching for very large prime facors if necessary. For example x % 7
must be one of {0, 1, 6} for any 3rd power.
abs((x-round(x))/x) < epsilon
(for some small epsilon).