Project Euler Problem #71

April 9, 2010

Read the details of the problem here

Summary

Listing reduced proper fractions in ascending order of size.

Solution

This problem reminded me of the Achilles and the Tortoise Paradox in that everything must reach a half-way stage before reaching a final destination. As there are an infinite amount of half-way points you’d never arrive at the destination. In essence it’s possible to solve this problem by calculating the half-way points between the two fractions given…well, not exactly but it makes for a nice story!

In the realm of reduced fractions this is called a Farey Sequence. As you’ll see though they aren’t exactly half-way points, they are called mediants and are just created from adding the numerator and denominator of neighbouring terms.

So seeing how it works for this problem. The whole fractional space (if you can call it that) lives between 0 and 1 or, for this purpose, 0/1 and 1/1. This is a Farey sequence of order 1 (the highest denominator in use).

0                          1
-..........................-   
1                          1

Just partition the space according the mediant rules a/c + b/d = (a+b)/(c+d). This creates a Farey sequence of order 2.

0            1             1
-............_.............-   
1            2             1

This problem is interested in values less than 1/2 (as 3/7 < 1/2) so just partition again to the left hand side. Giving an order 3 sequence.

0     1      1             1
-....._......_.............-   
1     3      2             1

And again. This time to the right of the 1/3 as 2/5 > 1/3.

0     1  2   1             1
-....._.._..._.............-   
1     3  5   2             1

Repeat to the right of the 2/5 to get the 3/7 that the problem is expecting as the upper bound. This means that, in a Farey Sequence of order 7, 2/5 and 3/7 are neighboring terms (also known as a Farey Pair).

0     1  2 3 1             1
-....._.._._._.............-   
1     3  5 7 2             1

So, to solve this problem it’s just necessary to keep performing this calculation between 2/5 and 3/7, adding 3/7 each time to the resulting fraction, whilst the denominator doesn’t exceed 1,000,000.

So the next few terms would be:

    2/5 + 3/7 = 5/12,

    5/12 + 3/7 = 8/19,

    8/19 + 3/7 = 11/26, etc.

The coding is extremely straightforward.

def ( answer, c ) = [ 2, 5 ]
def ( b, d ) = [ 3, 7 ]

while (c + d <= 1000000) {
    answer += b
    c += d
}

This is another one of those Euler questions that goes to show it’s worth knowing a few little tricks like this rather than relying on brute force for a solution.

The program runs in 0.17 seconds, easily within my time limit.

Note: It’s actually not really necessary to write a program to solve this at all. From the algorithm above, it’s obvious that the solution is (2+3n)/(5+7n) where the denominator is limited by 1,000,000, and so 7n < 999,995. 999,992 is divisible by 7, giving a denominator of 999,997 and n =142856. Just plugging this into the formula for the numerator gives the answer.

Conclusion

As it was Groovy didn’t play any significant part in this solution. It just required simply addition which Groovy is quite capable of handling in a performant manner.

Advertisements

One Response to “Project Euler Problem #71”


  1. […] is really just a variant of Problem 71 that I solved using Farey Sequences. I found that I could use the same approach but the […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: