arithmoi-0.11.0.0: Efficient basic number-theoretic functions.

Math.NumberTheory.ArithmeticFunctions.Inverse

Contents

Description

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.

Synopsis

# Documentation

inverseTotient :: (Semiring b, Integral a, Euclidean a, UniqueFactorisation a) => (a -> b) -> a -> b Source #

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


inverseJordan :: (Semiring b, Integral a, Euclidean a, UniqueFactorisation a) => Word -> (a -> b) -> a -> b Source #

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]


inverseSigma :: (Semiring b, Euclidean a, UniqueFactorisation a, Integral a, Enum (Prime a), Bits a) => (a -> b) -> a -> b Source #

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


inverseSigmaK :: (Semiring b, Euclidean a, UniqueFactorisation a, Integral a, Enum (Prime a), Bits a) => Word -> (a -> b) -> a -> b Source #

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


# Wrappers

newtype MinWord Source #

Wrapper to use in conjunction with inverseTotient and inverseSigma. Extracts the minimal preimage of function.

Constructors

 MinWord FieldsunMinWord :: Word
Instances
 Source # Instance details Methods(==) :: MinWord -> MinWord -> Bool #(/=) :: MinWord -> MinWord -> Bool # Source # Instance details Methods(<) :: MinWord -> MinWord -> Bool #(<=) :: MinWord -> MinWord -> Bool #(>) :: MinWord -> MinWord -> Bool #(>=) :: MinWord -> MinWord -> Bool # Source # Instance details MethodsshowList :: [MinWord] -> ShowS # Source # Instance details Methods

newtype MaxWord Source #

Wrapper to use in conjunction with inverseTotient and inverseSigma. Extracts the maximal preimage of function.

Constructors

 MaxWord FieldsunMaxWord :: Word
Instances
 Source # Instance details Methods(==) :: MaxWord -> MaxWord -> Bool #(/=) :: MaxWord -> MaxWord -> Bool # Source # Instance details Methods(<) :: MaxWord -> MaxWord -> Bool #(<=) :: MaxWord -> MaxWord -> Bool #(>) :: MaxWord -> MaxWord -> Bool #(>=) :: MaxWord -> MaxWord -> Bool # Source # Instance details MethodsshowList :: [MaxWord] -> ShowS # Source # Instance details Methods

Wrapper to use in conjunction with inverseTotient and inverseSigma. Extracts the minimal preimage of function.

Constructors

 MinNatural FieldsunMinNatural :: !Natural Infinity
Instances
 Source # Instance details Methods Source # Instance details Methods Source # Instance details MethodsshowList :: [MinNatural] -> ShowS # Source # Instance details Methods

newtype MaxNatural Source #

Wrapper to use in conjunction with inverseTotient and inverseSigma. Extracts the maximal preimage of function.

Constructors

 MaxNatural FieldsunMaxNatural :: Natural
Instances
 Source # Instance details Methods Source # Instance details Methods Source # Instance details MethodsshowList :: [MaxNatural] -> ShowS # Source # Instance details Methods

# Utils

asSetOfPreimages :: (Ord a, Semiring a) => (forall b. Semiring b => (a -> b) -> a -> b) -> a -> Set a Source #

Helper to extract a set of preimages for inverseTotient or inverseSigma.