If all the irreducible fractions between 0 and 1, with denominators at most 99, are listed in ascending order, which two fractions would be before and after 11/21? Determine which two fractions are adjacent to 34/87 in this listing.

I'm fairly certain this won't give the exact answer, but I was trying to think of an algorithm to start with any such fraction and get to the answer analytically, rather than brute force.

First thought:  Start with 11/21 = N/D, and multiply N and D by whatever maximizes D with D<100.  In this case 44/84.  Then vary N or D by 1, whichever produces the smallest percent change in the value of the fraction (since N<D it will always be D).  So the provisional answer with this algorithm is:
     44/85 and 44/83       (again, I'll be very surprised if this is the answer)

Next thought: multiply N and D by something that makes N an integer, and D an integer plus 1/2.
Example:  34/87 = 17/43.5  -->  17/44 and 17/43

Next thought:  find a multiplier, x, that produces a numerator (N*x) which is an integer, and a denominator (D*x) which is just slightly off from being an integer.  But I don't see a non brute force way to do that.

Posted by Larry on 2004-07-23 10:19:03