## 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 *x _{i}* =

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

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

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

My Haskell solution (see http://bonsaicode.wordpress.com/2012/07/10/programming-praxis-sieving-for-totients/ for a version with comments):

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?

You sieve on primes, which means starting at 2.

Python 2.7 solution:

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

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

See http://docs.python.org/release/2.3.5/whatsnew/section-slices.html.

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

[…] Pages: 1 2 […]