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

Posted by programmingpraxis
Filed in Exercises
9 Comments »

9 Responses to “Sieving For Totients”

  1. Programming Praxis – Sieving For Totients « Bonsai Code said
    July 10, 2012 at 11:11 AM

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

  2. Remco Niemeijer said
    July 10, 2012 at 11:12 AM

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

    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
    July 10, 2012 at 1:48 PM

    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
    July 10, 2012 at 1:51 PM

    You sieve on primes, which means starting at 2.

  5. Mike said
    July 10, 2012 at 7:38 PM

    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])
	return tots
  6. programmingpraxis said
    July 10, 2012 at 7:56 PM

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

  7. Mike said
    July 11, 2012 at 1:52 AM

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

  8. programmingpraxis said
    July 11, 2012 at 12:57 PM

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

Leave a comment