Thread: Euler totient function

Hi,

Can someone please tell me how to compute the Euler totient function for large values of n?

e.g n=3800.

Originally Posted by jedoob

Hi,

Can someone please tell me how to compute the Euler totient function for large values of n?

e.g n=3800.

If n>1
Factorize,
n=p_1^a_1 p_2^a_2 *...* p_n ^ a_n

Then,

phi(n) = n*(1-1/p_1)(1-1/p_2)*...*(1-1/p_n)

Originally Posted by jedoob

Hi,

Can someone please tell me how to compute the Euler totient function for large values of n?

e.g n=3800.

Me I fire up Euler and type:

Code:

>load "C:\Documents and Settings\CB\My Programs\Euler23\Euler Utils\number theory.e";
>
>
>EulerTotient(3800)
         1440 
>

Where EulerTotient is defined as:

Code:

 
function EulerTotient(n)
##
## Function to calculate the Euler Totient
## function of its argument
##
## The Euler Totient function of N returns the number
## of integers coprime to N and less than N (counting 1)
##
## Abromowitz and Stegun Section 24.3.2 gives:
##
## phi(N)=N.prod[(1-1/p),p|N]
##
## that is it is N times the product over primes p which divide
## N of (1-1/p).
##
## This is used in Eulers extension to Fermat's little
## theorem:
##
## if gcd(a,n)=1, a^phi(n) = 1 (mod n).
##
## CaptainBlack 2003
##
  fctrs=factor1(n); ..gives the prime factorisation of n with muliplicities
  fctrs=fctrs(:,1)'; ..just keep the distinct primes
 
  product=n*prod(1-1/fctrs); 
 
  return round(product,0)  ..round to nearest integer incase or rounding errors in float calculations
endfunction;

Note the comments are longer than the code!

RonL