## Posts Tagged ‘totient’

### Programming Praxis – Sieving For Totients

July 10, 2012

In today’s Programming Praxis exercise, our goal is to calculate the totients of a given range of numbers using a sieve. Let’s get started, shall we?

Due to the way I structured my code, Data.Map is a little more convenient than Data.Vector (since Data.Vector lacks the equivalent of the adjust function).

`import qualified Data.Map as M`

The sieving can be solved easily with two folds. The outer one to check all the elements in the list, and the inner one to update all the multiples of a given index. One space-saving trick is to realize that you don’t need to treat i and its multiples differently, since i * (1 – 1/i) = i – i/i = i – 1. This saves a separate insert call.

```totients :: Integral a => a -> [a]
totients n = M.elems \$ foldl (\m i -> if m M.! i == i
then foldr (M.adjust (\x -> div (x*(i-1)) i)) m [i,2*i..n] else m)
(M.fromList \$ zip [0..n] [0..n]) [2..n]```

A test to see if everything is working properly:

```main :: IO ()
main = print \$ totients 100```

### Programming Praxis – Divisors And Totatives

November 26, 2010

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?

Some imports:

```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.