Farey Sequence | Efficient Python3 program to print Farey Sequence of order n ; Optimized function to print Farey sequence of order n ; We know first two terms are 0 / 1 and 1 / n ; For next terms to be evaluated ; Using recurrence relation to find the next term ; Print next term ; Update x1 , y1 , x2 and y2 for next iteration ; Driver Code
import math NEW_LINE def farey ( n ) : NEW_LINE INDENT x1 = 0 ; NEW_LINE y1 = 1 ; NEW_LINE x2 = 1 ; NEW_LINE y2 = n ; NEW_LINE print ( x1 , end = " " ) NEW_LINE print ( " / " , end = " " ) NEW_LINE print ( y1 , x2 , end = " " ) NEW_LINE print ( " / " , end = " " ) NEW_LINE print ( y2 , end = " ▁ " ) ; NEW_LINE x = 0 ; NEW_LINE y = 0 ; NEW_LINE while ( y != 1.0 ) : NEW_LINE INDENT x = math . floor ( ( y1 + n ) / y2 ) * x2 - x1 ; NEW_LINE y = math . floor ( ( y1 + n ) / y2 ) * y2 - y1 ; NEW_LINE print ( x , end = " " ) NEW_LINE print ( " / " , end = " " ) NEW_LINE print ( y , end = " ▁ " ) ; NEW_LINE x1 = x2 ; NEW_LINE x2 = x ; NEW_LINE y1 = y2 ; NEW_LINE y2 = y ; NEW_LINE DEDENT DEDENT n = 7 ; NEW_LINE print ( " Farey ▁ Sequence ▁ of ▁ order " , n , " is " ) ; NEW_LINE farey ( n ) ; NEW_LINE