23 - Number of Proper Fractions with Denominator d

Don’t say so much, just coding…

Instruction

If n is the numerator and d the denominator of a fraction, that fraction is defined a (reduced) proper fraction if and only if GCD(n,d)==1.

For example 5/16 is a proper fraction, while 6/16 is not, as both 6 and 16 are divisible by 2, thus the fraction can be reduced to 3/8.

Now, if you consider a given number d, how many proper fractions can be built using d as a denominator?

For example, let’s assume that d is 15: you can build a total of 8 different proper fractions between 0 and 1 with it: 1/15, 2/15, 4/15, 7/15, 8/15, 11/15, 13/15 and 14/15.

You are to build a function that computes how many proper fractions you can build with a given denominator:

The order of the permutations doesn’t matter.

proper_fractions(1)==0
proper_fractions(2)==1
proper_fractions(5)==4
proper_fractions(15)==8
proper_fractions(25)==20

Be ready to handle big numbers.

Ruby

Init

def proper_fractions(n)
  #your code here
end

Sample Testing

Test.assert_equals(proper_fractions(1),0)
Test.assert_equals(proper_fractions(2),1)
Test.assert_equals(proper_fractions(5),4)
Test.assert_equals(proper_fractions(15),8)
Test.assert_equals(proper_fractions(25),20)

Javascript

Init

function properFractions(n){
  //your code here
}

Sample Testing

Test.assertEquals(properFractions(1),0);
Test.assertEquals(properFractions(2),1);
Test.assertEquals(properFractions(5),4);
Test.assertEquals(properFractions(15),8);
Test.assertEquals(properFractions(25),20);

---

Thinking

想法(1): 一開始我是直接暴力破解的，但發現時間複雜度很高，所以沒過 ·＿＿·
想法(2): 其實題目就是 1 ~ N 中與 N 互質的數，後來找到原來是 歐拉函示(?)

圖片來源：Unsplash Annie Spratt

Hint & Reference

• Ruby
  • Ruby - apidock doc Rational
• JavaScript
  • JS - MDN Math.sqrt()

Solution

Ruby

# Solution 1
def proper_fractions(n)
  return 0 if n == 1

  result = n
  (2..Math.sqrt(n).to_i).each{ |x|
    if n % x < 1
      n = n / x while n % x < 1 
      result = result - result / x
    end
  }
    
  result = result - result / n if n > 1
  result
end

Javascript

// Solution 1
function properFractions(n){
  if (n === 1) return 0;

  let res = n, a = n;
  for(let i = 2; i <= Math.sqrt(a); i++) {
    if(a % i === 0) {
      res = res / i * (i - 1);
      while(a % i === 0) a /= i;
    }
  }

  if(a > 1)
    res = res / a * (a - 1)
  
  return res
}