-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/

-- | Efficient basic number-theoretic functions.
--   
--   A library of basic functionality needed for number-theoretic
--   calculations. The aim of this library is to provide efficient
--   implementations of the functions. Primes and related things (totients,
--   factorisation), powers (integer roots and tests, modular
--   exponentiation).
@package arithmoi
@version 0.13.2.0

-- | Container for pairwise coprime numbers.
module Math.NumberTheory.Euclidean.Coprimes

-- | The input list is assumed to be a factorisation of some number into a
--   list of powers of (possibly, composite) non-zero factors. The output
--   list is a factorisation of the same number such that all factors are
--   coprime. Such transformation is crucial to continue factorisation
--   (lazily, in parallel or concurrent fashion) without having to merge
--   multiplicities of primes, which occurs more than in one composite
--   factor.
--   
--   
--   >>> splitIntoCoprimes [(140, 1), (165, 1)]
--   Coprimes {unCoprimes = [(28,1),(33,1),(5,2)]}
--   
--   >>> splitIntoCoprimes [(360, 1), (210, 1)]
--   Coprimes {unCoprimes = [(7,1),(5,2),(3,3),(2,4)]}
--   
splitIntoCoprimes :: (Eq a, GcdDomain a, Eq b, Num b) => [(a, b)] -> Coprimes a b

-- | A list of pairwise coprime numbers with their multiplicities.
data Coprimes a b

-- | Unwrap.
unCoprimes :: Coprimes a b -> [(a, b)]

-- | Wrap a non-zero number with its multiplicity into Coprimes.
--   
--   
--   >>> singleton 210 1
--   Coprimes {unCoprimes = [(210,1)]}
--   
singleton :: (Eq a, GcdDomain a, Eq b, Num b) => a -> b -> Coprimes a b

-- | Add a non-zero number with its multiplicity to Coprimes.
--   
--   
--   >>> insert 360 1 (singleton 210 1)
--   Coprimes {unCoprimes = [(7,1),(5,2),(3,3),(2,4)]}
--   
--   >>> insert 2 4 (insert 7 1 (insert 5 2 (singleton 4 3)))
--   Coprimes {unCoprimes = [(7,1),(5,2),(2,10)]}
--   
insert :: (Eq a, GcdDomain a, Eq b, Num b) => a -> b -> Coprimes a b -> Coprimes a b
instance (GHC.Classes.Eq a, GHC.Classes.Eq b) => GHC.Classes.Eq (Math.NumberTheory.Euclidean.Coprimes.Coprimes a b)
instance (GHC.Classes.Eq a, Data.Euclidean.GcdDomain a, GHC.Classes.Eq b, GHC.Internal.Num.Num b) => GHC.Internal.Base.Monoid (Math.NumberTheory.Euclidean.Coprimes.Coprimes a b)
instance (GHC.Classes.Eq a, Data.Euclidean.GcdDomain a, GHC.Classes.Eq b, GHC.Internal.Num.Num b) => GHC.Internal.Base.Semigroup (Math.NumberTheory.Euclidean.Coprimes.Coprimes a b)
instance (GHC.Internal.Show.Show a, GHC.Internal.Show.Show b) => GHC.Internal.Show.Show (Math.NumberTheory.Euclidean.Coprimes.Coprimes a b)

-- | Chinese remainder theorem
module Math.NumberTheory.Moduli.Chinese

-- | chinese (n1, m1) (n2, m2) returns (n, lcm
--   m1 m2) such that n `mod` m1 == n1 and n `mod` m2 ==
--   n2, if exists. Moduli m1 and m2 are allowed to
--   have common factors.
--   
--   
--   >>> chinese (1, 2) (2, 3)
--   Just (-1, 6)
--   
--   >>> chinese (3, 4) (5, 6)
--   Just (-1, 12)
--   
--   >>> chinese (3, 4) (2, 6)
--   Nothing
--   
chinese :: (Eq a, Ring a, Euclidean a) => (a, a) -> (a, a) -> Maybe (a, a)

-- | Same as chinese, but operates on residues.
--   
--   
--   >>> :set -XDataKinds
--   
--   >>> import Data.Mod
--   
--   >>> (1 `modulo` 2) `chineseSomeMod` (2 `modulo` 3)
--   Just (5 `modulo` 6)
--   
--   >>> (3 `modulo` 4) `chineseSomeMod` (5 `modulo` 6)
--   Just (11 `modulo` 12)
--   
--   >>> (3 `modulo` 4) `chineseSomeMod` (2 `modulo` 6)
--   Nothing
--   
chineseSomeMod :: SomeMod -> SomeMod -> Maybe SomeMod

-- | A smooth number is an number, which can be represented as a
--   product of powers of elements from a given set (smooth basis). E. g.,
--   48 = 3 * 4 * 4 is smooth over a set {3, 4}, and 24 is not.
module Math.NumberTheory.SmoothNumbers

-- | An abstract representation of a smooth basis.
data SmoothBasis a

-- | Unwrap elements of a smooth basis.
unSmoothBasis :: SmoothBasis a -> [a]

-- | Build a SmoothBasis from a list of numbers, sanitizing it from
--   duplicates, zeros and units.
--   
--   
--   >>> fromList [2, 3]
--   SmoothBasis {unSmoothBasis = [2,3]}
--   
--   >>> fromList [2, 2]
--   SmoothBasis {unSmoothBasis = [2]}
--   
--   >>> fromList [1, 3]
--   SmoothBasis {unSmoothBasis = [3]}
--   
fromList :: (Eq a, GcdDomain a) => [a] -> SmoothBasis a

-- | Check that a given number is smooth under a given SmoothBasis.
--   
--   
--   >>> isSmooth (fromList [2,3]) 12
--   True
--   
--   >>> isSmooth (fromList [2,3]) 15
--   False
--   
isSmooth :: (Eq a, GcdDomain a) => SmoothBasis a -> a -> Bool

-- | Generate an infinite ascending list of smooth numbers over a
--   given smooth basis.
--   
--   This routine is more efficient than filtering with isSmooth.
--   
--   
--   >>> take 10 (smoothOver (fromList [2, 5]))
--   [1,2,4,5,8,10,16,20,25,32]
--   
smoothOver :: Integral a => SmoothBasis a -> [a]

-- | A generalization of smoothOver, suitable for
--   non-Integral domains. The first argument must be an appropriate
--   Ideal norm function, like norm or norm.
--   
--   This routine is more efficient than filtering with isSmooth.
--   
--   
--   >>> import Math.NumberTheory.Quadratic.GaussianIntegers
--   
--   >>> take 10 (smoothOver' norm (fromList [1+ι,3]))
--   [1,1+ι,2,2+2*ι,3,4,3+3*ι,4+4*ι,6,8]
--   
smoothOver' :: (Eq a, Num a, Ord b) => (a -> b) -> SmoothBasis a -> [a]
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Math.NumberTheory.SmoothNumbers.SmoothBasis a)

-- | A newtype wrapper around IntSet.
--   
--   This module is intended to be imported qualified, e. g.,
--   
--   
--   import Math.NumberTheory.Primes.IntSet (PrimeIntSet)
--   import qualified Math.NumberTheory.Primes.IntSet as PrimeIntSet
--   
module Math.NumberTheory.Primes.IntSet

-- | A set of Prime integers.
data PrimeIntSet

-- | Convert to a set of integers.
unPrimeIntSet :: PrimeIntSet -> IntSet

-- | Build a singleton set.
singleton :: Prime Int -> PrimeIntSet

-- | Build a set from a list of primes.
fromList :: [Prime Int] -> PrimeIntSet

-- | Build a set from an ascending list of primes (the precondition is not
--   checked).
fromAscList :: [Prime Int] -> PrimeIntSet

-- | Build a set from an ascending list of distinct primes (the
--   precondition is not checked).
fromDistinctAscList :: [Prime Int] -> PrimeIntSet

-- | Insert a prime into the set.
insert :: Prime Int -> PrimeIntSet -> PrimeIntSet

-- | Delete an integer from the set.
delete :: Int -> PrimeIntSet -> PrimeIntSet

-- | Check whether the given prime is a member of the set.
member :: Prime Int -> PrimeIntSet -> Bool

-- | Check whether the given prime is not a member of the set.
notMember :: Prime Int -> PrimeIntSet -> Bool

-- | Find a prime in the set, equal to the given integer, if any exists.
lookupEQ :: Int -> PrimeIntSet -> Maybe (Prime Int)

-- | Find the largest prime in the set, smaller than the given integer, if
--   any exists.
lookupLT :: Int -> PrimeIntSet -> Maybe (Prime Int)

-- | Find the smallest prime in the set, greater than the given integer, if
--   any exists.
lookupGT :: Int -> PrimeIntSet -> Maybe (Prime Int)

-- | Find the largest prime in the set, smaller or equal to the given
--   integer, if any exists.
lookupLE :: Int -> PrimeIntSet -> Maybe (Prime Int)

-- | Find the smallest prime in the set, greater or equal to the given
--   integer, if any exists.
lookupGE :: Int -> PrimeIntSet -> Maybe (Prime Int)

-- | Check whether the set is empty.
null :: PrimeIntSet -> Bool

-- | Cardinality of the set.
size :: PrimeIntSet -> Int

-- | Check whether the first argument is a subset of the second one.
isSubsetOf :: PrimeIntSet -> PrimeIntSet -> Bool

-- | Check whether the first argument is a proper subset of the second one.
isProperSubsetOf :: PrimeIntSet -> PrimeIntSet -> Bool

-- | Check whether two sets are disjoint.
disjoint :: PrimeIntSet -> PrimeIntSet -> Bool

-- | Difference between a set of primes and a set of integers.
difference :: PrimeIntSet -> IntSet -> PrimeIntSet

-- | An alias to difference.
(\\) :: PrimeIntSet -> IntSet -> PrimeIntSet
infixl 9 \\

-- | Symmetric difference of two sets of primes.
symmetricDifference :: PrimeIntSet -> PrimeIntSet -> PrimeIntSet

-- | Intersection of a set of primes and a set of integers.
intersection :: PrimeIntSet -> IntSet -> PrimeIntSet

-- | Filter primes satisfying a predicate.
filter :: (Prime Int -> Bool) -> PrimeIntSet -> PrimeIntSet

-- | Partition primes according to a predicate.
partition :: (Prime Int -> Bool) -> PrimeIntSet -> (PrimeIntSet, PrimeIntSet)

-- | Split into primes strictly less and strictly greater than the first
--   argument.
split :: Int -> PrimeIntSet -> (PrimeIntSet, PrimeIntSet)

-- | Simultaneous split and member.
splitMember :: Prime Int -> PrimeIntSet -> (PrimeIntSet, Bool, PrimeIntSet)

-- | Simultaneous split and lookupEQ.
splitLookupEQ :: Int -> PrimeIntSet -> (PrimeIntSet, Maybe (Prime Int), PrimeIntSet)

-- | Decompose a set into pieces based on the structure of the underlying
--   tree.
splitRoot :: PrimeIntSet -> [PrimeIntSet]

-- | Fold a set using the given right-associative operator.
foldr :: (Prime Int -> b -> b) -> b -> PrimeIntSet -> b

-- | Fold a set using the given left-associative operator.
foldl :: (a -> Prime Int -> a) -> a -> PrimeIntSet -> a

-- | A strict version of foldr.
foldr' :: (Prime Int -> b -> b) -> b -> PrimeIntSet -> b

-- | A strict version of foldl.
foldl' :: (a -> Prime Int -> a) -> a -> PrimeIntSet -> a

-- | Delete the smallest prime in the set.
deleteMin :: PrimeIntSet -> PrimeIntSet

-- | Delete the largest prime in the set.
deleteMax :: PrimeIntSet -> PrimeIntSet

-- | Split a set into the smallest prime and the rest, if non-empty.
minView :: PrimeIntSet -> Maybe (Prime Int, PrimeIntSet)

-- | Split a set into the largest prime and the rest, if non-empty.
maxView :: PrimeIntSet -> Maybe (Prime Int, PrimeIntSet)

-- | Convert the set to a list of ascending primes.
toAscList :: PrimeIntSet -> [Prime Int]

-- | Convert the set to a list of descending primes.
toDescList :: PrimeIntSet -> [Prime Int]
instance GHC.Internal.Data.Data.Data Math.NumberTheory.Primes.IntSet.PrimeIntSet
instance GHC.Classes.Eq Math.NumberTheory.Primes.IntSet.PrimeIntSet
instance GHC.Internal.IsList.IsList Math.NumberTheory.Primes.IntSet.PrimeIntSet
instance GHC.Internal.Base.Monoid Math.NumberTheory.Primes.IntSet.PrimeIntSet
instance Control.DeepSeq.NFData Math.NumberTheory.Primes.IntSet.PrimeIntSet
instance GHC.Classes.Ord Math.NumberTheory.Primes.IntSet.PrimeIntSet
instance GHC.Internal.Base.Semigroup Math.NumberTheory.Primes.IntSet.PrimeIntSet
instance GHC.Internal.Show.Show Math.NumberTheory.Primes.IntSet.PrimeIntSet

-- | Number of primes not exceeding n, π(n), and
--   n-th prime; also fast, but reasonably accurate approximations
--   to these.
module Math.NumberTheory.Primes.Counting

