[Tutor] Basic number theory w/ Python
Kirby Urner
urnerk@qwest.net
Thu, 10 Jan 2002 22:35:40 -0800
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?