Math.NumberTheory.Powers.General

Deprecated: Use Math.NumberTheory.Roots

Description: Deprecated

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

Documentation

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

For a positive power \( k \) and a given \( n \) return the integer \( k \)-th root \( \lfloor \sqrt[k]{n} \rfloor \). Throw an error if \( k \le 0 \) or if \( n \le 0 \) and \( k \) is even.

>>> integerRoot 6 65
2
>>> integerRoot 5 243
3
>>> integerRoot 4 624
4
>>> integerRoot 3 (-124)
-5
>>> integerRoot 1 5
5

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

For a positive exponent \( k \) calculate the exact integer \( k \)-th root of the second argument if it exists, otherwise return Nothing.

>>> map (uncurry exactRoot) [(6, 65), (5, 243), (4, 624), (3, -124), (1, 5)]
[Nothing,Just 3,Nothing,Nothing,Just 5]

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

For a positive exponent \( k \) test whether the second argument is a perfect \( k \)-th power.

>>> map (uncurry isKthPower) [(6, 65), (5, 243), (4, 624), (3, -124), (1, 5)]
[False,True,False,False,True]

isPerfectPower :: Integral a => a -> Bool

Test whether the argument is a non-trivial perfect power (e. g., square, cube, etc.).

>>> map isPerfectPower [0..10]
[True,True,False,False,True,False,False,False,True,True,False]
>>> map isPerfectPower [-10..0]
[False,False,True,False,False,False,False,False,False,True,True]

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

For \( n \not\in \{ -1, 0, 1 \} \) find the largest exponent \( k \) for which an exact integer \( k \)-th root \( r \) exists. Return \( (r, k) \).

For \( n \in \{ -1, 0, 1 \} \) arbitrarily large exponents exist; by arbitrary convention highestPower returns \( (n, 3) \).

>>> map highestPower [0..10]
[(0,3),(1,3),(2,1),(3,1),(2,2),(5,1),(6,1),(7,1),(2,3),(3,2),(10,1)]
>>> map highestPower [-10..0]
[(-10,1),(-9,1),(-2,3),(-7,1),(-6,1),(-5,1),(-4,1),(-3,1),(-2,1),(-1,3),(0,3)]

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.