-- | primeCount n == π(n) is the number of (positive)
--   primes not exceeding n.
--   
--   For efficiency, the calculations are done on 64-bit signed integers,
--   therefore n must not exceed primeCountMaxArg.
--   
--   Requires O(n^0.5) space, the time complexity is
--   roughly O(n^0.7). For small bounds,
--   primeCount n simply counts the primes not exceeding
--   n, for bounds from 30000 on, Meissel's algorithm is
--   used in the improved form due to D.H. Lehmer, cf.
--   http://en.wikipedia.org/wiki/Prime_counting_function#Algorithms_for_evaluating_.CF.80.28x.29.
primeCount :: Integer -> Integer

-- | Maximal allowed argument of primeCount. Currently 8e18.
primeCountMaxArg :: Integer

-- | nthPrime n calculates the n-th prime.
--   Numbering of primes is 1-based, so nthPrime 1 ==
--   2.
--   
--   Requires O((n*log n)^0.5) space, the time complexity
--   is roughly O((n*log n)^0.7. The argument must be
--   strictly positive.
nthPrime :: Int -> Prime Integer

-- | approxPrimeCount n gives an approximation of the
--   number of primes not exceeding n. The approximation is fairly
--   good for n large enough.
approxPrimeCount :: Integral a => a -> a

-- | Following property holds:
--   
--   
--   approxPrimeCount n >= primeCount n || n >= approxPrimeCountOverestimateLimit
--   
approxPrimeCountOverestimateLimit :: Integral a => a

-- | nthPrimeApprox n gives an approximation to the n-th
--   prime. The approximation is fairly good for n large enough.
nthPrimeApprox :: Integer -> Integer

-- | Following property holds:
--   
--   
--   nthPrimeApprox n <= nthPrime n || n >= nthPrimeApproxUnderestimateLimit
--   
nthPrimeApproxUnderestimateLimit :: Integer

module Math.NumberTheory.Primes

-- | Wrapper for prime elements of a. It is supposed to be
--   constructed by nextPrime / precPrime. and eliminated by
--   unPrime.
--   
--   One can leverage Enum instance to generate lists of primes.
--   Here are some examples.
--   
--   
--   
- Generate primes from the given interval:
--   
--   
--   
--   >>> :set -XFlexibleContexts
--   
--   >>> [nextPrime 101 .. precPrime 130]
--   [Prime 101,Prime 103,Prime 107,Prime 109,Prime 113,Prime 127]
--   
--   
--   
--   
- Generate an infinite list of primes:
--   
--   
--   
--   [nextPrime 101 ..]
--   [Prime 101,Prime 103,Prime 107,Prime 109,Prime 113,Prime 127...
--   
--   
--   
--   
- Generate primes from the given interval of form p = 6k+5:
--   
--   
--   
--   >>> [nextPrime 101, nextPrime 107 .. precPrime 150]
--   [Prime 101,Prime 107,Prime 113,Prime 131,Prime 137,Prime 149]
--   
--   
--   
--   
- Get next prime:
--   
--   
--   
--   >>> succ (nextPrime 101)
--   Prime 103
--   
--   
--   
--   
- Get previous prime:
--   
--   
--   
--   >>> pred (nextPrime 101)
--   Prime 97
--   
--   
--   
--   
- Count primes less than a given number (cf.
--   approxPrimeCount):
--   
--   
--   
--   >>> fromEnum (precPrime 100)
--   25
--   
--   
--   
--   
- Get 25-th prime number (cf. nthPrimeApprox):
--   
--   
--   
--   >>> toEnum 25 :: Prime Int
--   Prime 97
--   
data Prime a

-- | Unwrap prime element.
unPrime :: Prime a -> a

-- | Convert between primes of different types, similar in spirit to
--   toIntegralSized.
--   
--   A simpler version of this function is:
--   
--   
--   toPrimeIntegral :: (Integral a, Integral b) => a -> Maybe b
--   toPrimeIntegral (Prime a)
--     | toInteger a == b = Just (Prime (fromInteger b))
--     | otherwise        = Nothing
--     where
--       b = toInteger a
--   
--   
--   The point of toPrimeIntegral is to avoid redundant conversions
--   and conditions, when it is safe to do so, determining type sizes
--   statically with bitSizeMaybe. For example,
--   toPrimeIntegral from Prime Int to Prime
--   Word boils down to Just . fromIntegral.
toPrimeIntegral :: (Integral a, Integral b, Bits a, Bits b) => Prime a -> Maybe (Prime b)

-- | Smallest prime, greater or equal to argument.
--   
--   
--   nextPrime (-100) ==    2
--   nextPrime  1000  == 1009
--   nextPrime  1009  == 1009
--   
nextPrime :: (Bits a, Integral a, UniqueFactorisation a) => a -> Prime a

-- | Largest prime, less or equal to argument. Undefined, when argument
--   < 2.
--   
--   
--   precPrime 100 == 97
--   precPrime  97 == 97
--   
precPrime :: (Bits a, Integral a, UniqueFactorisation a) => a -> Prime a

-- | A class for unique factorisation domains.
class Num a => UniqueFactorisation a

-- | Factorise a number into a product of prime powers. Factorisation of 0
--   is an undefined behaviour. Otherwise following invariants hold:
--   
--   
--   abs n == abs (product (map (\(p, k) -> unPrime p ^ k) (factorise n)))
--   all ((> 0) . snd) (factorise n)
--   
--   
--   
--   >>> factorise (1 :: Integer)
--   []
--   
--   >>> factorise (-1 :: Integer)
--   []
--   
--   >>> factorise (6 :: Integer)
--   [(Prime 2,1),(Prime 3,1)]
--   
--   >>> factorise (-108 :: Integer)
--   [(Prime 2,2),(Prime 3,3)]
--   
--   
--   This function is a replacement for factorise. If you were
--   looking for the latter, please import
--   Math.NumberTheory.Primes.Factorisation instead of this module.
--   
--   Warning: there are no guarantees of any particular order of
--   prime factors, do not expect them to be ascending. E. g.,
--   
--   
--   >>> factorise 10251562501
--   [(Prime 101701,1),(Prime 100801,1)]
--   
factorise :: UniqueFactorisation a => a -> [(Prime a, Word)]

-- | Check whether an argument is prime. If it is then return an associated
--   prime.
--   
--   
--   >>> isPrime (3 :: Integer)
--   Just (Prime 3)
--   
--   >>> isPrime (4 :: Integer)
--   Nothing
--   
--   >>> isPrime (-5 :: Integer)
--   Just (Prime 5)
--   
--   
--   This function is a replacement for isPrime. If you were looking
--   for the latter, please import Math.NumberTheory.Primes.Testing
--   instead of this module.
isPrime :: UniqueFactorisation a => a -> Maybe (Prime a)

-- | Restore a number from its factorisation.
factorBack :: Num a => [(Prime a, Word)] -> a

-- | Ascending list of primes.
--   
--   
--   >>> take 10 primes
--   [Prime 2,Prime 3,Prime 5,Prime 7,Prime 11,Prime 13,Prime 17,Prime 19,Prime 23,Prime 29]
--   
--   
--   primes is a polymorphic list, so the results of computations
--   are not retained in memory. Make it monomorphic to take advantages of
--   memoization. Compare
--   
--   
--   >>> primes !! 1000000 :: Prime Int -- (5.32 secs, 6,945,267,496 bytes)
--   Prime 15485867
--   
--   >>> primes !! 1000000 :: Prime Int -- (5.19 secs, 6,945,267,496 bytes)
--   Prime 15485867
--   
--   
--   against
--   
--   
--   >>> let primes' = primes :: [Prime Int]
--   
--   >>> primes' !! 1000000 :: Prime Int -- (5.29 secs, 6,945,269,856 bytes)
--   Prime 15485867
--   
--   >>> primes' !! 1000000 :: Prime Int -- (0.02 secs, 336,232 bytes)
--   Prime 15485867
--   
primes :: Integral a => [Prime a]
instance GHC.Internal.Enum.Bounded (Math.NumberTheory.Primes.Types.Prime GHC.Types.Int)
instance GHC.Internal.Enum.Bounded (Math.NumberTheory.Primes.Types.Prime GHC.Types.Word)
instance GHC.Internal.Enum.Enum (Math.NumberTheory.Primes.Types.Prime GHC.Num.Integer.Integer)
instance GHC.Internal.Enum.Enum (Math.NumberTheory.Primes.Types.Prime GHC.Num.Natural.Natural)
instance GHC.Internal.Enum.Enum (Math.NumberTheory.Primes.Types.Prime GHC.Types.Int)
instance GHC.Internal.Enum.Enum (Math.NumberTheory.Primes.Types.Prime GHC.Types.Word)
instance Math.NumberTheory.Primes.UniqueFactorisation GHC.Types.Int
instance Math.NumberTheory.Primes.UniqueFactorisation GHC.Num.Integer.Integer
instance Math.NumberTheory.Primes.UniqueFactorisation GHC.Num.Natural.Natural
instance Math.NumberTheory.Primes.UniqueFactorisation GHC.Types.Word

-- | Efficient calculation of linear recurrent sequences, including
--   Fibonacci and Lucas sequences.
module Math.NumberTheory.Recurrences.Linear

-- | Infinite zero-based table of factorials.
--   
--   
--   >>> take 5 factorial
--   [1,1,2,6,24]
--   
--   
--   The time-and-space behaviour of factorial is similar to
--   described in Math.NumberTheory.Recurrences.Bilinear#memory.
factorial :: (Num a, Enum a) => Infinite a

-- | Prime factors of a factorial.
--   
--   
--   factorialFactors n == factorise (factorial !! n)
--   
--   
--   
--   >>> factorialFactors 10
--   [(Prime 2,8),(Prime 3,4),(Prime 5,2),(Prime 7,1)]
--   
factorialFactors :: Word -> [(Prime Word, Word)]

-- | fibonacci k calculates the k-th Fibonacci
--   number in O(log (abs k)) steps. The index may be
--   negative. This is efficient for calculating single Fibonacci numbers
--   (with large index), but for computing many Fibonacci numbers in close
--   proximity, it is better to use the simple addition formula starting
--   from an appropriate pair of successive Fibonacci numbers.
fibonacci :: Num a => Int -> a

-- | fibonacciPair k returns the pair (F(k),
--   F(k+1)) of the k-th Fibonacci number and its successor,
--   thus it can be used to calculate the Fibonacci numbers from some index
--   on without needing to compute the previous. The pair is efficiently
--   calculated in O(log (abs k)) steps. The index may be
--   negative.
fibonacciPair :: Num a => Int -> (a, a)

-- | lucas k computes the k-th Lucas number. Very
--   similar to fibonacci.
lucas :: Num a => Int -> a

-- | lucasPair k computes the pair (L(k), L(k+1))
--   of the k-th Lucas number and its successor. Very similar to
--   fibonacciPair.
lucasPair :: Num a => Int -> (a, a)

-- | generalLucas p q k calculates the quadruple (U(k),
--   U(k+1), V(k), V(k+1)) where U(i) is the Lucas sequence
--   of the first kind and V(i) the Lucas sequence of the second
--   kind for the parameters p and q, where p^2-4q /=
--   0. Both sequences satisfy the recurrence relation A(j+2) =
--   p*A(j+1) - q*A(j), the starting values are U(0) = 0, U(1) =
--   1 and V(0) = 2, V(1) = p. The Fibonacci numbers form the
--   Lucas sequence of the first kind for the parameters p = 1, q =
--   -1 and the Lucas numbers form the Lucas sequence of the second
--   kind for these parameters. Here, the index must be non-negative, since
--   the terms of the sequence for negative indices are in general not
--   integers.
generalLucas :: Num a => a -> a -> Int -> (a, a, a, a)

-- | Bilinear recurrent sequences and Bernoulli numbers, roughly covering
--   Ch. 5-6 of Concrete Mathematics by R. L. Graham, D. E. Knuth
--   and O. Patashnik.
--   
--   Note on memory leaks and memoization. Top-level definitions in
--   this module are polymorphic, so the results of computations are not
--   retained in memory. Make them monomorphic to take advantages of
--   memoization. Compare
--   
--   
--   >>> binomial !! 1000 !! 1000 :: Integer -- (0.01 secs, 1,385,512 bytes)
--   1
--   
--   >>> binomial !! 1000 !! 1000 :: Integer -- (0.01 secs, 1,381,616 bytes)
--   1
--   
--   
--   against
--   
--   
--   >>> let binomial' = binomial :: [[Integer]]
--   
--   >>> binomial' !! 1000 !! 1000 :: Integer -- (0.01 secs, 1,381,696 bytes)
--   1
--   
--   >>> binomial' !! 1000 !! 1000 :: Integer -- (0.01 secs, 391,152 bytes)
--   1
--   
module Math.NumberTheory.Recurrences.Bilinear

-- | Infinite zero-based table of binomial coefficients (also known as
--   Pascal triangle).
--   
--   
--   binomial !! n !! k == n! / k! / (n - k)!
--   
--   
--   Note that binomial !! n !! k is asymptotically slower than
--   binomialLine n !! k, but imposes only Semiring
--   constraint.
--   
--   
--   >>> take 6 binomial :: [[Int]]
--   [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]
--   
binomial :: Semiring a => Infinite [a]

-- | Pascal triangle, rotated by 45 degrees.
--   
--   
--   binomialRotated !! n !! k == (n + k)! / n! / k! == binomial !! (n + k) !! k
--   
--   
--   Note that binomialRotated !! n !! k is asymptotically slower
--   than binomialDiagonal n !! k, but imposes only Semiring
--   constraint.
--   
--   
--   >>> take 6 (map (take 6) binomialRotated) :: [[Int]]
--   [[1,1,1,1,1,1],[1,2,3,4,5,6],[1,3,6,10,15,21],[1,4,10,20,35,56],[1,5,15,35,70,126],[1,6,21,56,126,252]]
--   
binomialRotated :: Semiring a => Infinite (Infinite a)

-- | The n-th (zero-based) line of binomial (and the n-th diagonal
--   of binomialRotated).
--   
--   
--   >>> binomialLine 5
--   [1,5,10,10,5,1]
--   
binomialLine :: (Enum a, GcdDomain a) => a -> [a]

-- | The n-th (zero-based) diagonal of binomial (and the n-th line
--   of binomialRotated).
--   
--   
--   >>> take 6 (binomialDiagonal 5)
--   [1,6,21,56,126,252]
--   
binomialDiagonal :: (Enum a, GcdDomain a) => a -> Infinite a

-- | Prime factors of a binomial coefficient.
--   
--   
--   binomialFactors n k == factorise (binomial !! n !! k)
--   
--   
--   
--   >>> binomialFactors 10 4
--   [(Prime 2,1),(Prime 3,1),(Prime 5,1),(Prime 7,1)]
--   
binomialFactors :: Word -> Word -> [(Prime Word, Word)]

-- | Infinite zero-based table of Stirling numbers of the first
--   kind.
--   
--   
--   >>> take 5 (map (take 5) stirling1)
--   [[1],[0,1],[0,1,1],[0,2,3,1],[0,6,11,6,1]]
--   
--   
--   Complexity: stirling1 !! n !! k is O(n ln n) bits long, its
--   computation takes O(k n^2 ln n) time and forces thunks stirling1
--   !! i !! j for 0 <= i <= n and max(0, k - n +
--   i) <= j <= k.
--   
--   One could also consider unsignedStirling1st from
--   combinat package to compute stand-alone values.
stirling1 :: (Num a, Enum a) => Infinite [a]

-- | Infinite zero-based table of Stirling numbers of the second
--   kind.
--   
--   
--   >>> take 5 (map (take 5) stirling2)
--   [[1],[0,1],[0,1,1],[0,1,3,1],[0,1,7,6,1]]
--   
--   
--   Complexity: stirling2 !! n !! k is O(n ln n) bits long, its
--   computation takes O(k n^2 ln n) time and forces thunks stirling2
--   !! i !! j for 0 <= i <= n and max(0, k - n +
--   i) <= j <= k.
--   
--   One could also consider stirling2nd from combinat
--   package to compute stand-alone values.
stirling2 :: (Num a, Enum a) => Infinite [a]

-- | Infinite one-based table of Lah numbers. lah !! n !! k
--   equals to lah(n + 1, k + 1).
--   
--   
--   >>> take 5 (map (take 5) lah)
--   [[1],[2,1],[6,6,1],[24,36,12,1],[120,240,120,20,1]]
--   
--   
--   Complexity: lah !! n !! k is O(n ln n) bits long, its
--   computation takes O(k n ln n) time and forces thunks lah !! n !!
--   i for 0 <= i <= k.
lah :: Integral a => Infinite [a]

-- | Infinite zero-based table of Eulerian numbers of the first
--   kind.
--   
--   
--   >>> take 5 (map (take 5) eulerian1)
--   [[],[1],[1,1],[1,4,1],[1,11,11,1]]
--   
--   
--   Complexity: eulerian1 !! n !! k is O(n ln n) bits long, its
--   computation takes O(k n^2 ln n) time and forces thunks eulerian1
--   !! i !! j for 0 <= i <= n and max(0, k - n +
--   i) <= j <= k.
eulerian1 :: (Num a, Enum a) => Infinite [a]

-- | Infinite zero-based table of Eulerian numbers of the second
--   kind.
--   
--   
--   >>> take 5 (map (take 5) eulerian2)
--   [[],[1],[1,2],[1,8,6],[1,22,58,24]]
--   
--   
--   Complexity: eulerian2 !! n !! k is O(n ln n) bits long, its
--   computation takes O(k n^2 ln n) time and forces thunks eulerian2
--   !! i !! j for 0 <= i <= n and max(0, k - n +
--   i) <= j <= k.
eulerian2 :: (Num a, Enum a) => Infinite [a]

-- | Infinite zero-based sequence of Bernoulli numbers, computed via
--   connection with stirling2.
--   
--   
--   >>> take 5 bernoulli
--   [1 % 1,(-1) % 2,1 % 6,0 % 1,(-1) % 30]
--   
--   
--   Complexity: bernoulli !! n is O(n ln n) bits long, its
--   computation takes O(n^3 ln n) time and forces thunks stirling2 !!
--   i !! j for 0 <= i <= n and 0 <= j <=
--   i.
--   
--   One could also consider bernoulli from combinat package
--   to compute stand-alone values.
bernoulli :: Integral a => Infinite (Ratio a)

-- | The same sequence as euler', but with type [a]
--   instead of [Ratio a] as the denominators in euler'
--   are always 1.
--   
--   
--   >>> take 10 euler :: [Integer]
--   [1,0,-1,0,5,0,-61,0,1385,0]
--   
euler :: Integral a => Infinite a

-- | Infinite zero-based list of the n-th order Euler polynomials
--   evaluated at 1. The algorithm used was derived from
--   Algorithms for Bernoulli numbers and Euler numbers by Kwang-Wu
--   Chen, third formula of the Corollary in page 7. Element-by-element
--   division of sequences A1986631 and A006519 in OEIS.
--   
--   
--   >>> take 10 eulerPolyAt1 :: [Rational]
--   [1 % 1,1 % 2,0 % 1,(-1) % 4,0 % 1,1 % 2,0 % 1,(-17) % 8,0 % 1,31 % 2]
--   
eulerPolyAt1 :: Integral a => Infinite (Ratio a)

-- | Faulhaber's formula.
--   
--   
--   >>> sum (map (^ 10) [0..100])
--   959924142434241924250
--   
--   >>> sum $ zipWith (*) (faulhaberPoly 10) (iterate (* 100) 1)
--   959924142434241924250 % 1
--   
faulhaberPoly :: (GcdDomain a, Integral a) => Int -> [Ratio a]

module Math.NumberTheory.Recurrences

-- | Infinite zero-based table of partition numbers.
--   
--   
--   >>> take 10 partition
--   [1,1,2,3,5,7,11,15,22,30]
--   
--   
--   
--   >>> :set -XDataKinds
--   
--   >>> import Data.Mod
--   
--   >>> partition !! 1000 :: Mod 1000
--   (991 `modulo` 1000)
--   
partition :: Num a => Infinite a

-- | Primality tests.
module Math.NumberTheory.Primes.Testing

-- | isPrime n tests whether n is a prime (negative or
--   positive). It is a combination of trial division and Baillie-PSW test.
--   
--   If isPrime n returns False then n is
--   definitely composite. There is a theoretical possibility that
--   isPrime n is True, but in fact n is not
--   prime. However, no such numbers are known and none exist below
--   2^64. If you have found one, please report it, because it is
--   a major discovery.
isPrime :: Integer -> Bool

-- | isCertifiedPrime n tests primality of n,
--   first trial division by small primes is performed, then a Baillie PSW
--   test and finally a prime certificate is constructed and verified,
--   provided no step before found n to be composite. Constructing
--   prime certificates can take a very long time, so use this with
--   care.
isCertifiedPrime :: Integer -> Bool

-- | Primality test after Baillie, Pomerance, Selfridge and Wagstaff. The
--   Baillie-PSW test consists of a strong Fermat probable primality test
--   followed by a (strong) Lucas primality test. This implementation
--   assumes that the number n to test is odd and larger than
--   3. Even and small numbers have to be handled before. Also,
--   before applying this test, trial division by small primes should be
--   performed to identify many composites cheaply (although the
--   Baillie-PSW test is rather fast, about the same speed as a strong
--   Fermat test for four or five bases usually, it is, for large numbers,
--   much more costly than trial division by small primes, the primes less
--   than 1000, say, so eliminating numbers with small prime
--   factors beforehand is more efficient).
--   
--   The Baillie-PSW test is very reliable, so far no composite numbers
--   passing it are known, and it is known (Gilchrist 2010) that no
--   Baillie-PSW pseudoprimes exist below 2^64. However, a
--   heuristic argument by Pomerance indicates that there are likely
--   infinitely many Baillie-PSW pseudoprimes. On the other hand, according
--   to http://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html
--   there is reason to believe that there are none with less than several
--   thousand digits, so that for most use cases the test can be considered
--   definitive.
bailliePSW :: Integer -> Bool

-- | Miller-Rabin probabilistic primality test. It consists of the trial
--   division test and several rounds of the strong Fermat test with
--   different bases. The choice of trial divisors and bases are
--   implementation details and may change in future silently.
--   
--   First argument stands for the number of rounds of strong Fermat test.
--   If it is 0, only trial division test is performed.
--   
--   If millerRabinV k n returns False then n is
--   definitely composite. Otherwise n may appear composite with
--   probability 1/4^k.
millerRabinV :: Int -> Integer -> Bool

-- | isStrongFermatPP n b tests whether non-negative
--   n is a strong Fermat probable prime for base b.
--   
--   Apart from primes, also some composite numbers have the tested
--   property, but those are rare. Very rare are composite numbers having
--   the property for many bases, so testing a large prime candidate with
--   several bases can identify composite numbers with high probability. An
--   odd number n > 3 is prime if and only if
--   isStrongFermatPP n b holds for all b with
--   2 <= b <= (n-1)/2, but of course checking all those
--   bases would be less efficient than trial division, so one normally
--   checks only a relatively small number of bases, depending on the
--   desired degree of certainty. The probability that a randomly chosen
--   base doesn't identify a composite number n is less than
--   1/4, so five to ten tests give a reasonable level of
--   certainty in general.
--   
--   Please consult Deterministic variants of the Miller-Rabin primality
--   test for the best choice of bases.
isStrongFermatPP :: Integer -> Integer -> Bool

-- | isFermatPP n b tests whether n is a Fermat
--   probable prime for the base b, that is, whether b^(n-1)
--   mod n == 1. This is a weaker but simpler condition.
--   However, more is lost in strength than is gained in simplicity, so for
--   primality testing, the strong check should be used. The remarks about
--   the choice of bases to test from isStrongFermatPP
--   apply with the modification that if a and b are
--   Fermat bases for n, then a*b always is a
--   Fermat base for n too. A Charmichael number is a
--   composite number n which is a Fermat probable prime for all
--   bases b coprime to n. By the above, only primes
--   p <= n/2 not dividing n need to be tested to
--   identify Carmichael numbers (however, testing all those primes would
--   be less efficient than determining Carmichaelness from the prime
--   factorisation; but testing an appropriate number of prime bases is
--   reasonable to find out whether it's worth the effort to undertake the
--   prime factorisation).
isFermatPP :: Integer -> Integer -> Bool

-- | trialDivisionPrimeTo bound n tests whether n
--   is coprime to all primes <= bound. If n <=
--   bound^2, this is a full prime test, but very slow if n
--   has no small prime divisors.
trialDivisionPrimeTo :: Integer -> Integer -> Bool

-- | Type for numbers, accompanied by their factorisation.
module Math.NumberTheory.Prefactored

-- | A container for a number and its pairwise coprime (but not necessarily
--   prime) factorisation. It is designed to preserve information about
--   factors under multiplication. One can use this representation to speed
--   up prime factorisation and computation of arithmetic functions.
--   
--   For instance, let p and q be big primes:
--   
--   
--   >>> let p = 1000000000000000000000000000057 :: Integer
--   
--   >>> let q = 2000000000000000000000000000071 :: Integer
--   
--   
--   It would be difficult to compute the totient function of their product
--   as is, because once we multiplied them the information of factors is
--   lost and totient (p * q) would take ages.
--   Things become different if we simply change types of p and
--   q to prefactored ones:
--   
--   
--   >>> let p = 1000000000000000000000000000057 :: Prefactored Integer
--   
--   >>> let q = 2000000000000000000000000000071 :: Prefactored Integer
--   
--   
--   Now the totient function can be computed instantly:
--   
--   
--   >>> import Math.NumberTheory.ArithmeticFunctions
--   
--   >>> prefValue $ totient (p^2 * q^3)
--   8000000000000000000000000001752000000000000000000000000151322000000000000000000000006445392000000000000000000000135513014000000000000000000001126361040
--   
--   >>> prefValue $ totient $ totient (p^2 * q^3)
--   2133305798262843681544648472180210822742702690942899511234131900112583590230336435053688694839034890779375223070157301188739881477320529552945446912000
--   
--   
--   Let us look under the hood:
--   
--   
--   >>> import Math.NumberTheory.ArithmeticFunctions
--   
--   >>> prefFactors $ totient (p^2 * q^3)
--   Coprimes {unCoprimes = [(1000000000000000000000000000057,1),(41666666666666666666666666669,1),(2000000000000000000000000000071,2),(111111111111111111111111111115,1),(2,4),(3,3)]}
--   
--   >>> prefFactors $ totient $ totient (p^2 * q^3)
--   Coprimes {unCoprimes = [(39521,1),(227098769,1),(22222222222222222222222222223,1),(2000000000000000000000000000071,1),(361696272343,1),(85331809838489,1),(6046667,1),(199937,1),(5,3),(41666666666666666666666666669,1),(2,22),(3,8)]}
--   
--   
--   Pairwise coprimality of factors is crucial, because it allows us to
--   process them independently, possibly even in parallel or concurrent
--   fashion.
--   
--   Following invariant is guaranteed to hold:
--   
--   
--   abs (prefValue x) = abs (product (map (uncurry (^)) (prefFactors x)))
--   
data Prefactored a

-- | Create Prefactored from a given number.
--   
--   
--   >>> fromValue 123
--   Prefactored {prefValue = 123, prefFactors = Coprimes {unCoprimes = [(123,1)]}}
--   
fromValue :: (Eq a, GcdDomain a) => a -> Prefactored a

-- | Create Prefactored from a given list of pairwise coprime (but
--   not necessarily prime) factors with multiplicities.
--   
--   
--   >>> fromFactors (splitIntoCoprimes [(140, 1), (165, 1)])
--   Prefactored {prefValue = 23100, prefFactors = Coprimes {unCoprimes = [(28,1),(33,1),(5,2)]}}
--   
--   >>> fromFactors (splitIntoCoprimes [(140, 2), (165, 3)])
--   Prefactored {prefValue = 88045650000, prefFactors = Coprimes {unCoprimes = [(28,2),(33,3),(5,5)]}}
--   
fromFactors :: Semiring a => Coprimes a Word -> Prefactored a
instance GHC.Classes.Eq a => GHC.Classes.Eq (Math.NumberTheory.Prefactored.Prefactored a)
instance (GHC.Classes.Eq a, GHC.Internal.Num.Num a, Data.Euclidean.GcdDomain a) => GHC.Internal.Num.Num (Math.NumberTheory.Prefactored.Prefactored a)
instance (GHC.Classes.Eq a, Data.Euclidean.GcdDomain a) => Data.Semiring.Semiring (Math.NumberTheory.Prefactored.Prefactored a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Math.NumberTheory.Prefactored.Prefactored a)
instance (GHC.Classes.Eq a, Data.Euclidean.GcdDomain a, Math.NumberTheory.Primes.UniqueFactorisation a) => Math.NumberTheory.Primes.UniqueFactorisation (Math.NumberTheory.Prefactored.Prefactored a)

-- | Generalised Möbius inversion
module Math.NumberTheory.MoebiusInversion

-- | generalInversion g n evaluates the generalised Möbius
--   inversion of g at the argument n.
--   
--   The generalised Möbius inversion implemented here allows an efficient
--   calculation of isolated values of the function f : N -> Z
--   if the function g defined by
--   
--   
--   g n = sum [f (n `quot` k) | k <- [1 .. n]]
--   
--   
--   can be cheaply computed. By the generalised Möbius inversion formula,
--   then
--   
--   
--   f n = sum [moebius k * g (n `quot` k) | k <- [1 .. n]]
--   
--   
--   which allows the computation in O(n) steps, if the values of
--   the Möbius function are known. A slightly different formula, used
--   here, does not need the values of the Möbius function and allows the
--   computation in O(n^0.75) steps, using O(n^0.5) memory.
--   
--   An example of a pair of such functions where the inversion allows a
--   more efficient computation than the direct approach is
--   
--   
--   f n = number of reduced proper fractions with denominator <= n
--   
--   g n = number of proper fractions with denominator <= n
--   
--   
--   (a proper fraction is a fraction 0 < n/d < 1).
--   Then f n is the cardinality of the Farey sequence of order
--   n (minus 1 or 2 if 0 and/or 1 are included in the Farey
--   sequence), or the sum of the totients of the numbers 2 <= k
--   <= n. f n is not easily directly computable, but then
--   g n = n*(n-1)/2 is very easy to compute, and hence the
--   inversion gives an efficient method of computing f n.
--   
--   Since the function arguments are used as array indices, the domain of
--   f is restricted to Int.
--   
--   The value f n is then computed by generalInversion g
--   n. Note that when many values of f are needed, there are
--   far more efficient methods, this method is only appropriate to compute
--   isolated values of f.
generalInversion :: forall t (v :: Type -> Type). (Num t, Vector v t) => Proxy v -> (Word -> t) -> Word -> t

-- | totientSum n is, for n > 0, the sum of
--   [totient k | k <- [1 .. n]], computed via generalised
--   Möbius inversion. See
--   http://mathworld.wolfram.com/TotientSummatoryFunction.html for
--   the formula used for totientSum.
--   
--   
--   >>> import Data.Proxy
--   
--   >>> totientSum (Proxy :: Proxy Data.Vector.Unboxed.Vector) 100 :: Int
--   3044
--   
--   >>> totientSum (Proxy :: Proxy Data.Vector.Vector) 100 :: Integer
--   3044
--   
totientSum :: forall t (v :: Type -> Type). (Integral t, Vector v t) => Proxy v -> Word -> t

-- | Singleton data types.
module Math.NumberTheory.Moduli.Singleton

-- | This singleton data type establishes a correspondence between a modulo
--   m on type level and its factorisation on term level.
data SFactors a (m :: Nat)

-- | Create a singleton from a type-level positive modulo m,
--   passed in a constraint.
--   
--   
--   >>> :set -XDataKinds
--   
--   >>> sfactors :: SFactors Integer 13
--   SFactors {unSFactors = [(Prime 13,1)]}
--   
sfactors :: forall a (m :: Nat). (Ord a, UniqueFactorisation a, KnownNat m) => SFactors a m

-- | Create a singleton from factors of m. Factors must be
--   distinct, as in output of factorise.
--   
--   
--   >>> import Math.NumberTheory.Primes
--   
--   >>> someSFactors (factorise 98)
--   SFactors {unSFactors = [(Prime 2,1),(Prime 7,2)]}
--   
someSFactors :: (Ord a, Num a) => [(Prime a, Word)] -> Some (SFactors a)

-- | Factors of m.
unSFactors :: SFactors a m -> [(Prime a, Word)]

-- | Convert a singleton to a proof that m is known. Usage
--   example:
--   
--   
--   toModulo :: SFactors Integer m -> Natural
--   toModulo t = case proofFromSFactors t of Sub Dict -> natVal t
--   
proofFromSFactors :: forall a (m :: Nat). Integral a => SFactors a m -> () :- KnownNat m

-- | This singleton data type establishes a correspondence between a modulo
--   m on type level and a cyclic group of the same order on term
--   level.
data CyclicGroup a (m :: Nat)

-- | Create a singleton from a type-level positive modulo m,
--   passed in a constraint.
--   
--   
--   >>> :set -XDataKinds
--   
--   >>> import Data.Maybe
--   
--   >>> cyclicGroup :: Maybe (CyclicGroup Integer 169)
--   Just (CGOddPrimePower' (Prime 13) 2)
--   
--   
--   
--   >>> :set -XTypeOperators -XNoStarIsType
--   
--   >>> import GHC.TypeNats
--   
--   >>> sfactorsToCyclicGroup (sfactors :: SFactors Integer 4)
--   Just CG4'
--   
--   >>> sfactorsToCyclicGroup (sfactors :: SFactors Integer (2 * 13 ^ 3))
--   Just (CGDoubleOddPrimePower' (Prime 13) 3)
--   
--   >>> sfactorsToCyclicGroup (sfactors :: SFactors Integer  (4 * 13))
--   Nothing
--   
cyclicGroup :: forall a (m :: Nat). (Integral a, UniqueFactorisation a, KnownNat m) => Maybe (CyclicGroup a m)

-- | Create a singleton from factors. Factors must be distinct, as in
--   output of factorise.
cyclicGroupFromFactors :: (Eq a, Num a) => [(Prime a, Word)] -> Maybe (Some (CyclicGroup a))

-- | Similar to cyclicGroupFromFactors . factorise, but much
--   faster, because it but performes only one primality test instead of
--   full factorisation.
cyclicGroupFromModulo :: (Integral a, UniqueFactorisation a) => a -> Maybe (Some (CyclicGroup a))

-- | Convert a cyclic group to a proof that m is known. Usage
--   example:
--   
--   
--   toModulo :: CyclicGroup Integer m -> Natural
--   toModulo t = case proofFromCyclicGroup t of Sub Dict -> natVal t
--   
proofFromCyclicGroup :: forall a (m :: Nat). Integral a => CyclicGroup a m -> () :- KnownNat m

-- | Unidirectional pattern for residues modulo 2.
pattern CG2 :: CyclicGroup a m

-- | Unidirectional pattern for residues modulo 4.
pattern CG4 :: CyclicGroup a m

-- | Unidirectional pattern for residues modulo p^k for
--   odd prime p.
pattern CGOddPrimePower :: Prime a -> Word -> CyclicGroup a m

-- | Unidirectional pattern for residues modulo 2p^k for
--   odd prime p.
pattern CGDoubleOddPrimePower :: Prime a -> Word -> CyclicGroup a m

-- | Invert sfactorsToCyclicGroup.
--   
--   
--   >>> import Data.Maybe
--   
--   >>> cyclicGroupToSFactors (fromJust (sfactorsToCyclicGroup (sfactors :: SFactors Integer 4)))
--   SFactors {unSFactors = [(Prime 2,2)]}
--   
cyclicGroupToSFactors :: forall a (m :: Nat). Num a => CyclicGroup a m -> SFactors a m

-- | Check whether a multiplicative group of residues, characterized by its
--   modulo, is cyclic and, if yes, return its form.
--   
--   
--   >>> :set -XTypeOperators -XNoStarIsType
--   
--   >>> import GHC.TypeNats
--   
--   >>> sfactorsToCyclicGroup (sfactors :: SFactors Integer 4)
--   Just CG4'
--   
--   >>> sfactorsToCyclicGroup (sfactors :: SFactors Integer (2 * 13 ^ 3))
--   Just (CGDoubleOddPrimePower' (Prime 13) 3)
--   
--   >>> sfactorsToCyclicGroup (sfactors :: SFactors Integer  (4 * 13))
--   Nothing
--   
sfactorsToCyclicGroup :: forall a (m :: Nat). (Eq a, Num a) => SFactors a m -> Maybe (CyclicGroup a m)

-- | Wrapper to hide an unknown type-level natural.
data Some (a :: Nat -> Type)
[Some] :: forall (a :: Nat -> Type) (m :: Nat). a m -> Some a
instance GHC.Classes.Eq (Math.NumberTheory.Moduli.Singleton.CyclicGroup a m)
instance GHC.Classes.Eq (Math.NumberTheory.Moduli.Singleton.SFactors a m)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Math.NumberTheory.Moduli.Singleton.Some (Math.NumberTheory.Moduli.Singleton.CyclicGroup a))
instance GHC.Classes.Ord a => GHC.Classes.Eq (Math.NumberTheory.Moduli.Singleton.Some (Math.NumberTheory.Moduli.Singleton.SFactors a))
instance GHC.Internal.Generics.Generic (Math.NumberTheory.Moduli.Singleton.CyclicGroup a m)
instance GHC.Internal.Generics.Generic (Math.NumberTheory.Moduli.Singleton.SFactors a m)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Math.NumberTheory.Moduli.Singleton.CyclicGroup a m)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Math.NumberTheory.Moduli.Singleton.SFactors a m)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Math.NumberTheory.Moduli.Singleton.Some (Math.NumberTheory.Moduli.Singleton.CyclicGroup a))
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Math.NumberTheory.Moduli.Singleton.Some (Math.NumberTheory.Moduli.Singleton.SFactors a))
instance GHC.Classes.Ord (Math.NumberTheory.Moduli.Singleton.CyclicGroup a m)
instance GHC.Classes.Ord (Math.NumberTheory.Moduli.Singleton.SFactors a m)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Math.NumberTheory.Moduli.Singleton.Some (Math.NumberTheory.Moduli.Singleton.CyclicGroup a))
instance GHC.Classes.Ord a => GHC.Classes.Ord (Math.NumberTheory.Moduli.Singleton.Some (Math.NumberTheory.Moduli.Singleton.SFactors a))
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Math.NumberTheory.Moduli.Singleton.CyclicGroup a m)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Math.NumberTheory.Moduli.Singleton.SFactors a m)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Math.NumberTheory.Moduli.Singleton.Some (Math.NumberTheory.Moduli.Singleton.CyclicGroup a))
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Math.NumberTheory.Moduli.Singleton.Some (Math.NumberTheory.Moduli.Singleton.SFactors a))

