In today’s Programming Praxis exercise,our goal is to make a small library to compute the following of a number: the divisors, the sum of the divisors, the number of divisors, the totatives and the totient. Let’s get started, shall we?
import Data.List import Data.Numbers.Primes import Data.Ratio
Calculating the divisors of a number could be done the compact but naive way (divisors n = filter ((== 0) . mod n) [1..n]), but let’s go with the slightly longer but more efficient version of multiplying every combination of prime factors.
divisors :: Integral a => a -> [a] divisors = nub . sort . map product . subsequences . primeFactors
Getting the sum of divisors is trivial.
divisorSum :: Integral a => a -> a divisorSum = sum . divisors
For the amount of divisors we’ll ignore the trivial method (length . divisors) and go with the more efficient algorithm.
divisorCount :: Integral a => a -> Int divisorCount = product . map (succ . length) . group . primeFactors
The totatives can be be trivially calculated using trial division.
totatives :: Integral a => a -> [a] totatives n = filter ((== 1) . gcd n) [1..n]
For the totient there is also a better way than the trivial one (length . totatives):
totient :: (Integral a, Integral b) => a -> b totient n = floor . product $ n % 1 : [1 - 1 % f | f <- nub $ primeFactors n]
As usual, some tests to see if everything is working properly:
main :: IO () main = do print $ divisors 60 == [1,2,3,4,5,6,10,12,15,20,30,60] print $ divisorSum 60 == 168 print $ divisorCount 60 == 12 print $ totatives 30 == [1,7,11,13,17,19,23,29] print $ totient 30 == 8 print $ totient 60 == 16
Looks like it is, and at five lines of code I’d call this a pretty small library 🙂 Fortunately, the non-trivial algorithms don’t add much in the way of length. Sure, the lines are a little longer, but they’re all still one-liners. I’d say it’s worth it for the improved speed.