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)

Defined in Math.NumberTheory.ArithmeticFunctions.Class

Methods

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

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

Applicative (ArithmeticFunction n)

Defined in Math.NumberTheory.ArithmeticFunctions.Class

Methods

pure :: a -> ArithmeticFunction n a

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

liftA2 :: (a -> b -> c) -> ArithmeticFunction n a -> ArithmeticFunction n b -> ArithmeticFunction n c

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

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

Floating a => Floating (ArithmeticFunction n a)

Defined in Math.NumberTheory.ArithmeticFunctions.Class

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)

Defined in Math.NumberTheory.ArithmeticFunctions.Class

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

Defined in Math.NumberTheory.ArithmeticFunctions.Class

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)

Defined in Math.NumberTheory.ArithmeticFunctions.Class

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)

Defined in Math.NumberTheory.ArithmeticFunctions.Class

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 a function. The value on 0 is undefined.

runFunctionOnFactors :: ArithmeticFunction n a -> [(Prime n, Word)] -> a

Convert to a function on prime factorisation.

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, Ord n) => n -> Set n

See divisorsA.

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

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

divisorsList :: UniqueFactorisation n => n -> [n]

See divisorsListA.

divisorsListA :: UniqueFactorisation n => ArithmeticFunction n [n]

The unsorted list of all (positive) divisors of an argument, produced in lazy fashion.

divisorsSmall :: Int -> IntSet

See divisorsSmallA.

divisorsSmallA :: ArithmeticFunction Int IntSet

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

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

Synonym for tau.

>>> map divisorCount [1..10]
[1,2,2,3,2,4,2,4,3,4]

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

See tauA.

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

See sigmaA.

