# Daily Challenge #78 - Number of Proper Fractions with Denominator d

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:

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

This challenge today comes from GiacomoSorbi at CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

### Discussion  E. Choroba

The number of proper fractions is the number of numbers in 1 .. N-1 that are coprime with N, i.e. whose greatest common divisor with N is 1.

``````#!/usr/bin/perl
use warnings;
use strict;

sub gcd {
my (\$x, \$y) = @_;
(\$x, \$y) = (\$y, \$x) if \$x > \$y;

return \$y unless \$x;

return gcd(\$y - (\$x * int(\$y / \$x)), \$x)
}

sub proper_fractions {
my (\$n) = @_;
grep 1 == gcd(\$n, \$_), 1 .. \$n - 1
}

use Test::More tests => 5;

is proper_fractions(1), 0;
is proper_fractions(2), 1;
is proper_fractions(5), 4;
is proper_fractions(15), 8;
is proper_fractions(25), 20;
`````` sam
``````import GHC.Real (Ratio(..))

isProper n x = let (a :% b) = (x / n) :: Rational
in if b == n then True else False

properFractions n = length [a / n | a <- [1..n], isProper n a]
`````` Oleksii Filonenko

Rust:

``````use num::Integer;

fn proper_fractions(d: usize) -> usize {
(1..d).filter(|n| d.gcd(n) == 1).count()
}

#[cfg(test)]
mod tests {
use super::*;

#[test]
fn test_examples() {
assert_eq!(proper_fractions(0), 0);
assert_eq!(proper_fractions(1), 0);
assert_eq!(proper_fractions(2), 1);
assert_eq!(proper_fractions(5), 4);
assert_eq!(proper_fractions(15), 8);
assert_eq!(proper_fractions(25), 20);
}
}
``````

Two beers for the `num` crate (for `gcd`) :) Jeff Ong

A Javascript solution:

``````const gcd = (n, d) => {
return d === 0 ? n : gcd(d, n % d);
}

const proper_fractions = (d) => {
if (d === 0 || d === 1) {
return 0;
}
if (d === 2) {
return 1;
}
let count = 0;
let n = 0;
while (n < d) {
if (gcd(n, d) === 1) {
count++;
}
n++;
}
return count;
}

console.log('Test cases');
console.log(`if d = 1, result: \${proper_fractions(1)}`);
console.log(`if d = 2,  result: \${proper_fractions(2)}`);
console.log(`if d = 5,  result: \${proper_fractions(5)}`);
console.log(`if d = 15, result: \${proper_fractions(15)}`);
console.log(`if d = 25, result: \${proper_fractions(25)}`);
``````

Test cases:

``````if d = 1, result: 0
if d = 2,  result: 1
if d = 5,  result: 4
if d = 15, result: 8
if d = 25, result: 20
``````

This is a pretty straight-forward solution using a counter. You can run this in vscode terminal as `node [file-name].js` Michael Kohl

F#

``````module DailyChallenge

let rec gcd x y =
if y = 0 then x
else gcd y (x % y)

let properFractions d =
seq { 1..d - 1 }
|> Seq.filter (fun n -> gcd d n = 1)
|> Seq.length
``````

Alternatively one could write `properFractions` using a query expression:

``````let properFractions d =
query {
for n in 1..d - 1 do
where (gcd n d = 1)
count
}
``````

Tests:

``````module DailyChallengeTest

open FsUnit.Xunit
open Xunit
open DailyChallenge

[<Fact>]
let ``0 has no proper fractions`` () =
properFractions 0 |> should equal 0

[<Fact>]
let ``1 has no proper fractions`` () =
properFractions 1 |> should equal 0

[<Fact>]
let ``5 has 4 proper fractions`` () =
properFractions 5 |> should equal 4

[<Fact>]
let ``15 has 8 proper fractions`` () =
properFractions 15 |> should equal 8

[<Fact>]
let ``25 has 20 proper fractions`` () =
properFractions 25 |> should equal 20
`````` Melvin Yeo

My first time writing in Golang, managed to figure out the basic syntax.

``````package main

func gcd(a int, b int) int {
if b == 0 {
return a
}

return gcd(b, a%b)
}

func properFractions(denom int) int {
results := 0

for i := 1; i < denom; i++ {
if gcd(denom, i) == 1 {
results++
}
}

return results
}

func main() {

}
``````

For testing

``````package main

import "testing"

func TestProperFractions(t *testing.T) {
params := map[int]int{
1:  0,
2:  1,
5:  4,
15: 8,
25: 20,
}
for key, value := range params {
result := properFractions(key)

if result != value {
t.Errorf("Incorrect answer for %d, expected: %d, got: %d", key, value, result)
}
}
}

