Math.NumberTheory.Powers.General

Calculating integer roots and determining perfect powers. The algorithms are moderately efficient.

Documentation

integerRoot :: (Integral a, Integral b) => b -> a -> a

Calculate an integer root, integerRoot k n computes the (floor of) the k-th root of n, where k must be positive. r = integerRoot k n means r^k <= n < (r+1)^k if that is possible at all. It is impossible if k is even and n < 0, since then r^k >= 0 for all r, then, and if k <= 0, integerRoot raises an error. For k < 5, a specialised version is called which should be more efficient than the general algorithm. However, it is not guaranteed that the rewrite rules for those fire, so if k is known in advance, it is safer to directly call the specialised versions.

exactRoot :: (Integral a, Integral b) => b -> a -> Maybe a

exactRoot k n returns Nothing if n is not a k-th power, Just r if n == r^k. If k is divisible by 4, 3 or 2, a residue test is performed to avoid the expensive calculation if it can thus be determined that n is not a k-th power.

isKthPower :: (Integral a, Integral b) => b -> a -> Bool

isKthPower k n checks whether n is a k-th power.

isPerfectPower :: Integral a => a -> Bool

isPerfectPower n checks whether n == r^k for some k > 1.

highestPower :: Integral a => a -> (a, Word)

highestPower n produces the pair (b,k) with the largest exponent k such that n == b^k, except for abs n <= 1, in which case arbitrarily large exponents exist, and by an arbitrary decision (n,3) is returned.

First, by trial division with small primes, the range of possible exponents is reduced (if p^e exactly divides n, then k must be a divisor of e, if several small primes divide n, k must divide the greatest common divisor of their exponents, which mostly will be 1, generally small; if none of the small primes divides n, the range of possible exponents is reduced since the base is necessarily large), if that has not yet determined the result, the remaining factor is examined by trying the divisors of the gcd of the prime exponents if some have been found, otherwise by trying prime exponents recursively.

largePFPower :: Integer -> Integer -> (Integer, Word)

largePFPower bd n produces the pair (b,k) with the largest exponent k such that n == b^k, where bd > 1 (it is expected that bd is much larger, at least 1000 or so), n > bd^2 and n has no prime factors p <= bd, skipping the trial division phase of highestPower when that is a priori known to be superfluous. It is only present to avoid duplication of work in factorisation and primality testing, it is not expected to be generally useful. The assumptions are not checked, if they are not satisfied, wrong results and wasted work may be the consequence.