arithmoi-0.10.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, Euclidean a, UniqueFactorisation a, Ord 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


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


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