Let a and b be positive integers such that
43/197 < a/b < 17/77.
Find the minimum possible value of b.
If you know about
continued fractions then this is actually a pretty straightforward problem. Express 43/197 and 17/77 as continued fractions:
43/197: [0;4,1,1,2,1,1,3]
17/77: [0;4,1,1,8]
Then make a new continued fraction keeping matching terms and where the terms differ then increment the smaller one by 1 and stop.
Then the continued fraction for a/b becomes [0;4,1,1,3]. This is the continued fraction for 7/32.
What if you are like me and barely know of continued fractions? There is a fairly effective algorithm that can find the answer to the question with not too much work.
Start with r1 < a/b < r2 (all values assumed to be positive)
Is there at least one integer in the interval from r1 to r2?
If so set a/b equal to the smallest such integer and solve for a and b.
If not then take the reciprocals of everything (r1, r2, and a/b). Find the largest integer less than the new interval.
Then make a new r1, r2, and a/b fraction by subtracting that integer and head back to the start.
For this problem we start with 43/197 < a/b < 17/77
There is no integer in the interval.
Then 1/r2=77/17 and 1/r1=197/43 and 1/(a/b)=b/a.
4 is the largest integer less than 77/17.
Then 9/17 < a/(b-4a) < 25/43
There is no integer in the interval.
Then 1/r2=43/25 and 1/r1=17/9 and 1/(a/(b-4a))=(b-4a)/a.
1 is the largest integer less than 43/25.
Then 18/25 < (5a-b)/(b-4a) < 8/9
There is no integer in the interval.
Then 1/r2=9/8 and 1/r1=25/18 and 1/((5a-b)/(b-4a))=(b-4a)/(5a-b).
1 is the largest integer less than 9/8.
Then 1/8 < (2b-9a)/(5a-b) < 7/18
There is no integer in the interval.
Then 1/r2=18/7 and 1/r1=8 and 1/((2b-9a)/(5a-b))=(5a-b)/(2b-9a).
2 is the largest integer less than 18/7.
Then 4/7 < (23a-5b)/(2b-9a) < 6
There is an integer in the interval. The smallest is 1.
Then (23a-5b)/(2b-9a)=1 reduces to 32a=7b, which makes a/b=7/32.
Note, if we take some other integers in this interval, like 2, we get a different but not ideal answer. (23a-5b)/(2b-9a)=2 reduces to 41a=9b, implying a/b=9/41, which is precisely the second-best answer that Charlie's program found.