Sieving For Totients

July 10, 2012

The totient of a number n is the count of the numbers less than n that are coprime to it; two numbers are coprime if they have no common factor other than 1. For instance, the totient of 30 is 8, since the numbers 1, 7, 11, 13, 17, 19, 23 and 29 are coprime to 30. The totient function was discovered by Leonhard Euler, and it pops up in all kinds of strange places in number theory; for instance, the totatives of 30 are the spokes on a 2,3,5 factorization wheel. We have seen the totient function in a previous exercise.

If you want to know the totient of a single number m, the best way to find it is to factor n and take the product of 1 less than each factor; for instance, 30 = 2 * 3 * 5, and subtracting 1 from each factor, then multiplying, gives the totient 1 * 2 * 4 = 8. But if you want to find the totients of all the numbers less than a given n, a better approach than factoring each of them is sieving. The idea is simple: Set up an array X from 0 to n, store i in each Xi, then run through the array starting from 0 and whenever Xi = i loop over the multiples of i, multiplying each by i − 1.

Your task is to write a function that computes all the totients less than n by sieving. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

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

    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

    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])
    	return tots
    
  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.

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

  8. programmingpraxis said

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 611 other followers

%d bloggers like this: