Program to find common fraction between min and max using given constraint in Python

Suppose we have two long integer values maximum and minimum. We have to find a common fraction n/d such that min <= d <= max. And |n/d - pi| is smallest. Here pi = 3.14159265... and if there are more than one fractions holding this condition, then return the fraction with smallest denominator.

So, if the input is like minimum = 1 maximum = 10, then the output will be 22/7.

To solve this, we will follow these steps −

• P := a fraction (5706674932067741 / 1816491048114374) - 3
• a := 0, b := 1, c := 1, d := 1
• farey := an array of pairs, it has two pairs initially (a, b) and (c, d)
• Loop through the following unconditionally -
  • f := b + d
  • if f > maximum - minimum, then
    • come out from the loop
  • e := a + c
  • insert pair (e, f) at the end of farey
  • if P < the value of (e/f), then
    • c := e and d := f
  • therwise,
    • a := e and b := f
• p_min := floor of (P * minimum)
• while minimum <= maximum, do
  • c := 0, d := 0
  • for each pair (a, b) in farey, do
    • if minimum + b > maximum, then
      • come out from the loop
    • if |(p_min + a)/ (minimum + b) - P| <|p_min / minimum - P|, then
      • c := a, d := b
      • come out from the loop
  • if d is same as 0, then
    • come out from the loop
  • p_min := p_min + c
  • o minimum := minimum + d
  • o return fraction (p_min + 3 * minimum) / minimum

Example

Let us see the following implementation to get better understanding −

from fractions import Fraction def solve(minimum, maximum):    P = Fraction(5706674932067741, 1816491048114374) - 3    a, b, c, d = 0, 1, 1, 1    farey = [(a,b),(c,d)]    while True:       f = b + d       if f > maximum - minimum:          break       e = a + c       farey.append((e, f))       if P < Fraction(e, f):          c, d = e, f       else:          a, b = e, f    p_min = int(P * minimum)    while minimum <= maximum:       c, d = 0, 0       for a, b in farey:          if minimum + b > maximum:             break          if abs(Fraction(p_min + a, minimum + b).real - P) < abs(Fraction(p_min, minimum).real - P): c, d = a, b break if d == 0: break p_min += c minimum += d return ("{}/{}".format(p_min + 3 * minimum, minimum)) minimum = 1 maximum = 10 print(solve(minimum, maximum))

Input

4, 27 

Output

22/7