Copyright | (c) 2018 Andrew Lelechenko |
---|---|
License | MIT |
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com> |
Safe Haskell | None |
Language | Haskell2010 |
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, Integral a, Euclidean a, UniqueFactorisation a) => (a -> b) -> a -> b
- inverseJordan :: (Semiring b, Integral a, Euclidean a, UniqueFactorisation a) => Word -> (a -> b) -> a -> b
- inverseSigma :: (Semiring b, Euclidean a, UniqueFactorisation a, Integral a, Enum (Prime a), Bits a) => (a -> b) -> a -> b
- inverseSigmaK :: (Semiring b, Euclidean a, UniqueFactorisation a, Integral a, Enum (Prime a), Bits a) => Word -> (a -> b) -> a -> b
- newtype MinWord = MinWord {}
- newtype MaxWord = MaxWord {}
- data MinNatural
- = MinNatural {
- unMinNatural :: !Natural
- | Infinity
- = MinNatural {
- newtype MaxNatural = MaxNatural {}
- asSetOfPreimages :: (Ord a, Semiring a) => (forall b. Semiring b => (a -> b) -> a -> b) -> a -> Set a
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
Wrapper to use in conjunction with inverseTotient
and inverseSigma
.
Extracts the minimal preimage of function.
Wrapper to use in conjunction with inverseTotient
and inverseSigma
.
Extracts the maximal preimage of function.
data MinNatural Source #
Wrapper to use in conjunction with inverseTotient
and inverseSigma
.
Extracts the minimal preimage of function.
Instances
newtype MaxNatural Source #
Wrapper to use in conjunction with inverseTotient
and inverseSigma
.
Extracts the maximal preimage of function.
Instances
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
.