-- | Modular square roots and Jacobi symbol.
module Math.NumberTheory.Moduli.Sqrt

-- | List all modular square roots.
--   
--   
--   >>> :set -XDataKinds
--   
--   >>> sqrtsMod sfactors (1 :: Mod 60)
--   [(1 `modulo` 60),(49 `modulo` 60),(41 `modulo` 60),(29 `modulo` 60),(31 `modulo` 60),(19 `modulo` 60),(11 `modulo` 60),(59 `modulo` 60)]
--   
sqrtsMod :: forall (m :: Nat). SFactors Integer m -> Mod m -> [Mod m]

-- | List all square roots modulo a number, the factorisation of which is
--   passed as a second argument.
--   
--   
--   >>> sqrtsModFactorisation 1 (factorise 60)
--   [1,49,41,29,31,19,11,59]
--   
sqrtsModFactorisation :: Integer -> [(Prime Integer, Word)] -> [Integer]

-- | List all square roots modulo the power of a prime.
--   
--   
--   >>> import Data.Maybe
--   
--   >>> import Math.NumberTheory.Primes
--   
--   >>> sqrtsModPrimePower 7 (fromJust (isPrime 3)) 2
--   [4,5]
--   
--   >>> sqrtsModPrimePower 9 (fromJust (isPrime 3)) 3
--   [3,12,21,24,6,15]
--   
sqrtsModPrimePower :: Integer -> Prime Integer -> Word -> [Integer]

