arithmoi-0.13.0.0: Efficient basic number-theoretic functions.

Copyright | (c) 2016 Andrew Lelechenko
License | MIT
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com>
Safe Haskell | Safe-Inferred
Language | Haskell2010

Math.NumberTheory.ArithmeticFunctions

Contents

- List divisors
- Multiplicative functions
- Additive functions
- Misc

Description

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

Synopsis

- data ArithmeticFunction n a where
  - ArithmeticFunction :: Monoid m => (Prime n -> Word -> m) -> (m -> a) -> ArithmeticFunction n a
- runFunction :: UniqueFactorisation n => ArithmeticFunction n a -> n -> a
- runFunctionOnFactors :: ArithmeticFunction n a -> [(Prime n, Word)] -> a
- divisors :: (UniqueFactorisation n, Ord n) => n -> Set n
- divisorsA :: (Ord n, Num n) => ArithmeticFunction n (Set n)
- divisorsList :: UniqueFactorisation n => n -> [n]
- divisorsListA :: Num n => ArithmeticFunction n [n]
- divisorsSmall :: Int -> IntSet
- divisorsSmallA :: ArithmeticFunction Int IntSet
- divisorsTo :: (UniqueFactorisation n, Integral n) => n -> n -> Set n
- divisorsToA :: (UniqueFactorisation n, Integral n) => n -> ArithmeticFunction n (Set n)
- multiplicative :: Num a => (Prime n -> Word -> a) -> ArithmeticFunction n a
- divisorCount :: (UniqueFactorisation n, Num a) => n -> a
- tau :: (UniqueFactorisation n, Num a) => n -> a
- tauA :: Num a => ArithmeticFunction n a
- sigma :: (UniqueFactorisation n, Integral n, Num a, GcdDomain a) => Word -> n -> a
- sigmaA :: (Integral n, Num a, GcdDomain a) => Word -> ArithmeticFunction n a
- totient :: UniqueFactorisation n => n -> n
- totientA :: Num n => ArithmeticFunction n n
- jordan :: UniqueFactorisation n => Word -> n -> n
- jordanA :: Num n => Word -> ArithmeticFunction n n
- ramanujan :: Integer -> Integer
- ramanujanA :: ArithmeticFunction Integer Integer
- moebius :: UniqueFactorisation n => n -> Moebius
- moebiusA :: ArithmeticFunction n Moebius
- data Moebius
  - = MoebiusN
  - | MoebiusZ
  - | MoebiusP
- runMoebius :: Num a => Moebius -> a
- liouville :: (UniqueFactorisation n, Num a) => n -> a
- liouvilleA :: Num a => ArithmeticFunction n a
- additive :: Num a => (Prime n -> Word -> a) -> ArithmeticFunction n a
- smallOmega :: (UniqueFactorisation n, Num a) => n -> a
- smallOmegaA :: Num a => ArithmeticFunction n a
- bigOmega :: UniqueFactorisation n => n -> Word
- bigOmegaA :: ArithmeticFunction n Word
- carmichael :: (UniqueFactorisation n, Integral n) => n -> n
- carmichaelA :: Integral n => ArithmeticFunction n n
- expMangoldt :: UniqueFactorisation n => n -> n
- expMangoldtA :: Num n => ArithmeticFunction n n
- isNFree :: UniqueFactorisation n => Word -> n -> Bool
- isNFreeA :: Word -> ArithmeticFunction n Bool
- nFrees :: forall a. (Integral a, Bits a, UniqueFactorisation a, Enum (Prime a)) => Word -> [a]
- nFreesBlock :: forall a. (Integral a, Bits a, UniqueFactorisation a, Enum (Prime a)) => Word -> a -> Word -> [a]

# Documentation

data ArithmeticFunction n a where Source #

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

Instances details

Applicative (ArithmeticFunction n) Source # |

Instance details

Defined in Math.NumberTheory.ArithmeticFunctions.Class

Methods

pure :: a -> ArithmeticFunction n a Source #

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

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

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

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

