Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How it will be solved

  1. Sep 18, 2008 #1
    A fraction m / n is basic if 0 <= m < n and it is irreducible if gcd(m, n) = 1. Given a
    positive integer n, in this problem you are required to find out the number of irreducible
    basic fractions with denominator n .
    For example, the set of all basic fractions with denominator 12, before reduction to
    lowest terms, is
    Reduction yields
    Hence there are only the following 4 irreducible basic fractions with denominator 12
    Input
    Each line of the input contains a positive integer n (< 1000000000) and the input
    terminates with a value 0 for n (do not process this terminating value).
    Output
    For each n in the input print a line containing the number of irreducible basic fractions with
    denominator n
    Sample Input
    12
    123456
    7654321
    0
    Sample Output
    4
    41088
    7251444
     
  2. jcsd
  3. Sep 18, 2008 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    This makes no sense at all. Are you asking for a computer program to do that? If not, what do you mean by "input" and "output"?
     
  4. Sep 19, 2008 #3
    Well, computer program are usually easier math problems :) I believe he wants a computer program, but you can challenge yourself by finding a function f(x) such that it returns the number of irreducible basic fractions with denominator x.

    It looks like a fraction is simple if you can write m/n where gcd(m,n) = 1 and 0<m<n. Well if that is the case, then you're just looking for how many positive numbers are relatively prime to n that are less than n..

    If so, look up the euler phi function..
    http://en.wikipedia.org/wiki/Euler's_totient_function
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: How it will be solved
  1. How it will be solved (Replies: 1)

Loading...