Results 1 to 3 of 3

Math Help - Euler totient function

  1. #1
    Junior Member
    Joined
    Feb 2006
    Posts
    32

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by jedoob View Post
    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)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by jedoob View Post
    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
    Last edited by CaptainBlack; March 25th 2007 at 08:30 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 5th 2010, 02:04 AM
  2. Euler's Totient Function
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: July 12th 2010, 10:41 AM
  3. Euler Totient Function
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: June 3rd 2010, 06:38 PM
  4. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 12th 2009, 07:11 PM
  5. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 8th 2008, 09:53 PM

Search Tags


/mathhelpforum @mathhelpforum