sigmaA :: (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 => n -> n

See totientA.

totientA :: UniqueFactorisation 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 => Word -> n -> n

See jordanA.

jordanA :: UniqueFactorisation n => Word -> ArithmeticFunction n n

Calculates the k-th Jordan function of an argument.

jordanA 1 = totientA

ramanujan :: Integer -> Integer

See ramanujanA.

ramanujanA :: ArithmeticFunction Integer Integer

Calculates the Ramanujan tau function of a positive number n, using formulas given here

moebius :: UniqueFactorisation n => n -> Moebius

See moebiusA.

moebiusA :: ArithmeticFunction n Moebius

Calculates the Möbius function of an argument.

data Moebius

Represents three possible values of Möbius function.

Constructors

MoebiusN

• 1

MoebiusZ

0

MoebiusP

1

Instances

Eq Moebius

Defined in Math.NumberTheory.ArithmeticFunctions.Moebius

Methods

(==) :: Moebius -> Moebius -> Bool

(/=) :: Moebius -> Moebius -> Bool

Ord Moebius

Defined in Math.NumberTheory.ArithmeticFunctions.Moebius

Methods

compare :: Moebius -> Moebius -> Ordering

(<) :: Moebius -> Moebius -> Bool

(<=) :: Moebius -> Moebius -> Bool

(>) :: Moebius -> Moebius -> Bool

(>=) :: Moebius -> Moebius -> Bool

max :: Moebius -> Moebius -> Moebius

min :: Moebius -> Moebius -> Moebius

Show Moebius

Defined in Math.NumberTheory.ArithmeticFunctions.Moebius

Methods

showsPrec :: Int -> Moebius -> ShowS

show :: Moebius -> String

showList :: [Moebius] -> ShowS

Semigroup Moebius

Defined in Math.NumberTheory.ArithmeticFunctions.Moebius

Methods

(<>) :: Moebius -> Moebius -> Moebius

sconcat :: NonEmpty Moebius -> Moebius

stimes :: Integral b => b -> Moebius -> Moebius

Monoid Moebius

Defined in Math.NumberTheory.ArithmeticFunctions.Moebius

Methods

mempty :: Moebius

mappend :: Moebius -> Moebius -> Moebius

mconcat :: [Moebius] -> Moebius

Unbox Moebius

Defined in Math.NumberTheory.ArithmeticFunctions.Moebius

Vector Vector Moebius

Defined in Math.NumberTheory.ArithmeticFunctions.Moebius

Methods

basicUnsafeFreeze :: PrimMonad m => Mutable Vector (PrimState m) Moebius -> m (Vector Moebius)

basicUnsafeThaw :: PrimMonad m => Vector Moebius -> m (Mutable Vector (PrimState m) Moebius)

basicLength :: Vector Moebius -> Int

basicUnsafeSlice :: Int -> Int -> Vector Moebius -> Vector Moebius

basicUnsafeIndexM :: Monad m => Vector Moebius -> Int -> m Moebius

basicUnsafeCopy :: PrimMonad m => Mutable Vector (PrimState m) Moebius -> Vector Moebius -> m ()

elemseq :: Vector Moebius -> Moebius -> b -> b

MVector MVector Moebius

Defined in Math.NumberTheory.ArithmeticFunctions.Moebius

Methods

basicLength :: MVector s Moebius -> Int

basicUnsafeSlice :: Int -> Int -> MVector s Moebius -> MVector s Moebius

basicOverlaps :: MVector s Moebius -> MVector s Moebius -> Bool

basicUnsafeNew :: PrimMonad m => Int -> m (MVector (PrimState m) Moebius)

basicInitialize :: PrimMonad m => MVector (PrimState m) Moebius -> m ()

basicUnsafeReplicate :: PrimMonad m => Int -> Moebius -> m (MVector (PrimState m) Moebius)

basicUnsafeRead :: PrimMonad m => MVector (PrimState m) Moebius -> Int -> m Moebius

basicUnsafeWrite :: PrimMonad m => MVector (PrimState m) Moebius -> Int -> Moebius -> m ()

basicClear :: PrimMonad m => MVector (PrimState m) Moebius -> m ()

basicSet :: PrimMonad m => MVector (PrimState m) Moebius -> Moebius -> m ()

basicUnsafeCopy :: PrimMonad m => MVector (PrimState m) Moebius -> MVector (PrimState m) Moebius -> m ()

basicUnsafeMove :: PrimMonad m => MVector (PrimState m) Moebius -> MVector (PrimState m) Moebius -> m ()

basicUnsafeGrow :: PrimMonad m => MVector (PrimState m) Moebius -> Int -> m (MVector (PrimState m) Moebius)

newtype Vector Moebius

Defined in Math.NumberTheory.ArithmeticFunctions.Moebius

newtype Vector Moebius = V_Moebius (Vector Int8)

newtype MVector s Moebius

Defined in Math.NumberTheory.ArithmeticFunctions.Moebius

newtype MVector s Moebius = MV_Moebius (MVector s Int8)

runMoebius :: Num a => Moebius -> a

Convert to any numeric type.

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

See liouvilleA.

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

See smallOmegaA.

smallOmegaA :: Num a => ArithmeticFunction n a

Number of distinct prime factors.

smallOmegaA = additive (\_ _ -> 1)

bigOmega :: UniqueFactorisation n => n -> Word

See bigOmegaA.

bigOmegaA :: ArithmeticFunction n Word

Number of prime factors, counted with multiplicity.

bigOmegaA = additive (\_ k -> k)

Misc

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

See carmichaelA.

carmichaelA :: (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 => n -> n

See expMangoldtA.

expMangoldtA :: UniqueFactorisation n => ArithmeticFunction n n

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

isNFree :: UniqueFactorisation n => Word -> n -> Bool

See isNFreeA.

isNFreeA :: Word -> ArithmeticFunction 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.

nFrees

Arguments

:: Integral a

=> Word

Power n to be used to generate n-free numbers.

-> [a]

Generated infinite list of n-free numbers.

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

nFreesBlock

Arguments

:: Integral a

=> Word

Power n to be used to generate n-free numbers.

-> a

Starting number in the block.

-> Word

Maximum length of the block to be generated.

-> [a]

Generated list of n-free numbers.

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.