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:
```python
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.

Edit: to be extra precise, the term should be "reduced" fractions, thanks to [girianshiido](http://www.codewars.com/users/girianshiido) for pointing this out and sorry for the use of an improper word :)

Source: codewars | Difficulty: MEDIUM
Tags: Fundamentals

Mathematics

Starter code: def proper_fractions(n):
	

Solutions:
def proper_fractions(n):
	phi = n > 1 and n
	for p in range(2, int(n ** 0.5) + 1):
		if not n % p:
			phi -= phi // p
			while not n % p:
				n //= p
	if n > 1:
		phi -= phi // n
	return phi


def proper_fractions(n):
	factors = set()
	i = 2
	input = n
	while i * i <= input:
		if input % i == 0:
			factors.add(i)
			input = input // i
		else:
			i = i + 1
	factors.add(input)
	result = n
	for j in factors:
		result = result * (1 - 1 / j)
	return int(result)


def euler(n):
	res = 1.0 * n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n / p
			res *= 1.0 - 1.0 / p
		p += 1
	if n > 1:
		res *= 1.0 - 1.0 / n
	return int(res)

def proper_fractions(d):
	if d == 1:
		return 0
	return euler(d)


from fractions import Fraction

def proper_fractions(n):
	res = Fraction(n)
	for i in range(2, int(n ** 0.5) + 1):
		if n % i:
			continue
		while not n % i:
			n //= i
		res *= Fraction(i - 1, i)
		if n == 1:
			break
	else:
		res *= Fraction(n - 1, n)
	return res


def proper_fractions(n):
	if n < 3:
		return n - 1
	(s, t, i) = ([], 1, 2)
	while True:
		while n % i == 0:
			(t, s, n) = (t * (i if i in s else i - 1), s + [i], n // i)
		if i * i > n:
			return t * (n - 1) if n > 1 else t
		i += 1


import math

def Factor(n):
	(a, d) = ([], 2)
	while d * d <= n:
		if n % d == 0:
			a.append(d)
			n //= d
		else:
			d += 1
	if n > 1:
		a.append(n)
	return a

def proper_fractions(n):
	if n == 1:
		return 0
	(used, k) = ([], 1)
	for i in Factor(n):
		if i not in used:
			used.append(i)
			k *= math.pow(i, Factor(n).count(i)) - math.pow(i, Factor(n).count(i) - 1)
	return k


def unique_prime_factors(n):
	i = 2
	factors = set()
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.add(i)
	if n > 1:
		factors.add(n)
	return factors

def proper_fractions(n):
	if n == 1:
		return 0
	output = n
	for p in unique_prime_factors(n):
		output //= p
		output *= p - 1
	return output


import math

def proper_fractions(n):
	(divisors, final, unique, i) = ([], [], [], 1)
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				divisors.append(i)
			else:
				divisors.extend([i, n / i])
		i = i + 1
	divisors.sort()
	if len(divisors) <= 2:
		return n - 1
	(divisors.pop(0), divisors.pop())
	for (num, item) in enumerate(divisors):
		for x in divisors[0:num]:
			if not item % x:
				break
		else:
			unique.append(item)
	for (num, item) in enumerate(unique):
		cache = n / item
		for x in unique[0:num]:
			cache = cache - cache / x
		final.append(cache)
	return n - sum(final)


def proper_fractions(n):
	if n == 1:
		return 0
	res = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n /= i
			res -= res / i
		i += 1
	if n > 1:
		res -= res / n
	return int(res)