arithmoi-0.11.0.0: Efficient basic number-theoretic functions.

Copyright (c) 2018 Frederick Schneider 2018-2019 Andrew Lelechenko MIT Frederick Schneider None 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

# Documentation

data SmoothBasis a Source #

An abstract representation of a smooth basis.

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

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]


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]