-- | List all square roots by prime modulo.
--   
--   
--   >>> import Data.Maybe
--   
--   >>> import Math.NumberTheory.Primes
--   
--   >>> sqrtsModPrime 1 (fromJust (isPrime 5))
--   [1,4]
--   
--   >>> sqrtsModPrime 0 (fromJust (isPrime 5))
--   [0]
--   
--   >>> sqrtsModPrime 2 (fromJust (isPrime 5))
--   []
--   
sqrtsModPrime :: Integer -> Prime Integer -> [Integer]

-- | Represents three possible values of Jacobi symbol.
data JacobiSymbol
MinusOne :: JacobiSymbol
Zero :: JacobiSymbol
One :: JacobiSymbol

-- | Jacobi symbol of two arguments. The lower argument
--   ("denominator") must be odd and positive, this condition is checked.
--   
--   If arguments have a common factor, the result is Zero,
--   otherwise it is MinusOne or One.
--   
--   
--   >>> jacobi 1001 9911 -- arguments have a common factor 11
--   Zero
--   
--   >>> jacobi 1001 9907
--   MinusOne
--   
jacobi :: (Integral a, Bits a) => a -> a -> JacobiSymbol

-- | Convenience function to convert out of a Jacobi symbol
symbolToNum :: Num a => JacobiSymbol -> a

