Math.NumberTheory.ArithmeticFunctions

This module provides an interface for defining and manipulating arithmetic functions. It also defines several most widespreaded arithmetic functions.

Documentation

data ArithmeticFunction n a where

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

Constructors

ArithmeticFunction :: Monoid m => (Prime n -> Word -> m) -> (m -> a) -> ArithmeticFunction n a

Instances

Functor (ArithmeticFunction n)

Methods

fmap :: (a -> b) -> ArithmeticFunction n a -> ArithmeticFunction n b

(<$) :: a -> ArithmeticFunction n b -> ArithmeticFunction n a

Applicative (ArithmeticFunction n)

Methods

pure :: a -> ArithmeticFunction n a

(<*>) :: ArithmeticFunction n (a -> b) -> ArithmeticFunction n a -> ArithmeticFunction n b

(*>) :: ArithmeticFunction n a -> ArithmeticFunction n b -> ArithmeticFunction n b

(<*) :: ArithmeticFunction n a -> ArithmeticFunction n b -> ArithmeticFunction n a

Floating a => Floating (ArithmeticFunction n a)

Methods

pi :: ArithmeticFunction n a

exp :: ArithmeticFunction n a -> ArithmeticFunction n a

log :: ArithmeticFunction n a -> ArithmeticFunction n a

sqrt :: ArithmeticFunction n a -> ArithmeticFunction n a

(**) :: ArithmeticFunction n a -> ArithmeticFunction n a -> ArithmeticFunction n a

logBase :: ArithmeticFunction n a -> ArithmeticFunction n a -> ArithmeticFunction n a

sin :: ArithmeticFunction n a -> ArithmeticFunction n a

cos :: ArithmeticFunction n a -> ArithmeticFunction n a

tan :: ArithmeticFunction n a -> ArithmeticFunction n a

asin :: ArithmeticFunction n a -> ArithmeticFunction n a

acos :: ArithmeticFunction n a -> ArithmeticFunction n a

atan :: ArithmeticFunction n a -> ArithmeticFunction n a

sinh :: ArithmeticFunction n a -> ArithmeticFunction n a

cosh :: ArithmeticFunction n a -> ArithmeticFunction n a

tanh :: ArithmeticFunction n a -> ArithmeticFunction n a

asinh :: ArithmeticFunction n a -> ArithmeticFunction n a

acosh :: ArithmeticFunction n a -> ArithmeticFunction n a

atanh :: ArithmeticFunction n a -> ArithmeticFunction n a

log1p :: ArithmeticFunction n a -> ArithmeticFunction n a

expm1 :: ArithmeticFunction n a -> ArithmeticFunction n a

log1pexp :: ArithmeticFunction n a -> ArithmeticFunction n a

log1mexp :: ArithmeticFunction n a -> ArithmeticFunction n a

Fractional a => Fractional (ArithmeticFunction n a)

Methods

(/) :: ArithmeticFunction n a -> ArithmeticFunction n a -> ArithmeticFunction n a

recip :: ArithmeticFunction n a -> ArithmeticFunction n a

fromRational :: Rational -> ArithmeticFunction n a

Num a => Num (ArithmeticFunction n a)

Factorisation is expensive, so it is better to avoid doing it twice. Write 'runFunction (f + g) n' instead of 'runFunction f n + runFunction g n'.

Methods

(+) :: ArithmeticFunction n a -> ArithmeticFunction n a -> ArithmeticFunction n a

(-) :: ArithmeticFunction n a -> ArithmeticFunction n a -> ArithmeticFunction n a

(*) :: ArithmeticFunction n a -> ArithmeticFunction n a -> ArithmeticFunction n a

negate :: ArithmeticFunction n a -> ArithmeticFunction n a

abs :: ArithmeticFunction n a -> ArithmeticFunction n a

signum :: ArithmeticFunction n a -> ArithmeticFunction n a

fromInteger :: Integer -> ArithmeticFunction n a

