DAY 23
1

# 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)
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){
}
``````

#### 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);
``````

• Ruby
• JavaScript

# 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
}
``````