-- | This module exports functions for manipulating Gaussian integers,
--   including computing their prime factorisations.
module Math.NumberTheory.Quadratic.GaussianIntegers

-- | A Gaussian integer is a+bi, where a and b are both integers.
data GaussianInteger
(:+) :: !Integer -> !Integer -> GaussianInteger
[real] :: GaussianInteger -> !Integer
[imag] :: GaussianInteger -> !Integer
infix 6 :+

-- | The imaginary unit, where
--   
--   
--   ι .^ 2 == -1
--   
ι :: GaussianInteger

-- | Conjugate a Gaussian integer.
conjugate :: GaussianInteger -> GaussianInteger

-- | The square of the magnitude of a Gaussian integer.
norm :: GaussianInteger -> Integer

-- | An infinite list of the Gaussian primes. Uses primes in Z to
--   exhaustively generate all Gaussian primes (up to associates), in order
--   of ascending magnitude.
--   
--   
--   >>> take 10 primes
--   [Prime 1+ι,Prime 2+ι,Prime 1+2*ι,Prime 3,Prime 3+2*ι,Prime 2+3*ι,Prime 4+ι,Prime 1+4*ι,Prime 5+2*ι,Prime 2+5*ι]
--   
primes :: Infinite (Prime GaussianInteger)

-- | Find a Gaussian integer whose norm is the given prime number of form
--   4k + 1 using Hermite-Serret algorithm.
--   
--   
--   >>> import Math.NumberTheory.Primes (nextPrime)
--   
--   >>> findPrime (nextPrime 5)
--   Prime 2+ι
--   
findPrime :: Prime Integer -> Prime GaussianInteger
instance GHC.Classes.Eq Math.NumberTheory.Quadratic.GaussianIntegers.GaussianInteger
instance Data.Euclidean.Euclidean Math.NumberTheory.Quadratic.GaussianIntegers.GaussianInteger
instance Data.Euclidean.GcdDomain Math.NumberTheory.Quadratic.GaussianIntegers.GaussianInteger
instance GHC.Internal.Generics.Generic Math.NumberTheory.Quadratic.GaussianIntegers.GaussianInteger
instance Control.DeepSeq.NFData Math.NumberTheory.Quadratic.GaussianIntegers.GaussianInteger
instance GHC.Internal.Num.Num Math.NumberTheory.Quadratic.GaussianIntegers.GaussianInteger
instance GHC.Classes.Ord Math.NumberTheory.Quadratic.GaussianIntegers.GaussianInteger
instance Data.Semiring.Ring Math.NumberTheory.Quadratic.GaussianIntegers.GaussianInteger
instance Data.Semiring.Semiring Math.NumberTheory.Quadratic.GaussianIntegers.GaussianInteger
instance GHC.Internal.Show.Show Math.NumberTheory.Quadratic.GaussianIntegers.GaussianInteger
instance Math.NumberTheory.Primes.UniqueFactorisation Math.NumberTheory.Quadratic.GaussianIntegers.GaussianInteger

-- | This module exports functions for manipulating Eisenstein integers,
--   including computing their prime factorisations.
module Math.NumberTheory.Quadratic.EisensteinIntegers

-- | An Eisenstein integer is a + bω, where a and
--   b are both integers.
data EisensteinInteger
(:+) :: !Integer -> !Integer -> EisensteinInteger
infix 6 :+

-- | The imaginary unit for Eisenstein integers, where
--   
--   
--   ω == (-1/2) + ((sqrt 3)/2)ι == exp(2*pi*ι/3)
--   
--   
--   and ι is the usual imaginary unit with ι² == -1.
ω :: EisensteinInteger

-- | Conjugate a Eisenstein integer.
conjugate :: EisensteinInteger -> EisensteinInteger

-- | The square of the magnitude of a Eisenstein integer.
norm :: EisensteinInteger -> Integer

-- | Produce a list of an EisensteinInteger's associates.
associates :: EisensteinInteger -> [EisensteinInteger]

-- | List of all Eisenstein units, counterclockwise across all sextants,
--   starting with 1.
ids :: [EisensteinInteger]

-- | Find an Eisenstein integer whose norm is the given prime number in the
--   form 3k + 1.
--   
--   
--   >>> import Math.NumberTheory.Primes (nextPrime)
--   
--   >>> findPrime (nextPrime 7)
--   Prime 3+2*ω
--   
findPrime :: Prime Integer -> Prime EisensteinInteger

-- | An infinite list of Eisenstein primes. Uses primes in Z to
--   exhaustively generate all Eisenstein primes in order of ascending
--   norm.
--   
--   
--   
- Every prime is in the first sextant, so the list contains no
--   associates.
--   
- Eisenstein primes from the whole complex plane can be generated by
--   applying associates to each prime in this list.
--   
--   
--   
--   >>> take 10 primes
--   [Prime 2+ω,Prime 2,Prime 3+2*ω,Prime 3+ω,Prime 4+3*ω,Prime 4+ω,Prime 5+3*ω,Prime 5+2*ω,Prime 5,Prime 6+5*ω]
--   
primes :: Infinite (Prime EisensteinInteger)
instance GHC.Classes.Eq Math.NumberTheory.Quadratic.EisensteinIntegers.EisensteinInteger
instance Data.Euclidean.Euclidean Math.NumberTheory.Quadratic.EisensteinIntegers.EisensteinInteger
instance Data.Euclidean.GcdDomain Math.NumberTheory.Quadratic.EisensteinIntegers.EisensteinInteger
instance GHC.Internal.Generics.Generic Math.NumberTheory.Quadratic.EisensteinIntegers.EisensteinInteger
instance Control.DeepSeq.NFData Math.NumberTheory.Quadratic.EisensteinIntegers.EisensteinInteger
instance GHC.Internal.Num.Num Math.NumberTheory.Quadratic.EisensteinIntegers.EisensteinInteger
instance GHC.Classes.Ord Math.NumberTheory.Quadratic.EisensteinIntegers.EisensteinInteger
instance Data.Semiring.Ring Math.NumberTheory.Quadratic.EisensteinIntegers.EisensteinInteger
instance Data.Semiring.Semiring Math.NumberTheory.Quadratic.EisensteinIntegers.EisensteinInteger
instance GHC.Internal.Show.Show Math.NumberTheory.Quadratic.EisensteinIntegers.EisensteinInteger
instance Math.NumberTheory.Primes.UniqueFactorisation Math.NumberTheory.Quadratic.EisensteinIntegers.EisensteinInteger

-- | Polynomial modular equations.
module Math.NumberTheory.Moduli.Equations

-- | Find all solutions of ax + b ≡ 0 (mod m).
--   
--   
--   >>> :set -XDataKinds
--   
--   >>> solveLinear (6 :: Mod 10) 4 -- solving 6x + 4 ≡ 0 (mod 10)
--   [(1 `modulo` 10),(6 `modulo` 10)]
--   
solveLinear :: forall (m :: Nat). KnownNat m => Mod m -> Mod m -> [Mod m]

-- | Find all solutions of ax² + bx + c ≡ 0 (mod m).
--   
--   
--   >>> :set -XDataKinds
--   
--   >>> solveQuadratic sfactors (1 :: Mod 32) 0 (-17) -- solving x² - 17 ≡ 0 (mod 32)
--   [(9 `modulo` 32),(25 `modulo` 32),(7 `modulo` 32),(23 `modulo` 32)]
--   
solveQuadratic :: forall (m :: Nat). SFactors Integer m -> Mod m -> Mod m -> Mod m -> [Mod m]

-- | Multiplicative groups of integers modulo m.
module Math.NumberTheory.Moduli.Multiplicative

-- | This type represents elements of the multiplicative group mod m, i.e.
--   those elements which are coprime to m. Use isMultElement to
--   construct.
data MultMod (m :: Nat)

-- | Unwrap a residue.
multElement :: MultMod m -> Mod m

-- | Attempt to construct a multiplicative group element.
isMultElement :: forall (m :: Nat). KnownNat m => Mod m -> Maybe (MultMod m)

-- | For elements of the multiplicative group, we can safely perform the
--   inverse without needing to worry about failure.
invertGroup :: forall (m :: Nat). KnownNat m => MultMod m -> MultMod m

-- | PrimitiveRoot m is a type which is only inhabited by
--   primitive roots of m.
data PrimitiveRoot (m :: Nat)

-- | Extract primitive root value.
unPrimitiveRoot :: PrimitiveRoot m -> MultMod m

-- | Check whether a given modular residue is a primitive root.
--   
--   
--   >>> :set -XDataKinds
--   
--   >>> import Data.Maybe
--   
--   >>> isPrimitiveRoot (fromJust cyclicGroup) (1 :: Mod 13)
--   Nothing
--   
--   >>> isPrimitiveRoot (fromJust cyclicGroup) (2 :: Mod 13)
--   Just (PrimitiveRoot {unPrimitiveRoot = MultMod {multElement = (2 `modulo` 13)}})
--   
isPrimitiveRoot :: forall a (m :: Nat). (Integral a, UniqueFactorisation a) => CyclicGroup a m -> Mod m -> Maybe (PrimitiveRoot m)

-- | Computes the discrete logarithm. Currently uses a combination of the
--   baby-step giant-step method and Pollard's rho algorithm, with Bach
--   reduction.
--   
--   
--   >>> :set -XDataKinds
--   
--   >>> import Data.Maybe
--   
--   >>> let cg = fromJust cyclicGroup :: CyclicGroup Integer 13
--   
--   >>> let rt = fromJust (isPrimitiveRoot cg 2)
--   
--   >>> let x  = fromJust (isMultElement 11)
--   
--   >>> discreteLogarithm cg rt x
--   7
--   
discreteLogarithm :: forall (m :: Nat). CyclicGroup Integer m -> PrimitiveRoot m -> MultMod m -> Natural
instance GHC.Internal.TypeNats.KnownNat m => GHC.Internal.Enum.Bounded (Math.NumberTheory.Moduli.Multiplicative.MultMod m)
instance GHC.Classes.Eq (Math.NumberTheory.Moduli.Multiplicative.MultMod m)
instance GHC.Classes.Eq (Math.NumberTheory.Moduli.Multiplicative.PrimitiveRoot m)
instance GHC.Internal.TypeNats.KnownNat m => GHC.Internal.Base.Monoid (Math.NumberTheory.Moduli.Multiplicative.MultMod m)
instance GHC.Classes.Ord (Math.NumberTheory.Moduli.Multiplicative.MultMod m)
instance GHC.Internal.TypeNats.KnownNat m => GHC.Internal.Base.Semigroup (Math.NumberTheory.Moduli.Multiplicative.MultMod m)
instance GHC.Internal.Show.Show (Math.NumberTheory.Moduli.Multiplicative.MultMod m)
instance GHC.Internal.Show.Show (Math.NumberTheory.Moduli.Multiplicative.PrimitiveRoot m)

-- | Safe modular arithmetic with modulo on type level.
module Math.NumberTheory.Moduli.Class

-- | This data type represents integers modulo m, equipped with
--   useful instances.
--   
--   For example, 3 :: Mod 10 stands for the class of integers
--   congruent to <math>
--   
--   
--   >>> :set -XDataKinds
--   
--   >>> 3 + 8 :: Mod 10 -- 3 + 8 = 11 ≡ 1 (mod 10)
--   1
--   
--   
--   Note: Mod 0 has no inhabitants, eventhough <math>
--   is technically isomorphic to <math>.
data Mod (m :: Nat)

-- | The canonical representative of the residue class, always between 0
--   and m-1 inclusively.
getVal :: forall (m :: Nat). Mod m -> Integer

-- | The canonical representative of the residue class, always between 0
--   and m-1 inclusively.
getNatVal :: forall (m :: Nat). Mod m -> Natural

-- | Linking type and value levels: extract modulo m as a value.
getMod :: forall (m :: Nat). KnownNat m => Mod m -> Integer

-- | Linking type and value levels: extract modulo m as a value.
getNatMod :: forall (m :: Nat). KnownNat m => Mod m -> Natural

-- | If an argument is coprime with the modulus, return its modular
--   inverse. Otherwise return Nothing.
--   
--   
--   >>> :set -XDataKinds
--   
--   >>> invertMod 3 :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
--   Just 7
--   
--   >>> invertMod 4 :: Mod 10 -- 4 and 10 are not coprime
--   Nothing
--   
invertMod :: forall (m :: Nat). KnownNat m => Mod m -> Maybe (Mod m)

-- | Synonym of (^%).
powMod :: forall (m :: Nat) a. (KnownNat m, Integral a) => Mod m -> a -> Mod m

