theburningmonk.com

Prob­lem

Con­sider the frac­tion, n/d, where n and d are pos­i­tive inte­gers. If n < d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper frac­tions for d <= 8 in ascend­ing order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that 2/5 is the frac­tion imme­di­ately to the left of 3/7.

By list­ing the set of reduced proper frac­tions for d <= 1,000,000 in ascend­ing order of size, find the numer­a­tor of the frac­tion imme­di­ately to the left of 3/7.

Solu­tion

This prob­lem is fairly easy, given that the answer we’re look­ing for much be very close to 3 / 7 (0.4285714286) I sim­ply iter­ate through the denom­i­na­tors, d, and find the clos­est numer­a­tor, n, which will pro­duce a value less than 3 / 7. Then fil­ter the set so we end up with only the n, d pairs that have a GCD of 1 and pick the numer­a­tor from the n, d pair whose n / d frac­tion is the biggest.