DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

dev.to staff
dev.to staff

Posted on

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!

Top comments (11)

Collapse
 
brightone profile image
Oleksii Filonenko • Edited on

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) :)

Collapse
 
jeffong profile image
Jeff Ong • Edited on

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

Collapse
 
swizzard profile image
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]
Collapse
 
choroba profile image
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;
Collapse
 
colorfusion profile image
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)
        }
    }
}

Collapse
 
larisho profile image
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
Collapse
 
earlware profile image
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...

Collapse
 
avalander profile image
Avalander • Edited on

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")
  }
}
Collapse
 
brightone profile image
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

πŸ‘‹ Hey, my name is Noah and I’m the one who set up this ad. My job is to get you to join DEV, so if you fancy doing me a favor, I’d love for you to create an account.

If you found DEV from searching around, here are a couple of our most popular articles on DEV: