Copyright	(c) 2018 Andrew Lelechenko
License	MIT
Maintainer	Andrew Lelechenko <andrew.lelechenko@gmail.com>
Safe Haskell	None
Language	Haskell2010

Math.NumberTheory.ArithmeticFunctions.Inverse

Contents

Wrappers
Utils

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

inverseTotient :: (Semiring b, Euclidean a, UniqueFactorisation a, Ord a) => (a -> b) -> a -> b
inverseSigma :: (Semiring b, Euclidean a, UniqueFactorisation a, Integral a) => (a -> b) -> a -> b
newtype MinWord = MinWord {
- unMinWord :: Word
}
newtype MaxWord = MaxWord {
- unMaxWord :: Word
}
data MinNatural
- = MinNatural {
  - unMinNatural :: !Natural
  }
- | Infinity
newtype MaxNatural = MaxNatural {
- unMaxNatural :: Natural
}
asSetOfPreimages :: (Euclidean a, Integral a) => (forall b. Semiring b => (a -> b) -> a -> b) -> a -> Set a

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) => (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
Fields unMinWord :: Word

Instances

Eq MinWord Source #
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods (==) :: MinWord -> MinWord -> Bool # (/=) :: MinWord -> MinWord -> Bool #
Ord MinWord Source #
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods compare :: MinWord -> MinWord -> Ordering # (<) :: MinWord -> MinWord -> Bool # (<=) :: MinWord -> MinWord -> Bool # (>) :: MinWord -> MinWord -> Bool # (>=) :: MinWord -> MinWord -> Bool # max :: MinWord -> MinWord -> MinWord # min :: MinWord -> MinWord -> MinWord #
Show MinWord Source #
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods showsPrec :: Int -> MinWord -> ShowS # show :: MinWord -> String # showList :: [MinWord] -> ShowS #
Semiring MinWord Source #
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods plus :: MinWord -> MinWord -> MinWord # zero :: MinWord # times :: MinWord -> MinWord -> MinWord # one :: MinWord #

newtype MaxWord Source #

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

Constructors

MaxWord
Fields unMaxWord :: Word

Instances

Eq MaxWord Source #
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods (==) :: MaxWord -> MaxWord -> Bool # (/=) :: MaxWord -> MaxWord -> Bool #
Ord MaxWord Source #
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods compare :: MaxWord -> MaxWord -> Ordering # (<) :: MaxWord -> MaxWord -> Bool # (<=) :: MaxWord -> MaxWord -> Bool # (>) :: MaxWord -> MaxWord -> Bool # (>=) :: MaxWord -> MaxWord -> Bool # max :: MaxWord -> MaxWord -> MaxWord # min :: MaxWord -> MaxWord -> MaxWord #
Show MaxWord Source #
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods showsPrec :: Int -> MaxWord -> ShowS # show :: MaxWord -> String # showList :: [MaxWord] -> ShowS #
Semiring MaxWord Source #
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods plus :: MaxWord -> MaxWord -> MaxWord # zero :: MaxWord # times :: MaxWord -> MaxWord -> MaxWord # one :: MaxWord #

data MinNatural Source #

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

Constructors

MinNatural
Fields unMinNatural :: !Natural
Infinity

Instances

Eq MinNatural Source #
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods (==) :: MinNatural -> MinNatural -> Bool # (/=) :: MinNatural -> MinNatural -> Bool #
Ord MinNatural Source #
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods compare :: MinNatural -> MinNatural -> Ordering # (<) :: MinNatural -> MinNatural -> Bool # (<=) :: MinNatural -> MinNatural -> Bool # (>) :: MinNatural -> MinNatural -> Bool # (>=) :: MinNatural -> MinNatural -> Bool # max :: MinNatural -> MinNatural -> MinNatural # min :: MinNatural -> MinNatural -> MinNatural #
Show MinNatural Source #
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods showsPrec :: Int -> MinNatural -> ShowS # show :: MinNatural -> String # showList :: [MinNatural] -> ShowS #
Semiring MinNatural Source #
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods plus :: MinNatural -> MinNatural -> MinNatural # zero :: MinNatural # times :: MinNatural -> MinNatural -> MinNatural # one :: MinNatural #

newtype MaxNatural Source #

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

Constructors

MaxNatural
Fields unMaxNatural :: Natural

Instances

Eq MaxNatural Source #
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods (==) :: MaxNatural -> MaxNatural -> Bool # (/=) :: MaxNatural -> MaxNatural -> Bool #
Ord MaxNatural Source #
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods compare :: MaxNatural -> MaxNatural -> Ordering # (<) :: MaxNatural -> MaxNatural -> Bool # (<=) :: MaxNatural -> MaxNatural -> Bool # (>) :: MaxNatural -> MaxNatural -> Bool # (>=) :: MaxNatural -> MaxNatural -> Bool # max :: MaxNatural -> MaxNatural -> MaxNatural # min :: MaxNatural -> MaxNatural -> MaxNatural #
Show MaxNatural Source #
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods showsPrec :: Int -> MaxNatural -> ShowS # show :: MaxNatural -> String # showList :: [MaxNatural] -> ShowS #
Semiring MaxNatural Source #
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods plus :: MaxNatural -> MaxNatural -> MaxNatural # zero :: MaxNatural # times :: MaxNatural -> MaxNatural -> MaxNatural # one :: MaxNatural #

Utils

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

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