`````` EarlWare

A Swift solution:

``````import Foundation

/*
gcdRecurse:  finds GCD of two numbers using the recursive algorithm

@param num: positive Int to find GCD of
@param num2: second positive Int to find GCD of

@return Int which is the GCD of num & num2
*/
func gcdRecurse(_ num:Int, _ num2:Int) -> Int {
let remainder = (num2 % num)

if remainder != 0 {
return gcdRecurse(remainder, num)
} else {
return num
}
}

/*
properFractions:  Challenge function, finds total number of proper fractions possible for a given number.

@param n: positive Int to find number of fractions for.

@return Int which is the total number of proper fractions.
*/
func properFractions(_ num:Int) -> Int {
var count = 0

for n in 1..<num {
if (gcdRecurse(num, n) == 1) {
count += 1
}
}

return count
}

print("Example 1:   1   ->  ", properFractions(1))     //  0
print("Example 2:   2   ->  ", properFractions(2))     //  1
print("Example 3:   5   ->  ", properFractions(5))     //  4
print("Example 4:   15  ->  ", properFractions(15))    //  8
print("Example 4:   25  ->  ", properFractions(25))    //  20

print("\n\nPassed all tests:    ", (properFractions(1) == 0 &&
properFractions(2) == 1 &&
properFractions(5) == 4 &&
properFractions(15) == 8 &&
properFractions(25) == 20), "\n\n")

``````

Output:

``````Example 1:   1   ->   0
Example 2:   2   ->   1
Example 3:   5   ->   4
Example 4:   15  ->   8
Example 4:   25  ->   20

Passed all tests:     true

Program ended with exit code: 0
``````

Had to implement a GCD function, as I didn't find one in the standard Swift library(if anyone knows different, let me know!)

Otherwise pretty straight forward, choose to go with brute force for-loop and a counter, as I found after some testing the array functions like .filter() / .map() / .reduce() are SCARY slow... Avalander

### Scala

``````def properFractions (n: Int): Int = {
val abs_n = Math.abs(n)
val propers = for {
x <- 1 until n
if gcd(Math.abs(x), abs_n) == 1
} yield x
propers.length
}

def gcd(x: Int, y: Int): Int =
if (y == 0) x
else gcd(y, x % y)
``````

Not much going on. Generate a sequence with all the numbers between `1` and `n - 1` which greatest common denominator with `n` is one and get the length of that sequence.

#### Tests

``````class FractionSpec extends FunSuite {
test("properFractions") {
assert(properFractions(1) == 0, "No proper fractions with denominator 1")
assert(properFractions(2) == 1, "1 proper fraction with denominator 2")
assert(properFractions(5) == 4, "4 proper fractions with denominator 5")
assert(properFractions(15) == 8, "8 proper fractions with denominator 15")
assert(properFractions(25) == 20, "20 proper fractions with denominator 25")
}
}
`````` Gab

Clojure:

``````(defn get-divisors [num]
"Returns sorted list of divisors"
(for [x (range 1 num)
:when (= (mod num x) 0)]
x))

(defn can-reduce? [num denom]
"Returns true if fraction can be reduced, otherwise false"
(first
(filter #(= (mod num %) 0) (rest (get-divisors denom)))))

(defn proper-fractions [denom]
"Returns the number of proper fractions that
can be created with the given denominator"
(count
(filter #(not (can-reduce? % denom)) (range 1 denom))))

(proper-fractions 1)
;; 0
(proper-fractions 2)
;; 1
(proper-fractions 5)
;; 5
(proper-fractions 15)
;; 8
(proper-fractions 25)
;; 20
`````` Oleksii Filonenko

Elixir:

``````defmodule Day78 do
@spec proper_fractions(pos_integer) :: non_neg_integer
def proper_fractions(1), do: 0
def proper_fractions(denom) when denom > 1 do
Enum.count(1..denom, &(Integer.gcd(&1, denom) == 1))
end
end
``````

Tests:

``````defmodule Day78Test do
use ExUnit.Case
import Day78, only: [proper_fractions: 1]

test "1/1 is improper" do
assert proper_fractions(1) == 0
end

test "2/1 is proper" do
assert proper_fractions(2) == 1
end

test "other common cases" do
assert proper_fractions(5) == 4
assert proper_fractions(15) == 8
assert proper_fractions(25) == 20
end

test "works only with positive numbers" do
assert_raise FunctionClauseError, fn -> proper_fractions(0) end
assert_raise FunctionClauseError, fn -> proper_fractions(-1) end
end
end
``````