arithmoi-0.13.2.0: Efficient basic number-theoretic functions.

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, 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 {
  - unMinWord :: Word
  }
- newtype MaxWord = MaxWord {
  - unMaxWord :: Word
  }
- data MinNatural
  - = MinNatural {
    - unMinNatural :: !Natural
    }
  - | Infinity
- newtype MaxNatural = MaxNatural {
  - unMaxNatural :: Natural
  }
- 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

newtype MinWord Source #

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

Constructors

MinWord |

Fields

- unMinWord :: Word

#### Instances

Instances details

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

newtype MaxWord Source #

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

Constructors

MaxWord |

Fields

- unMaxWord :: Word

#### Instances

Instances details

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

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

Instances details

Show MinNatural Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods showsPrec :: Int -> MinNatural -> ShowS Source # show :: MinNatural -> String Source # showList :: [MinNatural] -> ShowS Source #
Eq MinNatural Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods (==) :: MinNatural -> MinNatural -> Bool Source # (/=) :: MinNatural -> MinNatural -> Bool Source #
Ord MinNatural Source # |

Instance details

Defined in Math.NumberTheory.ArithmeticFunctions.Inverse

Methods

compare :: MinNatural -> MinNatural -> Ordering Source #

(<) :: MinNatural -> MinNatural -> Bool Source #

(<=) :: MinNatural -> MinNatural -> Bool Source #

(>) :: MinNatural -> MinNatural -> Bool Source #

(>=) :: MinNatural -> MinNatural -> Bool Source #

max :: MinNatural -> MinNatural -> MinNatural Source #

min :: MinNatural -> MinNatural -> MinNatural Source #

Semiring MinNatural Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods plus :: MinNatural -> MinNatural -> MinNatural Source # zero :: MinNatural Source # times :: MinNatural -> MinNatural -> MinNatural Source # one :: MinNatural Source # fromNatural :: Natural -> MinNatural Source #

newtype MaxNatural Source #

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

Constructors

MaxNatural |

Fields

- unMaxNatural :: Natural

#### Instances

Instances details

Show MaxNatural Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods showsPrec :: Int -> MaxNatural -> ShowS Source # show :: MaxNatural -> String Source # showList :: [MaxNatural] -> ShowS Source #
Eq MaxNatural Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods (==) :: MaxNatural -> MaxNatural -> Bool Source # (/=) :: MaxNatural -> MaxNatural -> Bool Source #
Ord MaxNatural Source # |

Instance details

Defined in Math.NumberTheory.ArithmeticFunctions.Inverse

Methods

compare :: MaxNatural -> MaxNatural -> Ordering Source #

(<) :: MaxNatural -> MaxNatural -> Bool Source #

(<=) :: MaxNatural -> MaxNatural -> Bool Source #

(>) :: MaxNatural -> MaxNatural -> Bool Source #

(>=) :: MaxNatural -> MaxNatural -> Bool Source #

max :: MaxNatural -> MaxNatural -> MaxNatural Source #

min :: MaxNatural -> MaxNatural -> MaxNatural Source #

Semiring MaxNatural Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Inverse Methods plus :: MaxNatural -> MaxNatural -> MaxNatural Source # zero :: MaxNatural Source # times :: MaxNatural -> MaxNatural -> MaxNatural Source # one :: MaxNatural Source # fromNatural :: Natural -> MaxNatural Source #

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