-- | Drop-in replacement for ^ with much better performance.
--   Negative powers are allowed, but may throw DivideByZero, if an
--   argument is not coprime with the modulus.
--   
--   
--   >>> :set -XDataKinds
--   
--   >>> 3 ^% 4 :: Mod 10    -- 3 ^ 4 = 81 ≡ 1 (mod 10)
--   1
--   
--   >>> 3 ^% (-1) :: Mod 10 -- 3 * 7 = 21 ≡ 1 (mod 10)
--   7
--   
--   >>> 4 ^% (-1) :: Mod 10 -- 4 and 10 are not coprime
--   (*** Exception: divide by zero
--   
(^%) :: forall (m :: Nat) a. (KnownNat m, Integral a) => Mod m -> a -> Mod m
infixr 8 ^%

-- | This type represents elements of the multiplicative group mod m, i.e.
--   those elements which are coprime to m. Use isMultElement to
--   construct.
data MultMod (m :: Nat)

-- | Unwrap a residue.
multElement :: MultMod m -> Mod m

-- | Attempt to construct a multiplicative group element.
isMultElement :: forall (m :: Nat). KnownNat m => Mod m -> Maybe (MultMod m)

-- | For elements of the multiplicative group, we can safely perform the
--   inverse without needing to worry about failure.
invertGroup :: forall (m :: Nat). KnownNat m => MultMod m -> MultMod m

-- | This type represents residues with unknown modulo and rational
--   numbers. One can freely combine them in arithmetic expressions, but
--   each operation will spend time on modulo's recalculation:
--   
--   
--   >>> 2 `modulo` 10 + 4 `modulo` 15
--   (1 `modulo` 5)
--   
--   >>> (2 `modulo` 10) * (4 `modulo` 15)
--   (3 `modulo` 5)
--   
--   >>> import Data.Ratio
--   
--   >>> 2 `modulo` 10 + fromRational (3 % 7)
--   (1 `modulo` 10)
--   
--   >>> 2 `modulo` 10 * fromRational (3 % 7)
--   (8 `modulo` 10)
--   
--   
--   If performance is crucial, it is recommended to extract Mod m
--   for further processing by pattern matching. E. g.,
--   
--   
--   case modulo n m of
--     SomeMod k -> process k -- Here k has type Mod m
--     InfMod{}  -> error "impossible"
--   
data SomeMod
[SomeMod] :: forall (m :: Nat). KnownNat m => Mod m -> SomeMod
[InfMod] :: Rational -> SomeMod

-- | Create modular value by representative of residue class and modulo.
--   One can use the result either directly (via functions from Num
--   and Fractional), or deconstruct it by pattern matching. Note
--   that modulo never returns InfMod.
modulo :: Integer -> Natural -> SomeMod
infixl 7 `modulo`

-- | Computes the inverse value, if it exists.
--   
--   
--   >>> invertSomeMod (3 `modulo` 10) -- because 3 * 7 = 1 :: Mod 10
--   Just (7 `modulo` 10)
--   
--   >>> invertSomeMod (4 `modulo` 10)
--   Nothing
--   
--   >>> import Data.Ratio
--   
--   >>> invertSomeMod (fromRational (2 % 5))
--   Just 5 % 2
--   
invertSomeMod :: SomeMod -> Maybe SomeMod

-- | Drop-in replacement for ^, with much better performance. When
--   -O is enabled, there is a rewrite rule, which specialises ^ to
--   powSomeMod.
--   
--   
--   >>> powSomeMod (3 `modulo` 10) 4
--   (1 `modulo` 10)
--   
powSomeMod :: Integral a => SomeMod -> a -> SomeMod

-- | This class gives the integer associated with a type-level natural.
--   There are instances of the class for every concrete literal: 0, 1, 2,
--   etc.
class KnownNat (n :: Nat)

-- | Miscellaneous functions related to modular arithmetic.
module Math.NumberTheory.Moduli

-- | Cubic symbol of two Eisenstein Integers.
module Math.NumberTheory.Moduli.Cbrt

-- | Represents the cubic residue character It is either 0,
--   ω, ω² or 1.
data CubicSymbol
Zero :: CubicSymbol
Omega :: CubicSymbol
OmegaSquare :: CubicSymbol
One :: CubicSymbol

-- | Cubic symbol of two Eisenstein Integers. The first argument is
--   the numerator and the second argument is the denominator. The latter
--   must be coprime to 3. This condition is checked.
--   
--   If the arguments have a common factor, the result is Zero,
--   otherwise it is either Omega, OmegaSquare or One.
--   
--   
--   >>> cubicSymbol (45 + 23*ω) (11 - 30*ω)
--   0
--   
--   >>> cubicSymbol (31 - ω) (1 +10*ω)
--   ω
--   
cubicSymbol :: EisensteinInteger -> EisensteinInteger -> CubicSymbol

-- | Converts a cubic symbol to an Eisenstein Integer.
symbolToNum :: CubicSymbol -> EisensteinInteger
instance GHC.Classes.Eq Math.NumberTheory.Moduli.Cbrt.CubicSymbol
instance GHC.Internal.Base.Semigroup Math.NumberTheory.Moduli.Cbrt.CubicSymbol
instance GHC.Internal.Show.Show Math.NumberTheory.Moduli.Cbrt.CubicSymbol

module Math.NumberTheory.Diophantine

-- | Finds all primitive solutions (x,y) to the diophantine equation | x^2
--   + d*y^2 = m | when 1 <= d < m and gcd(d,m)=1 | Given m is square
--   free these are all the positive integer solutions
cornacchiaPrimitive :: Integer -> Integer -> [(Integer, Integer)]

-- | Finds all positive integer solutions (x,y) to the | diophantine
--   equation: | x^2 + d*y^2 = m | when 1 <= d < m and gcd(d,m)=1
cornacchia :: Integer -> Integer -> [(Integer, Integer)]

-- | N-free number generation.
module Math.NumberTheory.ArithmeticFunctions.NFreedom

-- | For a given nonnegative integer power n, generate all
--   n-free numbers in ascending order, starting at 1.
--   
--   When n is 0 or 1, the resulting list is
--   [1].
nFrees :: (Integral a, Bits a, UniqueFactorisation a, Enum (Prime a)) => Word -> [a]

-- | Generate n-free numbers in a block starting at a certain
--   value. The length of the list is determined by the value passed in as
--   the third argument. It will be lesser than or equal to this value.
--   
--   This function should not be used with a negative lower bound. If it
--   is, the result is undefined.
--   
--   The block length cannot exceed maxBound :: Int, this
--   precondition is not checked.
--   
--   As with nFrees, passing n = 0, 1 results in an empty
--   list.
nFreesBlock :: (Integral a, Bits a, UniqueFactorisation a, Enum (Prime a)) => Word -> a -> Word -> [a]

-- | Evaluate the isNFree function over a block. Value at
--   0, if zero falls into block, is undefined.
--   
--   This function should **not** be used with a negative lower
--   bound. If it is, the result is undefined. Furthermore, do not:
--   
--   
--   
- use a block length greater than maxBound :: Int.
--   
- use a power that is either of 0, 1.
--   
--   
--   None of these preconditions are checked, and if any occurs, the result
--   is undefined, if the function terminates.
--   
--   
--   >>> sieveBlockNFree 2 1 10
--   [True,True,True,False,True,True,True,False,False,True]
--   
sieveBlockNFree :: (Integral a, Enum (Prime a), Bits a, UniqueFactorisation a) => Word -> a -> Word -> Vector Bool

-- | Values of Möbius function.
module Math.NumberTheory.ArithmeticFunctions.Moebius

-- | Represents three possible values of Möbius function.
data Moebius

-- | 
--   
- 1
--   
MoebiusN :: Moebius

-- | 0
MoebiusZ :: Moebius

-- | 1
MoebiusP :: Moebius

-- | Convert to any numeric type.
runMoebius :: Num a => Moebius -> a

-- | Evaluate the Möbius function over a block. Value of f at 0,
--   if zero falls into block, is undefined.
--   
--   Based on the sieving algorithm from p. 3 of Computations of the
--   Mertens function and improved bounds on the Mertens conjecture by
--   G. Hurst. It is approximately 5x faster than sieveBlockUnboxed.
--   
--   
--   >>> sieveBlockMoebius 1 10
--   [MoebiusP,MoebiusN,MoebiusN,MoebiusZ,MoebiusN,MoebiusP,MoebiusN,MoebiusZ,MoebiusZ,MoebiusP]
--   
sieveBlockMoebius :: Word -> Word -> Vector Moebius
instance GHC.Classes.Eq Math.NumberTheory.ArithmeticFunctions.Moebius.Moebius
instance Data.Vector.Generic.Mutable.Base.MVector Data.Vector.Unboxed.Base.MVector Math.NumberTheory.ArithmeticFunctions.Moebius.Moebius
instance GHC.Internal.Base.Monoid Math.NumberTheory.ArithmeticFunctions.Moebius.Moebius
instance GHC.Classes.Ord Math.NumberTheory.ArithmeticFunctions.Moebius.Moebius
instance GHC.Internal.Base.Semigroup Math.NumberTheory.ArithmeticFunctions.Moebius.Moebius
instance GHC.Internal.Show.Show Math.NumberTheory.ArithmeticFunctions.Moebius.Moebius
instance Data.Vector.Unboxed.Base.Unbox Math.NumberTheory.ArithmeticFunctions.Moebius.Moebius
instance Data.Vector.Generic.Base.Vector Data.Vector.Unboxed.Base.Vector Math.NumberTheory.ArithmeticFunctions.Moebius.Moebius

-- | This module provides an interface for defining and manipulating
--   arithmetic functions. It also defines several most widespreaded
--   arithmetic functions.
module Math.NumberTheory.ArithmeticFunctions

-- | A typical arithmetic function operates on the canonical factorisation
--   of a number into prime's powers and consists of two rules. The first
--   one determines the values of the function on the powers of primes. The
--   second one determines how to combine these values into final result.
--   
--   In the following definition the first argument is the function on
--   prime's powers, the monoid instance determines a rule of combination
--   (typically Product or Sum), and the second argument is
--   convenient for unwrapping (typically, getProduct or
--   getSum).
data ArithmeticFunction n a
[ArithmeticFunction] :: forall m n a. Monoid m => (Prime n -> Word -> m) -> (m -> a) -> ArithmeticFunction n a

-- | Convert to a function. The value on 0 is undefined.
runFunction :: UniqueFactorisation n => ArithmeticFunction n a -> n -> a

-- | Convert to a function on prime factorisation.
runFunctionOnFactors :: ArithmeticFunction n a -> [(Prime n, Word)] -> a

-- | See divisorsToA.
divisorsTo :: (UniqueFactorisation n, Integral n) => n -> n -> Set n

-- | Represents three possible values of Möbius function.
data Moebius

-- | 
--   
- 1
--   
MoebiusN :: Moebius

-- | 0
MoebiusZ :: Moebius

-- | 1
MoebiusP :: Moebius

-- | For a given nonnegative integer power n, generate all
--   n-free numbers in ascending order, starting at 1.
--   
--   When n is 0 or 1, the resulting list is
--   [1].
nFrees :: (Integral a, Bits a, UniqueFactorisation a, Enum (Prime a)) => Word -> [a]

-- | Generate n-free numbers in a block starting at a certain
--   value. The length of the list is determined by the value passed in as
--   the third argument. It will be lesser than or equal to this value.
--   
--   This function should not be used with a negative lower bound. If it
--   is, the result is undefined.
--   
--   The block length cannot exceed maxBound :: Int, this
--   precondition is not checked.
--   
--   As with nFrees, passing n = 0, 1 results in an empty
--   list.
nFreesBlock :: (Integral a, Bits a, UniqueFactorisation a, Enum (Prime a)) => Word -> a -> Word -> [a]

-- | Convert to any numeric type.
runMoebius :: Num a => Moebius -> a

-- | See totientA.
totient :: UniqueFactorisation n => n -> n

-- | See divisorsA.
divisors :: (UniqueFactorisation n, Ord n) => n -> Set n

-- | The set of all (positive) divisors of an argument.
divisorsA :: (Ord n, Num n) => ArithmeticFunction n (Set n)

-- | See divisorsListA.
divisorsList :: UniqueFactorisation n => n -> [n]

-- | The unsorted list of all (positive) divisors of an argument, produced
--   in lazy fashion.
divisorsListA :: Num n => ArithmeticFunction n [n]

-- | See divisorsSmallA.
divisorsSmall :: Int -> IntSet

-- | Same as divisors, but with better performance on cost of type
--   restriction.
divisorsSmallA :: ArithmeticFunction Int IntSet

-- | The set of all (positive) divisors up to an inclusive bound.
divisorsToA :: (UniqueFactorisation n, Integral n) => n -> ArithmeticFunction n (Set n)

-- | Create a multiplicative function from the function on prime's powers.
--   See examples below.
multiplicative :: Num a => (Prime n -> Word -> a) -> ArithmeticFunction n a

-- | Synonym for tau.
--   
--   
--   >>> map divisorCount [1..10]
--   [1,2,2,3,2,4,2,4,3,4]
--   
divisorCount :: (UniqueFactorisation n, Num a) => n -> a

-- | See tauA.
tau :: (UniqueFactorisation n, Num a) => n -> a

-- | The number of (positive) divisors of an argument.
--   
--   
--   tauA = multiplicative (\_ k -> k + 1)
--   
tauA :: Num a => ArithmeticFunction n a

-- | See sigmaA.
sigma :: (UniqueFactorisation n, Integral n, Num a, GcdDomain a) => Word -> n -> a

-- | The sum of the k-th powers of (positive) divisors of an
--   argument.
--   
--   
--   sigmaA = multiplicative (\p k -> sum $ map (p ^) [0..k])
--   sigmaA 0 = tauA
--   
sigmaA :: (Integral n, Num a, GcdDomain a) => Word -> ArithmeticFunction n a

-- | Calculates the totient of a positive number n, i.e. the
--   number of k with 1 <= k <= n and
--   gcd n k == 1, in other words, the order of the group
--   of units in ℤ/(n).
totientA :: Num n => ArithmeticFunction n n

-- | See jordanA.
jordan :: UniqueFactorisation n => Word -> n -> n

-- | Calculates the k-th Jordan function of an argument.
--   
--   
--   jordanA 1 = totientA
--   
jordanA :: Num n => Word -> ArithmeticFunction n n

-- | See ramanujanA.
ramanujan :: Integer -> Integer

-- | Calculates the Ramanujan tau function of a positive number
--   n, using formulas given here
ramanujanA :: ArithmeticFunction Integer Integer

-- | See moebiusA.
moebius :: UniqueFactorisation n => n -> Moebius

-- | Calculates the Möbius function of an argument.
moebiusA :: ArithmeticFunction n Moebius

-- | See liouvilleA.
liouville :: (UniqueFactorisation n, Num a) => n -> a

-- | Calculates the Liouville function of an argument.
liouvilleA :: Num a => ArithmeticFunction n a

-- | Create an additive function from the function on prime's powers. See
--   examples below.
additive :: Num a => (Prime n -> Word -> a) -> ArithmeticFunction n a

-- | See smallOmegaA.
smallOmega :: (UniqueFactorisation n, Num a) => n -> a

-- | Number of distinct prime factors.
--   
--   
--   smallOmegaA = additive (\_ _ -> 1)
--   
smallOmegaA :: Num a => ArithmeticFunction n a

-- | See bigOmegaA.
bigOmega :: UniqueFactorisation n => n -> Word

-- | Number of prime factors, counted with multiplicity.
--   
--   
--   bigOmegaA = additive (\_ k -> k)
--   
bigOmegaA :: ArithmeticFunction n Word

-- | See carmichaelA.
carmichael :: (UniqueFactorisation n, Integral n) => n -> n

-- | Calculates the Carmichael function for a positive integer, that is,
--   the (smallest) exponent of the group of units in ℤ/(n).
carmichaelA :: Integral n => ArithmeticFunction n n

-- | See expMangoldtA.
expMangoldt :: UniqueFactorisation n => n -> n

-- | The exponent of von Mangoldt function. Use log expMangoldtA
--   to recover von Mangoldt function itself.
expMangoldtA :: Num n => ArithmeticFunction n n

-- | See isNFreeA.
isNFree :: UniqueFactorisation n => Word -> n -> Bool

-- | Check if an integer is n-free. An integer x is
--   n-free if in its factorisation into prime factors, no factor
--   has an exponent larger than or equal to n.
isNFreeA :: Word -> ArithmeticFunction n Bool

-- | Implementation and enumeration of Dirichlet characters.
module Math.NumberTheory.DirichletCharacters

-- | Similar to Maybe, but with different Semigroup and Monoid instances.
type OrZero a = Ap Maybe a

-- | Ap Nothing
pattern Zero :: OrZero a

-- | Ap (Just x)
pattern NonZero :: a -> OrZero a

-- | Interpret an OrZero as a number, taking the Zero case to
--   be 0.
orZeroToNum :: Num a => (b -> a) -> OrZero b -> a

-- | A Dirichlet character mod <math> is a group homomorphism from
--   <math> to <math>, represented abstractly by
--   DirichletCharacter. In particular, they take values at roots of
--   unity and can be evaluated using eval. A Dirichlet character
--   can be extended to a completely multiplicative function on
--   <math> by assigning the value 0 for <math> sharing a
--   common factor with <math>, using evalGeneral.
--   
--   There are finitely many possible Dirichlet characters for a given
--   modulus, in particular there are <math> characters modulo
--   <math>, where <math> refers to Euler's totient
--   function. This gives rise to Enum and Bounded instances.
data DirichletCharacter (n :: Nat)

-- | Give the dirichlet character from its number. Inverse of
--   characterNumber.
indexToChar :: forall (n :: Nat). KnownNat n => Natural -> DirichletCharacter n

-- | Give a collection of dirichlet characters from their numbers. This may
--   be more efficient than indexToChar for multiple characters, as
--   it prevents some internal recalculations.
indicesToChars :: forall (n :: Nat) f. (KnownNat n, Functor f) => f Natural -> f (DirichletCharacter n)

-- | We have a (non-canonical) enumeration of dirichlet characters.
characterNumber :: forall (n :: Nat). DirichletCharacter n -> Integer

-- | List all characters for the modulus. This is preferred to using
--   [minBound..maxBound].
allChars :: forall (n :: Nat). KnownNat n => [DirichletCharacter n]

-- | Attempt to construct a character from its table of values. An inverse
--   to evalAll, defined only on its image.
fromTable :: forall (n :: Nat). KnownNat n => Vector (OrZero RootOfUnity) -> Maybe (DirichletCharacter n)

-- | For elements of the multiplicative group <math>, a Dirichlet
--   character evaluates to a root of unity.
eval :: forall (n :: Nat). DirichletCharacter n -> MultMod n -> RootOfUnity

-- | A character can evaluate to a root of unity or zero: represented by
--   Nothing.
evalGeneral :: forall (n :: Nat). KnownNat n => DirichletCharacter n -> Mod n -> OrZero RootOfUnity

-- | In general, evaluating a DirichletCharacter at a point involves
--   solving the discrete logarithm problem, which can be hard: the
--   implementations here are around O(sqrt n). However, evaluating a
--   dirichlet character at every point amounts to solving the discrete
--   logarithm problem at every point also, which can be done together in
--   O(n) time, better than using a complex algorithm at each point
--   separately. Thus, if a large number of evaluations of a dirichlet
--   character are required, evalAll will be better than
--   evalGeneral, since computations can be shared.
evalAll :: forall (n :: Nat). KnownNat n => DirichletCharacter n -> Vector (OrZero RootOfUnity)

-- | Give the principal character for this modulus: a principal character
--   mod <math> is 1 for <math> coprime to <math>, and 0
--   otherwise.
principalChar :: forall (n :: Nat). KnownNat n => DirichletCharacter n

-- | Test if a given Dirichlet character is prinicpal for its modulus: a
--   principal character mod <math> is 1 for <math> coprime to
--   <math>, and 0 otherwise.
isPrincipal :: forall (n :: Nat). DirichletCharacter n -> Bool

-- | Get the order of the Dirichlet Character.
orderChar :: forall (n :: Nat). DirichletCharacter n -> Integer

-- | A Dirichlet character is real if it is real-valued.
data RealCharacter (n :: Nat)

-- | Test if a given DirichletCharacter is real, and if so give a
--   RealCharacter.
isRealCharacter :: forall (n :: Nat). DirichletCharacter n -> Maybe (RealCharacter n)

-- | Extract the character itself from a RealCharacter.
getRealChar :: RealCharacter n -> DirichletCharacter n

-- | Evaluate a real Dirichlet character, which can only take values
--   <math>.
toRealFunction :: forall (n :: Nat). KnownNat n => RealCharacter n -> Mod n -> Int

-- | The Jacobi symbol gives a real Dirichlet character for odd
--   moduli.
jacobiCharacter :: forall (n :: Nat). KnownNat n => Maybe (RealCharacter n)

-- | A Dirichlet character is primitive if cannot be induced from
--   any character with strictly smaller modulus.
data PrimitiveCharacter (n :: Nat)

-- | Test if a Dirichlet character is primitive.
isPrimitive :: forall (n :: Nat). DirichletCharacter n -> Maybe (PrimitiveCharacter n)

-- | Extract the character itself from a PrimitiveCharacter.
getPrimitiveChar :: PrimitiveCharacter n -> DirichletCharacter n

-- | Induce a Dirichlet character to a higher modulus. If <math>,
--   then <math> can be reduced to <math>. Thus, the
--   multiplicative function on <math> induces a multiplicative
--   function on <math>.
--   
--   
--   >>> :set -XTypeApplications -XDataKinds
--   
--   >>> chi = indexToChar 5 :: DirichletCharacter 45
--   
--   >>> chi2 = induced @135 chi :: Maybe (DirichletCharacter 135)
--   
induced :: forall (n :: Nat) (d :: Nat). (KnownNat d, KnownNat n) => DirichletCharacter d -> Maybe (DirichletCharacter n)

-- | This function also provides access to the new modulus on type level,
--   with a KnownNat instance
makePrimitive :: forall (n :: Nat). DirichletCharacter n -> WithNat PrimitiveCharacter

-- | Wrapper to hide an unknown type-level natural.
data WithNat (a :: Nat -> Type)
[WithNat] :: forall (m :: Nat) (a :: Nat -> Type). KnownNat m => a m -> WithNat a

-- | A representation of roots of unity: complex numbers
--   <math> for which there is <math> such that <math>.
newtype RootOfUnity
RootOfUnity :: Rational -> RootOfUnity

-- | Every root of unity can be expressed as <math> for some rational
--   <math> satisfying <math>, this function extracts it.
[fromRootOfUnity] :: RootOfUnity -> Rational

-- | Given a rational <math>, produce the root of unity <math>.
toRootOfUnity :: Rational -> RootOfUnity

-- | Convert a root of unity into an inexact complex number. Due to
--   floating point inaccuracies, it is recommended to avoid use of this
--   until the end of a calculation. Alternatively, with the
--   cyclotomic package, one can use polarRat 1 .
--   fromRootOfUnity to convert to a cyclotomic number.
toComplex :: Floating a => RootOfUnity -> Complex a

-- | Test if the internal DirichletCharacter structure is valid.
validChar :: forall (n :: Nat). KnownNat n => DirichletCharacter n -> Bool
instance GHC.Internal.TypeNats.KnownNat n => GHC.Internal.Enum.Bounded (Math.NumberTheory.DirichletCharacters.DirichletCharacter n)
instance GHC.Internal.TypeNats.KnownNat n => GHC.Internal.Enum.Enum (Math.NumberTheory.DirichletCharacters.DirichletCharacter n)
instance GHC.Classes.Eq (Math.NumberTheory.DirichletCharacters.DirichletCharacter n)
instance GHC.Classes.Eq Math.NumberTheory.DirichletCharacters.DirichletFactor
instance GHC.Classes.Eq (Math.NumberTheory.DirichletCharacters.PrimitiveCharacter n)
instance GHC.Classes.Eq (Math.NumberTheory.DirichletCharacters.RealCharacter n)
instance GHC.Internal.TypeNats.KnownNat n => GHC.Internal.Base.Monoid (Math.NumberTheory.DirichletCharacters.DirichletCharacter n)
instance GHC.Internal.Base.Semigroup (Math.NumberTheory.DirichletCharacters.DirichletCharacter n)

-- | Bulk evaluation of arithmetic functions over continuous intervals
--   without factorisation.
module Math.NumberTheory.ArithmeticFunctions.SieveBlock

-- | runFunctionOverBlock f x l evaluates
--   an arithmetic function for integers between x and
--   x+l-1 and returns a vector of length l. It
--   completely avoids factorisation, so it is asymptotically faster than
--   pointwise evaluation of f.
--   
--   Value of f at 0, if zero falls into block, is undefined.
--   
--   Beware that for underlying non-commutative monoids the results may
--   potentially differ from pointwise application via runFunction.
--   
--   This is a thin wrapper over sieveBlock, read more details
--   there.
--   
--   
--   >>> import Math.NumberTheory.ArithmeticFunctions
--   
--   >>> runFunctionOverBlock carmichaelA 1 10
--   [1,1,2,2,4,2,6,2,6,4]
--   
runFunctionOverBlock :: ArithmeticFunction Word a -> Word -> Word -> Vector a

-- | A record, which specifies a function to evaluate over a block.
--   
--   For example, here is a configuration for the totient function:
--   
--   
--   SieveBlockConfig
--     { sbcEmpty                = 1
--     , sbcFunctionOnPrimePower = \p a -> (unPrime p - 1) * unPrime p ^ (a - 1)
--     , sbcAppend               = (*)
--     }
--   
data SieveBlockConfig a
SieveBlockConfig :: a -> (Prime Word -> Word -> a) -> (a -> a -> a) -> SieveBlockConfig a

-- | value of a function on 1
[sbcEmpty] :: SieveBlockConfig a -> a

-- | how to evaluate a function on prime powers
[sbcFunctionOnPrimePower] :: SieveBlockConfig a -> Prime Word -> Word -> a

-- | how to combine values of a function on coprime arguments
[sbcAppend] :: SieveBlockConfig a -> a -> a -> a

-- | Create a config for a multiplicative function from its definition on
--   prime powers.
multiplicativeSieveBlockConfig :: Num a => (Prime Word -> Word -> a) -> SieveBlockConfig a

-- | Create a config for an additive function from its definition on prime
--   powers.
additiveSieveBlockConfig :: Num a => (Prime Word -> Word -> a) -> SieveBlockConfig a

-- | Evaluate a function over a block in accordance to provided
--   configuration. Value of f at 0, if zero falls into block, is
--   undefined.
--   
--   Based on Algorithm M of Parity of the number of primes in a given
--   interval and algorithms of the sublinear summation by A. V.
--   Lelechenko. See Lemma 2 on p. 5 on its algorithmic complexity. For the
--   majority of use-cases its time complexity is O(x^(1+ε)).
--   
--   For example, following code lists smallest prime factors:
--   
--   
--   >>> sieveBlock (SieveBlockConfig maxBound (\p _ -> unPrime p) min) 2 10 :: Data.Vector.Vector Word
--   [2,3,2,5,2,7,2,3,2,11]
--   
--   
--   And this is how to factorise all numbers in a block:
--   
--   
--   >>> sieveBlock (SieveBlockConfig [] (\p k -> [(unPrime p, k)]) (++)) 2 10 :: Data.Vector.Vector [(Word, Word)]
--   [[(2,1)],[(3,1)],[(2,2)],[(5,1)],[(2,1),(3,1)],[(7,1)],[(2,3)],[(3,2)],[(2,1),(5,1)],[(11,1)]]
--   
sieveBlock :: Vector v a => SieveBlockConfig a -> Word -> Word -> v a

-- | This is sieveBlock specialized to unboxed vectors.
--   
--   
--   >>> sieveBlockUnboxed (SieveBlockConfig 1 (\_ a -> a + 1) (*)) 1 10
--   [1,2,2,3,2,4,2,4,3,4]
--   
sieveBlockUnboxed :: Unbox a => SieveBlockConfig a -> Word -> Word -> Vector a

-- | Evaluate the Möbius function over a block. Value of f at 0,
--   if zero falls into block, is undefined.
--   
--   Based on the sieving algorithm from p. 3 of Computations of the
--   Mertens function and improved bounds on the Mertens conjecture by
--   G. Hurst. It is approximately 5x faster than sieveBlockUnboxed.
--   
--   
--   >>> sieveBlockMoebius 1 10
--   [MoebiusP,MoebiusN,MoebiusN,MoebiusZ,MoebiusN,MoebiusP,MoebiusN,MoebiusZ,MoebiusZ,MoebiusP]
--   
sieveBlockMoebius :: Word -> Word -> Vector Moebius

-- | Values of Mertens function.
module Math.NumberTheory.ArithmeticFunctions.Mertens

-- | Compute individual values of Mertens function in O(n^(2/3)) time and
--   space.
--   
--   
--   >>> map (mertens . (10 ^)) [0..9]
--   [1,-1,1,2,-23,-48,212,1037,1928,-222]
--   
--   
--   The implementation follows Theorem 3.1 from Computations of the
--   Mertens function and improved bounds on the Mertens conjecture by
--   G. Hurst, excluding segmentation of sieves.
mertens :: Word -> Int

-- | Computing inverses of multiplicative functions. The implementation is
--   based on Computing the Inverses, their Power Sums, and Extrema for
--   Euler’s Totient and Other Multiplicative Functions by M. A.
--   Alekseyev.
module Math.NumberTheory.ArithmeticFunctions.Inverse

-- | The inverse for totient function.
--   
--   The return value is parameterized by a Semiring, which allows
--   various applications by providing different (multiplicative)
--   embeddings. E. g., list all preimages (see a helper
--   asSetOfPreimages):
--   
--   
--   >>> import qualified Data.Set as S
--   
--   >>> import Data.Semigroup
--   
--   >>> S.mapMonotonic getProduct (inverseTotient (S.singleton . Product) 120)
--   fromList [143,155,175,183,225,231,244,248,286,308,310,350,366,372,396,450,462]
--   
--   
--   Count preimages:
--   
--   
--   >>> inverseTotient (const 1) 120
--   17
--   
--   
--   Sum preimages:
--   
--   
--   >>> inverseTotient id 120
--   4904
--   
--   
--   Find minimal and maximal preimages:
--   
--   
--   >>> unMinWord (inverseTotient MinWord 120)
--   143
--   
--   >>> unMaxWord (inverseTotient MaxWord 120)
--   462
--   
inverseTotient :: (Semiring b, Integral a, Euclidean a, UniqueFactorisation a) => (a -> b) -> a -> b

-- | The inverse for jordan function.
--   
--   Generalizes the inverseTotient function, which is
--   inverseJordan 1.
--   
--   The return value is parameterized by a Semiring, which allows
--   various applications by providing different (multiplicative)
--   embeddings. E. g., list all preimages (see a helper
--   asSetOfPreimages):
--   
--   
--   >>> import qualified Data.Set as S
--   
--   >>> import Data.Semigroup
--   
--   >>> S.mapMonotonic getProduct (inverseJordan 2 (S.singleton . Product) 192)
--   fromList [15,16]
--   
--   
--   Similarly to inverseTotient, it is possible to count and sum
--   preimages, or get the maximum/minimum preimage.
--   
--   Note: it is the user's responsibility to use an appropriate
--   type for inverseSigmaK. Even low values of k with Int or
--   Word will return invalid results due to over/underflow, or
--   throw exceptions (i.e. division by zero).
--   
--   
--   >>> asSetOfPreimages (inverseJordan 15) (jordan 15 19) :: S.Set Int
--   fromList []
--   
--   
--   
--   >>> asSetOfPreimages (inverseJordan 15) (jordan 15 19) :: S.Set Integer
--   fromList [19]
--   
inverseJordan :: (Semiring b, Integral a, Euclidean a, UniqueFactorisation a) => Word -> (a -> b) -> a -> b

-- | The inverse for sigma 1 function.
--   
--   The return value is parameterized by a Semiring, which allows
--   various applications by providing different (multiplicative)
--   embeddings. E. g., list all preimages (see a helper
--   asSetOfPreimages):
--   
--   
--   >>> import qualified Data.Set as S
--   
--   >>> import Data.Semigroup
--   
--   >>> :set -XFlexibleContexts
--   
--   >>> S.mapMonotonic getProduct (inverseSigma (S.singleton . Product) 120)
--   fromList [54,56,87,95]
--   
--   
--   Count preimages:
--   
--   
--   >>> inverseSigma (const 1) 120
--   4
--   
--   
--   Sum preimages:
--   
--   
--   >>> inverseSigma id 120
--   292
--   
--   
--   Find minimal and maximal preimages:
--   
--   
--   >>> unMinWord (inverseSigma MinWord 120)
--   54
--   
--   >>> unMaxWord (inverseSigma MaxWord 120)
--   95
--   
inverseSigma :: (Semiring b, Euclidean a, UniqueFactorisation a, Integral a, Enum (Prime a), Bits a) => (a -> b) -> a -> b

-- | The inverse for sigma function.
--   
--   Generalizes the inverseSigma function, which is
--   inverseSigmaK 1.
--   
--   The return value is parameterized by a Semiring, which allows
--   various applications by providing different (multiplicative)
--   embeddings. E. g., list all preimages (see a helper
--   asSetOfPreimages):
--   
--   
--   >>> import qualified Data.Set as S
--   
--   >>> import Data.Semigroup
--   
--   >>> :set -XFlexibleContexts
--   
--   >>> S.mapMonotonic getProduct (inverseSigmaK 2 (S.singleton . Product) 850)
--   fromList [24,26]
--   
--   
--   Similarly to inverseSigma, it is possible to count and sum
--   preimages, or get the maximum/minimum preimage.
--   
--   Note: it is the user's responsibility to use an appropriate
--   type for inverseSigmaK. Even low values of k with Int or
--   Word will return invalid results due to over/underflow, or
--   throw exceptions (i.e. division by zero).
--   
--   
--   >>> asSetOfPreimages (inverseSigmaK 17) (sigma 17 13) :: S.Set Int
--   fromList *** Exception: divide by zero
--   
inverseSigmaK :: (Semiring b, Euclidean a, UniqueFactorisation a, Integral a, Enum (Prime a), Bits a) => Word -> (a -> b) -> a -> b

-- | Wrapper to use in conjunction with inverseTotient and
--   inverseSigma. Extracts the minimal preimage of function.
newtype MinWord
MinWord :: Word -> MinWord
[unMinWord] :: MinWord -> Word

-- | Wrapper to use in conjunction with inverseTotient and
--   inverseSigma. Extracts the maximal preimage of function.
newtype MaxWord
MaxWord :: Word -> MaxWord
[unMaxWord] :: MaxWord -> Word

-- | Wrapper to use in conjunction with inverseTotient and
--   inverseSigma. Extracts the minimal preimage of function.
data MinNatural
MinNatural :: !Natural -> MinNatural
[unMinNatural] :: MinNatural -> !Natural
Infinity :: MinNatural

-- | Wrapper to use in conjunction with inverseTotient and
--   inverseSigma. Extracts the maximal preimage of function.
newtype MaxNatural
MaxNatural :: Natural -> MaxNatural
[unMaxNatural] :: MaxNatural -> Natural

-- | Helper to extract a set of preimages for inverseTotient or
--   inverseSigma.
asSetOfPreimages :: (Ord a, Semiring a) => (forall b. Semiring b => (a -> b) -> a -> b) -> a -> Set a
instance GHC.Classes.Eq Math.NumberTheory.ArithmeticFunctions.Inverse.MaxNatural
instance GHC.Classes.Eq Math.NumberTheory.ArithmeticFunctions.Inverse.MaxWord
instance GHC.Classes.Eq Math.NumberTheory.ArithmeticFunctions.Inverse.MinNatural
instance GHC.Classes.Eq Math.NumberTheory.ArithmeticFunctions.Inverse.MinWord
instance GHC.Classes.Ord Math.NumberTheory.ArithmeticFunctions.Inverse.MaxNatural
instance GHC.Classes.Ord Math.NumberTheory.ArithmeticFunctions.Inverse.MaxWord
instance GHC.Classes.Ord Math.NumberTheory.ArithmeticFunctions.Inverse.MinNatural
instance GHC.Classes.Ord Math.NumberTheory.ArithmeticFunctions.Inverse.MinWord
instance Data.Semiring.Semiring Math.NumberTheory.ArithmeticFunctions.Inverse.MaxNatural
instance Data.Semiring.Semiring Math.NumberTheory.ArithmeticFunctions.Inverse.MaxWord
instance Data.Semiring.Semiring Math.NumberTheory.ArithmeticFunctions.Inverse.MinNatural
instance Data.Semiring.Semiring Math.NumberTheory.ArithmeticFunctions.Inverse.MinWord
instance GHC.Internal.Show.Show Math.NumberTheory.ArithmeticFunctions.Inverse.MaxNatural
instance GHC.Internal.Show.Show Math.NumberTheory.ArithmeticFunctions.Inverse.MaxWord
instance GHC.Internal.Show.Show Math.NumberTheory.ArithmeticFunctions.Inverse.MinNatural
instance GHC.Internal.Show.Show Math.NumberTheory.ArithmeticFunctions.Inverse.MinWord
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Math.NumberTheory.ArithmeticFunctions.Inverse.PrimePowers a)

