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

Show a => Show (SmoothBasis a)

Methods

showsPrec :: Int -> SmoothBasis a -> ShowS

show :: SmoothBasis a -> String

showList :: [SmoothBasis a] -> ShowS

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

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

> 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 :: Integral 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.

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

smoothOverInRange :: 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.

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

smoothOverInRangeBF :: 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.

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