arithmoi-0.8.0.0: Efficient basic number-theoretic functions.

Copyright (c) 2018 Frederick Schneider MIT Frederick Schneider Provisional Non-portable (GHC extensions) None Haskell2010

Math.NumberTheory.SmoothNumbers

Description

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.

Synopsis

# Create a smooth basis

data SmoothBasis a Source #

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

Instances
 Eq a => Eq (SmoothBasis a) Source # Instance detailsDefined in Math.NumberTheory.SmoothNumbers Methods(==) :: SmoothBasis a -> SmoothBasis a -> Bool #(/=) :: SmoothBasis a -> SmoothBasis a -> Bool # Show a => Show (SmoothBasis a) Source # Instance detailsDefined in Math.NumberTheory.SmoothNumbers MethodsshowsPrec :: Int -> SmoothBasis a -> ShowS #show :: SmoothBasis a -> String #showList :: [SmoothBasis a] -> ShowS #

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

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) Source #

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) Source #

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

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

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

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]