-- | Numeric evaluation of various zeta-functions.
module Math.NumberTheory.Zeta

-- | Infinite sequence of approximate (up to given precision) values of
--   Riemann zeta-function at integer arguments, starting with
--   ζ(0).
--   
--   
--   >>> take 5 (zetas 1e-14) :: [Double]
--   [-0.5,Infinity,1.6449340668482264,1.2020569031595942,1.0823232337111381]
--   
--   
--   Beware to force evaluation of zetas !! 1 if the type
--   a does not support infinite values (for instance,
--   Fixed).
zetas :: (Floating a, Ord a) => a -> Infinite a

-- | Infinite sequence of exact values of Riemann zeta-function at even
--   arguments, starting with ζ(0). Note that due to numerical
--   errors conversion to Double may return values below 1:
--   
--   
--   >>> approximateValue (zetasEven !! 25) :: Double
--   0.9999999999999996
--   
--   
--   Use your favorite type for long-precision arithmetic. For instance,
--   Fixed works fine:
--   
--   
--   >>> import Data.Number.Fixed
--   
--   >>> approximateValue (zetasEven !! 25) :: Fixed Prec50
--   1.00000000000000088817842111574532859293035196051773
--   
zetasEven :: Infinite ExactPi

-- | Infinite sequence of approximate (up to given precision) values of
--   Dirichlet beta-function at integer arguments, starting with
--   β(0).
--   
--   
--   >>> take 5 (betas 1e-14) :: [Double]
--   [0.5,0.7853981633974483,0.9159655941772189,0.9689461462593694,0.9889445517411051]
--   
betas :: (Floating a, Ord a) => a -> Infinite a

