Copyright | (c) 2018 Frederick Schneider 2018-2019 Andrew Lelechenko |
---|---|
License | MIT |
Maintainer | Frederick Schneider <frederick.schneider2011@gmail.com> |
Safe Haskell | None |
Language | Haskell2010 |
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
Show a => Show (SmoothBasis a) Source # | |
Defined in Math.NumberTheory.SmoothNumbers showsPrec :: Int -> SmoothBasis a -> ShowS # show :: SmoothBasis a -> String # showList :: [SmoothBasis a] -> ShowS # |
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]
:: (Eq a, Num a, Ord b) | |
=> (a -> b) | |
-> 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]