22 lines
778 B
Python
22 lines
778 B
Python
from fractions import Fraction
|
|
|
|
|
|
class Fr(Fraction):
|
|
def __repr__(self):
|
|
return '(%s/%s)' % (self.numerator, self.denominator)
|
|
|
|
|
|
def farey(n, length=False):
|
|
if not length:
|
|
return [Fr(0, 1)] + sorted({Fr(m, k) for k in range(1, n+1) for m in range(1, k+1)})
|
|
else:
|
|
#return 1 + len({Fr(m, k) for k in range(1, n+1) for m in range(1, k+1)})
|
|
return (n*(n+3))//2 - sum(farey(n//k, True) for k in range(2, n+1))
|
|
|
|
if __name__ == '__main__':
|
|
print('Farey sequence for order 1 through 11 (inclusive):')
|
|
for n in range(1, 12):
|
|
print(farey(n))
|
|
print('Number of fractions in the Farey sequence for order 100 through 1,000 (inclusive) by hundreds:')
|
|
print([farey(i, length=True) for i in range(100, 1001, 100)])
|