-- | Infinite sequence of exact values of Dirichlet beta-function at odd
--   arguments, starting with β(1).
--   
--   
--   >>> import Data.ExactPi
--   
--   >>> approximateValue (betasOdd !! 25) :: Double
--   0.9999999999999987
--   
--   >>> import Data.Number.Fixed
--   
--   >>> approximateValue (betasOdd !! 25) :: Fixed Prec50
--   0.99999999999999999999999960726927497384196726751694
--   
betasOdd :: Infinite ExactPi

-- | Values of Hurwitz zeta function evaluated at ζ(s, a) for
--   s ∈ [0, 1 ..].
--   
--   The algorithm used was based on the Euler-Maclaurin formula and was
--   derived from Fast and Rigorous Computation of Special Functions to
--   High Precision by F. Johansson, chapter 4.8, formula 4.8.5. The
--   error for each value in this recurrence is given in formula 4.8.9 as
--   an indefinite integral, and in formula 4.8.12 as a closed form
--   formula.
--   
--   It is the user's responsibility to provide an appropriate
--   precision for the type chosen.
--   
--   For instance, when using Doubles, it does not make sense to
--   provide a number ε < 1e-53 as the desired precision. For
--   Floats, providing an ε < 1e-24 also does not make
--   sense. Example of how to call the function:
--   
--   
--   >>> zetaHurwitz 1e-15 0.25 !! 5
--   1024.3489745265808
--   
zetaHurwitz :: (Floating a, Ord a) => a -> a -> Infinite a
