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 (9)
Rust:
Two beers for the
num
crate (forgcd
) :)A Javascript solution:
Test cases:
This is a pretty straight-forward solution using a counter. You can run this in vscode terminal as
node [file-name].js
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.
My first time writing in Golang, managed to figure out the basic syntax.
For testing
Clojure:
A Swift solution:
Output:
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...
Scala
Not much going on. Generate a sequence with all the numbers between
1
andn - 1
which greatest common denominator withn
is one and get the length of that sequence.Tests
Elixir:
Tests: