Finding The Number Of Reduced Fractions

I've been working on this problem for the last two days. I feel like I'm dangerously close; but something is not quite clicking. Would love a fresh pair of eyes to run through this

Solution 1:

The number you need to compute is called Euler's Totient Function, the numbers of n's coprimes between 1 and n.

If the prime decomposotion of n is:

,

its Euler's totient function is:

The algorithm to compute it in pseudocode:

• φ = 1
• m = n
• For every prime number p less than or equal to sqrt(n):
  • If m divides p:
    • Multiply φ by p-1
    • Divide m by p-1
  • While m divides p:
    • Multiply φ by p
    • Divide m by p
• If m > 1:
  • // Note that at this point m must be a prime factor of n greater than sqrt(n)
  • Multiply φ by m-1

Solution 2:

All you need to is for the denominator supplied check to see if the gcd is 1 and if it is output to a list and then return the length of that list.

def proper_fractions(n):
    def gcd(x,y):
        while y:
            (x, y) = (y, x % y)
        return x
    if n <= 1:
        return 0
    else:
        count = 0
        for num in range(1,n):
            denom = gcd(n,num)
            if denom == 1:
                count += 1
        return count

Solution 3:

You should use Euler's totient function, as the user Anton has already stated. Here is one way to solve the problem. I've put some comments in the code.

def proper_fractions(n):
  distinct_prime_factors = set()   # use set to avoid duplicates
  totient_function = n
  if n == 1:
    totient_function = 0
  else:
    i = 2
    while i*i <= n:
      if n % i == 0:
        distinct_prime_factors.add(i)
        n = n/i
      else:
        i += 1
    if n > 1:
      distinct_prime_factors.add(n)   # picks up prime factors > sqrt(n)
    if len(distinct_prime_factors) == 0:   # empty set means denominator is prime
      totient_function = n - 1
    else:
      for p in distinct_prime_factors:
        totient_function = (totient_function*(p - 1))/p
  return totient_function

Euler's totient function uses the distinct prime factors. This is why it is better to use a set instead of a list, since sets don't allow for repeated elements.

Furthermore, after the while loop, it is important to add n to the set of prime factors if n is greater than 1. This is because the while loop terminates as soon as the prime factors are greater than the square root of n. For example, consider the number 77. The while loop will pick up 7, since 7*7 = 49, which is less than 77. However, it will not pick up 11, since 11*11 = 121, which is greater than 77.