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 [e-mail] with your suggestions!

Comments

[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

[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]

[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;

[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)
        }
    }
}

[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

[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")
  }
}

[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