arithmoi-0.13.2.0: Efficient basic number-theoretic functions.

Copyright | (c) 2018 Frederick Schneider 2018-2019 Andrew Lelechenko
License | MIT
Maintainer | Frederick Schneider <frederick.schneider2011@gmail.com>
Safe Haskell | None
Language | Haskell2010

Math.NumberTheory.SmoothNumbers

Description

A smooth number is an number, which can be represented as a product of powers of elements from a given set (smooth basis). E. g., 48 = 3 * 4 * 4 is smooth over a set {3, 4}, and 24 is not.

Synopsis

- data SmoothBasis a
- unSmoothBasis :: SmoothBasis a -> [a]
- fromList :: (Eq a, GcdDomain a) => [a] -> SmoothBasis a
- isSmooth :: (Eq a, GcdDomain a) => SmoothBasis a -> a -> Bool
- smoothOver :: Integral a => SmoothBasis a -> [a]
- smoothOver' :: (Eq a, Num a, Ord b) => (a -> b) -> SmoothBasis a -> [a]

# Documentation

data SmoothBasis a Source #

An abstract representation of a smooth basis.

#### Instances

Instances details

Show a => Show (SmoothBasis a) Source # |
Instance details Defined in Math.NumberTheory.SmoothNumbers Methods showsPrec :: Int -> SmoothBasis a -> ShowS Source # show :: SmoothBasis a -> String Source # showList :: [SmoothBasis a] -> ShowS Source #

unSmoothBasis :: SmoothBasis a -> [a] Source #

Unwrap elements of a smooth basis.

fromList :: (Eq a, GcdDomain a) => [a] -> SmoothBasis a Source #

Build a `SmoothBasis` from a list of numbers, sanitizing it from duplicates, zeros and units.

    >>> fromList [2, 3]
    SmoothBasis {unSmoothBasis = [2,3]}
    >>> fromList [2, 2]
    SmoothBasis {unSmoothBasis = [2]}
    >>> fromList [1, 3]
    SmoothBasis {unSmoothBasis = [3]}

isSmooth :: (Eq a, GcdDomain a) => SmoothBasis a -> a -> Bool Source #

Check that a given number is smooth under a given `SmoothBasis`.

    >>> isSmooth (fromList [2,3]) 12
    True
    >>> isSmooth (fromList [2,3]) 15
    False

smoothOver :: Integral a => SmoothBasis a -> [a] Source #

Generate an infinite ascending list of smooth numbers over a given smooth basis.

This routine is more efficient than filtering with `isSmooth`.

    >>> take 10 (smoothOver (fromList [2, 5]))
    [1,2,4,5,8,10,16,20,25,32]

smoothOver' Source #

Arguments

:: (Eq a, Num a, Ord b) |
=> (a -> b) | Ideal norm
-> SmoothBasis a |
-> [a] |

A generalization of `smoothOver`, suitable for non-`Integral` domains. The first argument must be an appropriate Ideal norm function, like `norm` or `norm`.

This routine is more efficient than filtering with `isSmooth`.

    >>> import Math.NumberTheory.Quadratic.GaussianIntegers
    >>> take 10 (smoothOver' norm (fromList [1+ι,3]))
    [1,1+ι,2,2+2*ι,3,4,3+3*ι,4+4*ι,6,8]