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
  }