Hi,

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

e.g n=3800.

Printable View

- March 25th 2007, 04:56 AMjedoobEuler totient function
Hi,

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

e.g n=3800. - March 25th 2007, 05:07 AMThePerfectHacker
- March 25th 2007, 07:10 AMCaptainBlack
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

>

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;

RonL