Project Euler — Problem 71 Solution

Problem

Con­sid­er 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 prop­er frac­tion.

If we list the set of reduced prop­er 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­ate­ly to the left of 3/7.

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

Solution

This prob­lem is fair­ly easy, giv­en 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 val­ue 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.