arithmoi-0.12.0.2: Efficient basic number-theoretic functions.
Copyright(c) 2018 Andrew Lelechenko
LicenseMIT
MaintainerAndrew Lelechenko <andrew.lelechenko@gmail.com>
Safe HaskellNone
LanguageHaskell2010

Math.NumberTheory.ArithmeticFunctions.Inverse

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

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

Wrappers

newtype MinWord Source #

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

Constructors

MinWord 

Fields

newtype MaxWord Source #

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

Constructors

MaxWord 

Fields

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.