Math.NumberTheory.SmoothNumbers

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.

Documentation

data SmoothBasis a

An abstract representation of a smooth basis.

Instances

Show a => Show (SmoothBasis a)

Defined in Math.NumberTheory.SmoothNumbers

Methods

showsPrec :: Int -> SmoothBasis a -> ShowS

show :: SmoothBasis a -> String

showList :: [SmoothBasis a] -> ShowS

unSmoothBasis :: SmoothBasis a -> [a]

Unwrap elements of a smooth basis.

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

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

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]

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'

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]