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 # 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]

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]