arithmoi-0.13.0.0: Efficient basic number-theoretic functions.

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

Math.NumberTheory.Euclidean.Coprimes

Description

Container for pairwise coprime numbers.

Synopsis

- splitIntoCoprimes :: (Eq a, GcdDomain a, Eq b, Num b) => [(a, b)] -> Coprimes a b
- data Coprimes a b
- unCoprimes :: Coprimes a b -> [(a, b)]
- singleton :: (Eq a, GcdDomain a, Eq b, Num b) => a -> b -> Coprimes a b
- insert :: (Eq a, GcdDomain a, Eq b, Num b) => a -> b -> Coprimes a b -> Coprimes a b

# Documentation

splitIntoCoprimes :: (Eq a, GcdDomain a, Eq b, Num b) => [(a, b)] -> Coprimes a b Source #

The input list is assumed to be a factorisation of some number into a list of powers of (possibly, composite) non-zero factors. The output list is a factorisation of the same number such that all factors are coprime. Such transformation is crucial to continue factorisation (lazily, in parallel or concurrent fashion) without having to merge multiplicities of primes, which occurs more than in one composite factor.

    >>> splitIntoCoprimes [(140, 1), (165, 1)]
    Coprimes {unCoprimes = [(28,1),(33,1),(5,2)]}
    >>> splitIntoCoprimes [(360, 1), (210, 1)]
    Coprimes {unCoprimes = [(7,1),(5,2),(3,3),(2,4)]}

data Coprimes a b Source #

A list of pairwise coprime numbers with their multiplicities.

#### Instances

Instances details

(Eq a, GcdDomain a, Eq b, Num b) => Monoid (Coprimes a b) Source # |
Instance details Defined in Math.NumberTheory.Euclidean.Coprimes Methods mempty :: Coprimes a b Source # mappend :: Coprimes a b -> Coprimes a b -> Coprimes a b Source # mconcat :: [Coprimes a b] -> Coprimes a b Source #
(Eq a, GcdDomain a, Eq b, Num b) => Semigroup (Coprimes a b) Source # |
Instance details Defined in Math.NumberTheory.Euclidean.Coprimes Methods (<>) :: Coprimes a b -> Coprimes a b -> Coprimes a b Source # sconcat :: NonEmpty (Coprimes a b) -> Coprimes a b Source # stimes :: Integral b0 => b0 -> Coprimes a b -> Coprimes a b Source #
(Show a, Show b) => Show (Coprimes a b) Source # |
Instance details Defined in Math.NumberTheory.Euclidean.Coprimes Methods showsPrec :: Int -> Coprimes a b -> ShowS Source # show :: Coprimes a b -> String Source # showList :: [Coprimes a b] -> ShowS Source #
(Eq a, Eq b) => Eq (Coprimes a b) Source # |
Instance details Defined in Math.NumberTheory.Euclidean.Coprimes Methods (==) :: Coprimes a b -> Coprimes a b -> Bool Source # (/=) :: Coprimes a b -> Coprimes a b -> Bool Source #

unCoprimes :: Coprimes a b -> [(a, b)] Source #

Unwrap.

singleton :: (Eq a, GcdDomain a, Eq b, Num b) => a -> b -> Coprimes a b Source #

Wrap a non-zero number with its multiplicity into `Coprimes`.

    >>> singleton 210 1
    Coprimes {unCoprimes = [(210,1)]}

insert :: (Eq a, GcdDomain a, Eq b, Num b) => a -> b -> Coprimes a b -> Coprimes a b Source #

Add a non-zero number with its multiplicity to `Coprimes`.

    >>> insert 360 1 (singleton 210 1)
    Coprimes {unCoprimes = [(7,1),(5,2),(3,3),(2,4)]}
    >>> insert 2 4 (insert 7 1 (insert 5 2 (singleton 4 3)))
    Coprimes {unCoprimes = [(7,1),(5,2),(2,10)]}