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.
Programming Praxis 
[…] 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):
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]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 […]