## Sieving For Totients

### July 10, 2012

This is simple; x is the array of totients, each element of x is set to i in the first `do` loop, the second `do` loop finds each xi = i, and the multiples of i are visited in the third `do` loop:

```(define (totients n)   (let ((x (make-vector (+ n 1))))     (do ((i 0 (+ i 1))) ((< n i))       (vector-set! x i i))     (do ((i 2 (+ i 1))) ((< n i) x)       (when (= i (vector-ref x i))         (vector-set! x i (- i 1))         (do ((j (+ i i) (+ i j))) ((< n j))           (vector-set! x j             (* (vector-ref x j) (- 1 (/ i)))))))))```

Here’s an example:

```> (totients 100) #101(0 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8 12 10 22      8 20 12 18 12 28 8 30 16 20 16 24 12 36 18 24 16 40 12 42 20      24 22 46 16 42 20 32 24 52 18 40 24 36 28 58 16 60 30 36 32      48 20 66 32 44 24 70 24 72 36 40 36 60 24 78 32 54 40 82 24      64 42 56 40 88 24 72 44 60 46 72 32 96 42 60 40)```

You can run the program at http://programmingpraxis.codepad.org/jt4ydVju.

Pages: 1 2

### 9 Responses to “Sieving For Totients”

1. […] today’s Programming Praxis exercise, our goal is to calculate the totients of a given range of numbers […]

2. There’s a small error in the problem description. You say that all the multiples need to be multiplied by i – 1, but that should be (i – 1) / i (or 1 – 1/i, which is the same thing).

```import qualified Data.Map as M

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]
```
3. Sam Kennedy said

I don’t quite understand, starting at index 0, (0 – 1) / 0, instantly you have divide by zero, then (1 – 1) / 1 = 0, you multiply everything in the array by zero, ending up with an array full of zeroes.

I feel I’m missing something here?

4. programmingpraxis said

You sieve on primes, which means starting at 2.

5. Mike said

Python 2.7 solution:

```def totient_sieve(n):
''' return list of totient(i) for i from 0 to n-1.

>>> totient_sieve(12)
[0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10]
'''

tots = range(n)
for i in range(2, n):
if tots[i] == i:
tots[i::i] = (x*(i-1)/i for x in tots[i::i])
```
6. programmingpraxis said

@Mike: What is the meaning of tots[i::i] on line 11 of your script?

7. Mike said

@praxis: tots is a list, tots[i::i] is a ‘slice’ of that list. Slice syntax is basically list_like_object[ start : stop : step ]. If the start or stop value is omitted, it defaults to the beginning or end of the list. An ommitted step defaults to 1.

In tots[i::i], the starting index is ‘i’, the stoping index is omitted, and the step is ‘i’. So tots[i::i] is a slice that refers to every i-th element of ‘tots’ starting at element ‘i’ and going to the end.

The right hand side of line 11 is a generator expression that lazily returns each element of the tots[i::i] multiplied by (i-1)/i.

Line 11 is an assignment to a slice, which assigns successive values from the thing on the right to successive elements of the slice on the left.

8. programmingpraxis said

I didn’t know about the step parameter. Thank you.

9. […] Pages: 1 2 […]