Copyright | (c) 2018 Andrew Lelechenko |
---|---|
License | MIT |
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com> |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
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
- 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.
Constructors
MinNatural | |
Fields
| |
Infinity |
Instances
Show MinNatural Source # | |
Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods showsPrec :: Int -> MinNatural -> ShowS # show :: MinNatural -> String # showList :: [MinNatural] -> ShowS # | |
Eq MinNatural Source # | |
Ord MinNatural Source # | |
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 # | |
Semiring MinNatural Source # | |
Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods plus :: MinNatural -> MinNatural -> MinNatural # zero :: MinNatural # times :: MinNatural -> MinNatural -> MinNatural # one :: MinNatural # fromNatural :: Natural -> MinNatural # |
newtype MaxNatural Source #
Wrapper to use in conjunction with inverseTotient
and inverseSigma
.
Extracts the maximal preimage of function.
Constructors
MaxNatural | |
Fields |
Instances
Show MaxNatural Source # | |
Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods showsPrec :: Int -> MaxNatural -> ShowS # show :: MaxNatural -> String # showList :: [MaxNatural] -> ShowS # | |
Eq MaxNatural Source # | |
Ord MaxNatural Source # | |
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 # | |
Semiring MaxNatural Source # | |
Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods plus :: MaxNatural -> MaxNatural -> MaxNatural # zero :: MaxNatural # times :: MaxNatural -> MaxNatural -> MaxNatural # one :: MaxNatural # fromNatural :: Natural -> MaxNatural # |
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
.