Math.NumberTheory.SmoothNumbers

A smooth number is an integer, 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.

Create a smooth basis

data SmoothBasis a

An abstract representation of a smooth basis. It consists of a set of coprime numbers ≥2.

Instances

Eq a => Eq (SmoothBasis a)

Defined in Math.NumberTheory.SmoothNumbers

Methods

(==) :: SmoothBasis a -> SmoothBasis a -> Bool

(/=) :: SmoothBasis a -> SmoothBasis a -> Bool

Show a => Show (SmoothBasis a)

Defined in Math.NumberTheory.SmoothNumbers

Methods

showsPrec :: Int -> SmoothBasis a -> ShowS

show :: SmoothBasis a -> String

showList :: [SmoothBasis a] -> ShowS

fromSet :: Euclidean a => Set a -> Maybe (SmoothBasis a)

Build a SmoothBasis from a set of coprime numbers ≥2.

>>> import qualified Data.Set as Set
>>> fromSet (Set.fromList [2, 3])
Just (SmoothBasis [2, 3])
>>> fromSet (Set.fromList [2, 4]) -- should be coprime
Nothing
>>> fromSet (Set.fromList [1, 3]) -- should be >= 2
Nothing

fromList :: Euclidean a => [a] -> Maybe (SmoothBasis a)

Build a SmoothBasis from a list of coprime numbers ≥2.

>>> fromList [2, 3]
Just (SmoothBasis [2, 3])
>>> fromList [2, 2]
Just (SmoothBasis [2])
>>> fromList [2, 4] -- should be coprime
Nothing
>>> fromList [1, 3] -- should be >= 2
Nothing

fromSmoothUpperBound :: Integral a => a -> Maybe (SmoothBasis a)

Build a SmoothBasis from a list of primes below given bound.

>>> fromSmoothUpperBound 10
Just (SmoothBasis [2, 3, 5, 7])
>>> fromSmoothUpperBound 1
Nothing

Generate smooth numbers

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

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

>>> import Data.Maybe
>>> take 10 (smoothOver (fromJust (fromList [2, 5])))
[1, 2, 4, 5, 8, 10, 16, 20, 25, 32]

smoothOverInRange :: forall a. Integral a => SmoothBasis a -> a -> a -> [a]

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

It may appear inefficient for short, but distant ranges; consider using smoothOverInRangeBF in such cases.

>>> import Data.Maybe
>>> smoothOverInRange (fromJust (fromList [2, 5])) 100 200
[100, 125, 128, 160, 200]

smoothOverInRangeBF :: forall a. Integral a => SmoothBasis a -> a -> a -> [a]

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

It is inefficient for large or starting near 0 ranges; consider using smoothOverInRange in such cases.

Suffix BF stands for the brute force algorithm, involving a lot of divisions.

>>> import Data.Maybe
>>> smoothOverInRangeBF (fromJust (fromList [2, 5])) 100 200
[100, 125, 128, 160, 200]