Functor (ArithmeticFunction n) Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Class Methods fmap :: (a -> b) -> ArithmeticFunction n a -> ArithmeticFunction n b Source # (<$) :: a -> ArithmeticFunction n b -> ArithmeticFunction n a Source #
Monoid a => Monoid (ArithmeticFunction n a) Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Class Methods mempty :: ArithmeticFunction n a Source # mappend :: ArithmeticFunction n a -> ArithmeticFunction n a -> ArithmeticFunction n a Source # mconcat :: [ArithmeticFunction n a] -> ArithmeticFunction n a Source #
Semigroup a => Semigroup (ArithmeticFunction n a) Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Class Methods (<>) :: ArithmeticFunction n a -> ArithmeticFunction n a -> ArithmeticFunction n a Source # sconcat :: NonEmpty (ArithmeticFunction n a) -> ArithmeticFunction n a Source # stimes :: Integral b => b -> ArithmeticFunction n a -> ArithmeticFunction n a Source #
Floating a => Floating (ArithmeticFunction n a) Source # |

Instance details

Defined in Math.NumberTheory.ArithmeticFunctions.Class

Methods

pi :: ArithmeticFunction n a Source #

exp :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

log :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

sqrt :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

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

logBase :: ArithmeticFunction n a -> ArithmeticFunction n a -> ArithmeticFunction n a Source #

sin :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

cos :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

tan :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

asin :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

acos :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

atan :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

sinh :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

cosh :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

tanh :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

asinh :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

acosh :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

atanh :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

log1p :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

expm1 :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

log1pexp :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

log1mexp :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

Num a => Num (ArithmeticFunction n a) Source # | 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'.

Instance details

Defined in Math.NumberTheory.ArithmeticFunctions.Class

Methods

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

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

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

negate :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

abs :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

signum :: ArithmeticFunction n a -> ArithmeticFunction n a Source #

fromInteger :: Integer -> ArithmeticFunction n a Source #

Fractional a => Fractional (ArithmeticFunction n a) Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Class Methods (/) :: ArithmeticFunction n a -> ArithmeticFunction n a -> ArithmeticFunction n a Source # recip :: ArithmeticFunction n a -> ArithmeticFunction n a Source # fromRational :: Rational -> ArithmeticFunction n a Source #

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

Convert to a function. The value on 0 is undefined.

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

Convert to a function on prime factorisation.

# List divisors

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

See `divisorsA`.

divisorsA :: (Ord n, Num n) => ArithmeticFunction n (Set n) Source #

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

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

See `divisorsListA`.

divisorsListA :: Num n => ArithmeticFunction n [n] Source #

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

divisorsSmall :: Int -> IntSet Source #

See `divisorsSmallA`.

divisorsSmallA :: ArithmeticFunction Int IntSet Source #

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

divisorsTo :: (UniqueFactorisation n, Integral n) => n -> n -> Set n Source #

See `divisorsToA`.

divisorsToA :: (UniqueFactorisation n, Integral n) => n -> ArithmeticFunction n (Set n) Source #

The set of all (positive) divisors up to an inclusive bound.

# Multiplicative functions

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

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

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

Synonym for `tau`.

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

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

See `tauA`.

tauA :: Num a => ArithmeticFunction n a Source #

The number of (positive) divisors of an argument.

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

sigma :: (UniqueFactorisation n, Integral n, Num a, GcdDomain a) => Word -> n -> a Source #

See `sigmaA`.

sigmaA :: (Integral n, Num a, GcdDomain a) => Word -> ArithmeticFunction n a Source #

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 Source #

See `totientA`.

totientA :: Num n => ArithmeticFunction n n Source #

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 Source #

See `jordanA`.

jordanA :: Num n => Word -> ArithmeticFunction n n Source #

Calculates the k-th Jordan function of an argument.

    jordanA 1 = totientA

ramanujan :: Integer -> Integer Source #

See `ramanujanA`.

ramanujanA :: ArithmeticFunction Integer Integer Source #

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

moebius :: UniqueFactorisation n => n -> Moebius Source #

See `moebiusA`.

moebiusA :: ArithmeticFunction n Moebius Source #

Calculates the Möbius function of an argument.

data Moebius Source #

Represents three possible values of Möbius function.

Constructors

MoebiusN

- 1

MoebiusZ | 0
MoebiusP | 1

#### Instances

Instances details

