A result of number theory is any positive integer is the sum of the totients of its factors. What does that mean? The totient of n is the number of positives less than n, including 1, and which are relatively prime to n, i.e. have no factors in common with n other than 1. So, for example, 28 has no factors in common, other than 1, with the following positive numbers < 28: [1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27] The number of such numbers is the totient of n, and is simply the length of this list, i.e. 12. So totient(28)==12. Defining totient(n) is easy (for small n) if we have a way to assure gcd(i,n)==1, 0<i<n. That's where the gcd function comes in (see below -- a paradigm Python program [1]). If you take all the factors of 28 (including both 1 and 28), compute their totients, and add 'em all up, you should get 28. And so for any positive integer.
factors(28) [1, 2, 4, 7, 14, 28]
map(totient,factors(28)) [1, 1, 2, 6, 6, 12]
1+1+2+6+6+12 28
Here are some functions to check this out for low (small) positive integers: from operator import add def gcd(a,b): "greatest common divisor of a,b" while b: a, b = b, a%b return a def factors(n): "return list of factors of n" return [i for i in range(1,n+1) if n%i==0] def sumtots(n): "sum the totients of n's factors" return reduce(add,[totient(i) for i in factors(n)]) Usage:
sumtots(28) 28 sumtots(100) 100 sumtots(120383) 120383
Kirby [1] my recollection is this simple Pythonic form of Euclid's Algorithm was first presented by Guido himself -- is this correct?