Semigroup a => Semigroup (ArithmeticFunction n a)

Methods

(<>) :: ArithmeticFunction n a -> ArithmeticFunction n a -> ArithmeticFunction n a

sconcat :: NonEmpty (ArithmeticFunction n a) -> ArithmeticFunction n a

stimes :: Integral b => b -> ArithmeticFunction n a -> ArithmeticFunction n a

Monoid a => Monoid (ArithmeticFunction n a)

Methods

mempty :: ArithmeticFunction n a

mappend :: ArithmeticFunction n a -> ArithmeticFunction n a -> ArithmeticFunction n a

mconcat :: [ArithmeticFunction n a] -> ArithmeticFunction n a

runFunction :: UniqueFactorisation n => ArithmeticFunction n a -> n -> a

Convert to function. The value on 0 is undefined.

Multiplicative functions

multiplicative :: Num a => (Prime n -> Word -> a) -> ArithmeticFunction n a

Create a multiplicative function from the function on prime's powers. See examples below.

divisors :: (UniqueFactorisation n, Num n, Ord n) => n -> Set n

divisorsA :: forall n. (UniqueFactorisation n, Num n, Ord n) => ArithmeticFunction n (Set n)

The set of all (positive) divisors of an argument.

divisorsSmall :: (UniqueFactorisation n, Prime n ~ Prime Int) => n -> IntSet

divisorsSmallA :: forall n. Prime n ~ Prime Int => ArithmeticFunction n IntSet

Same as divisors, but with better performance on cost of type restriction.

tau :: (UniqueFactorisation n, Num a) => n -> a

tauA :: Num a => ArithmeticFunction n a

The number of (positive) divisors of an argument.

tauA = multiplicative (\_ k -> k + 1)

sigma :: (UniqueFactorisation n, Integral n) => Word -> n -> n

sigmaA :: forall n. (UniqueFactorisation n, Integral n) => Word -> ArithmeticFunction n n

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

totient :: (UniqueFactorisation n, Integral n) => n -> n

totientA :: forall n. (UniqueFactorisation n, Integral n) => ArithmeticFunction n n

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

jordan :: (UniqueFactorisation n, Integral n) => Word -> n -> n

jordanA :: forall n. (UniqueFactorisation n, Integral n) => Word -> ArithmeticFunction n n

Calculates the k-th Jordan function of an argument.

jordanA 1 = totientA

moebius :: (UniqueFactorisation n, Num a) => n -> a

moebiusA :: Num a => ArithmeticFunction n a

Calculates the Moebius function of an argument.

liouville :: (UniqueFactorisation n, Num a) => n -> a

liouvilleA :: Num a => ArithmeticFunction n a

Calculates the Liouville function of an argument.

Additive functions

additive :: Num a => (Prime n -> Word -> a) -> ArithmeticFunction n a

Create an additive function from the function on prime's powers. See examples below.

smallOmega :: (UniqueFactorisation n, Num a) => n -> a

smallOmegaA :: Num a => ArithmeticFunction n a

Number of distinct prime factors.

smallOmegaA = additive (\_ _ -> 1)

bigOmega :: UniqueFactorisation n => n -> Word

bigOmegaA :: ArithmeticFunction n Word

Number of prime factors, counted with multiplicity.

bigOmegaA = additive (\_ k -> k)

Misc

carmichael :: (UniqueFactorisation n, Integral n) => n -> n

carmichaelA :: forall n. (UniqueFactorisation n, Integral n) => ArithmeticFunction n n

Calculates the Carmichael function for a positive integer, that is, the (smallest) exponent of the group of units in ℤ/(n).

expMangoldt :: (UniqueFactorisation n, Num n) => n -> n

expMangoldtA :: forall n. (UniqueFactorisation n, Num n) => ArithmeticFunction n n

The exponent of von Mangoldt function. Use log expMangoldtA to recover von Mangoldt function itself.