Results 1 to 3 of 3

Math Help - Number of positive integers less than 550 and relatively prime to 550

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    Number of positive integers less than 550 and relatively prime to 550

    550=2*5^2*11

    Is there an efficient way to do this without just multiplying all the combinations of the canonical decomposition?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by dwsmith View Post
    550=2*5^2*11

    Is there an efficient way to do this without just multiplying all the combinations of the canonical decomposition?
    Do you mean you want something more efficient than this?

    \displaystyle \varphi(550)=  550 \cdot \prod_{p|550} \left( 1-\frac{1}{p} \right)  = 550\left( 1-\frac{1}{2} \right)\left( 1-\frac{1}{5} \right)\left( 1-\frac{1}{11} \right) = 200

    If you're writing a program, then you can do a sieve. I don't know what else.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    I knew the phi function but I couldn't remember what it did. Thanks. I feel dumb now.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 29th 2011, 11:26 AM
  2. Replies: 1
    Last Post: May 16th 2011, 08:54 PM
  3. Replies: 2
    Last Post: March 1st 2011, 11:54 AM
  4. Sums of squares of positive integers prime to n
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 24th 2009, 12:15 AM
  5. Every Positive Number Has A Unique Positive Square Root
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: May 2nd 2008, 09:26 AM

/mathhelpforum @mathhelpforum