[Edu-sig] Basic number theory w/ Python

[Kirby Urner]

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?