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
    9
    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 07: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, 01:04 AM
  2. Euler's Totient Function
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: July 12th 2010, 09:41 AM
  3. Euler Totient Function
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: June 3rd 2010, 05:38 PM
  4. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 12th 2009, 06:11 PM
  5. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 8th 2008, 08:53 PM

Search Tags


/mathhelpforum @mathhelpforum