Monoid Moebius Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Moebius Methods mempty :: Moebius Source # mappend :: Moebius -> Moebius -> Moebius Source # mconcat :: [Moebius] -> Moebius Source #
Semigroup Moebius Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Moebius Methods (<>) :: Moebius -> Moebius -> Moebius Source # sconcat :: NonEmpty Moebius -> Moebius Source # stimes :: Integral b => b -> Moebius -> Moebius Source #
Show Moebius Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Moebius Methods showsPrec :: Int -> Moebius -> ShowS Source # show :: Moebius -> String Source # showList :: [Moebius] -> ShowS Source #
Eq Moebius Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Moebius Methods (==) :: Moebius -> Moebius -> Bool Source # (/=) :: Moebius -> Moebius -> Bool Source #
Ord Moebius Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Moebius Methods compare :: Moebius -> Moebius -> Ordering Source # (<) :: Moebius -> Moebius -> Bool Source # (<=) :: Moebius -> Moebius -> Bool Source # (>) :: Moebius -> Moebius -> Bool Source # (>=) :: Moebius -> Moebius -> Bool Source # max :: Moebius -> Moebius -> Moebius Source # min :: Moebius -> Moebius -> Moebius Source #
Unbox Moebius Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Moebius
Vector Vector Moebius Source # |

Instance details

Defined in Math.NumberTheory.ArithmeticFunctions.Moebius

Methods

basicUnsafeFreeze :: Mutable Vector s Moebius -> ST s (Vector Moebius) Source #

basicUnsafeThaw :: Vector Moebius -> ST s (Mutable Vector s Moebius) Source #

basicLength :: Vector Moebius -> Int Source #

basicUnsafeSlice :: Int -> Int -> Vector Moebius -> Vector Moebius Source #

basicUnsafeIndexM :: Vector Moebius -> Int -> Box Moebius Source #

basicUnsafeCopy :: Mutable Vector s Moebius -> Vector Moebius -> ST s () Source #

elemseq :: Vector Moebius -> Moebius -> b -> b Source #

MVector MVector Moebius Source # |

Instance details

Defined in Math.NumberTheory.ArithmeticFunctions.Moebius

Methods

basicLength :: MVector s Moebius -> Int Source #

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

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

basicUnsafeNew :: Int -> ST s (MVector s Moebius) Source #

basicInitialize :: MVector s Moebius -> ST s () Source #

basicUnsafeReplicate :: Int -> Moebius -> ST s (MVector s Moebius) Source #

basicUnsafeRead :: MVector s Moebius -> Int -> ST s Moebius Source #

basicUnsafeWrite :: MVector s Moebius -> Int -> Moebius -> ST s () Source #

basicClear :: MVector s Moebius -> ST s () Source #

basicSet :: MVector s Moebius -> Moebius -> ST s () Source #

basicUnsafeCopy :: MVector s Moebius -> MVector s Moebius -> ST s () Source #

basicUnsafeMove :: MVector s Moebius -> MVector s Moebius -> ST s () Source #

basicUnsafeGrow :: MVector s Moebius -> Int -> ST s (MVector s Moebius) Source #

newtype Vector Moebius Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Moebius newtype Vector Moebius = V_Moebius (Vector Int8)
newtype MVector s Moebius Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Moebius newtype MVector s Moebius = MV_Moebius (MVector s Int8)

runMoebius :: Num a => Moebius -> a Source #

Convert to any numeric type.

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

See `liouvilleA`.

liouvilleA :: Num a => ArithmeticFunction n a Source #

Calculates the Liouville function of an argument.

# Additive functions

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

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

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

See `smallOmegaA`.

smallOmegaA :: Num a => ArithmeticFunction n a Source #

Number of distinct prime factors.

    smallOmegaA = additive (\_ _ -> 1)

bigOmega :: UniqueFactorisation n => n -> Word Source #

See `bigOmegaA`.

bigOmegaA :: ArithmeticFunction n Word Source #

Number of prime factors, counted with multiplicity.

    bigOmegaA = additive (\_ k -> k)

# Misc

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

See `carmichaelA`.

carmichaelA :: Integral n => ArithmeticFunction n n Source #

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 Source #

See `expMangoldtA`.

expMangoldtA :: Num n => ArithmeticFunction n n Source #

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

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

See `isNFreeA`.

isNFreeA :: Word -> ArithmeticFunction n Bool Source #

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 Source #

Arguments

:: forall a. (Integral a, Bits a, UniqueFactorisation a, Enum (Prime 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 Source #

Arguments

:: forall a. (Integral a, Bits a, UniqueFactorisation a, Enum (Prime 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.