Problem 73 of Project Euler is the third problem in a row which treats ordering proper fractions. The problem description reads

Consider the fraction,n/d, wherenanddare positive integers. Ifn<dand HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions ford≤ 8 in ascending 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 there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions ford≤ 12,000?

Note: The upper limit has been changed recently.

I solved this in two different ways. Due to the small upper bound I attacked it bruteforce and with a somewhat smarter solution using Farey sequences. Something I have heard mentioned in many previous solutions but only just now started reading up on.

## Brute Force solution

The brute force solution is pretty straight forward. Looping through all possible denominators and counting all the numerators that fits the requirement. Nothing fancy just a whole lot of computing power. My C# implementation looks like

int a = 3; int b = 2; int limit = 12000; int result = 0; for (int d = 5; d <= limit; d++) { for (int n = d / a + 1; n < (d - 1) / b + 1; n++) { if (gcd(n, d) == 1) result++; } }

Accordingly running this code gives me the following result.

There are 7295372 proper fractions between 1/3 and 1/2 Solution took 1787 ms

Not really impressive using almost 2 seconds to solve this problem. We must be able to solve this faster.

## Farey Sequences

Farey sequences is something that I just discovered, nonetheless I find them very curious. A farey of order n is the sequence of ordered proper reduced fractions between 0 and 1, which has a denominator less than or equal to n. Such an example is given in the problem description which lists F_{8}.

The property that we need here is the fact that when we have two adjacent fractions a/b and c/d in a farey sequence of order n the next one e/f can be calculated as

I found these on wikipedia, and to be honest I haven’t found a good source to study this further, at least not one I found approachable. But assuming that it is correct, This means that if we can find the first two fractions we can enumerate through the rest of the fractions until we reach 1/2.

I found the next in the sequence by trial and error. We know that two terms a/b and c/d are adjacent if and only if b*c – a*d = 1. This is true for 1/3 and 4000/11999.

Once we have that we can make an implementation which looks like

int limit = 12000; int a = 1; int b = 3; int c = 4000; int d = 11999; int result = 0; while (!(c == 1 && d == 2)) { result++; int k = (limit + b) / d; int e = k * c - a; int f = k * d - b; a = c; b = d; c = e; d = f; }

This gives the following result

There are 7295372 proper fractions between 1/3 and 1/2 Solution took 69 ms

which is significantly faster than the brute force solution.

## Wrapping up

I have come up with two solutions, one using brute force and one using Farey sequences. The latter building on something I definitely need to study more to understand it fully. There is a solution file on the Project Euler website which gives another and faster solution, but I must admit that I can’t even begin to explain the theory they are using for that. So I will leave that as an option for you to check out.

The source code can be found here for you to study. As usual comments, questions and other solutions are welcome, and so “saying hi” as well. Just leave a comment to the post.

This blog image today is a rendering of ford circles which are closely related to Farey sequences.

The brute force solution is acting weird again 🙂

Some elementary math behind standard Farey sequences is reviewed in http://arxiv.org/abs/0801.1981 , Section 3, and in http://arxiv.org/abs/math/0411026 , Remark 7.10.

To answer your question just theoretically, you can use Remark 7.10(ii)(a) of http://arxiv.org/abs/math/0411026 , under m=n-1, twice or to combine it for two fractions thus obtaining a reduced formula.

Hi Rory

Thanks for the multiple comments and the links. I haven’t had the time to check them out in detail yet. They look good though and I am looking forward to read them.

/Kristian

Hi Kristian,

Could you please explain how you came up with values of n in the brute-force solution? I am having trouble understanding it.

Thanks

Anant

Yes of course. It is not exactly rocket science, but I can see that it might be a bit difficult to read.

Since we want to investigate fractions larger than 1/3 the closest thing we can get to that with for a given denominator d is d/3, since that might actually be less than 1/3, we add one.

The same goes for the upper bound, we search until we reach a fraction of 1/2, which for the denominator d is when n reaches d/2.

I hope this helps you, otherwise just ask again.

/Kristian

Thanks Krisitan. Yes it helped.

Just a quick note: there’s no need to keep track of the numerators (a & c) at all. They’re not needed to calculate the denominators, and you can simply stop when the denominator (d) is 2, since there’s only one possible numerator (which is 1). Should about half the run time.

I made one based on Mobius Inverse. result in 0.006 second.

http://pastebin.com/Xny8N8Vb

Here is a recursive version using Farey Neighbor property as defined in Wikipedia.

if p/q is between a/b and c/d, and neighbor to both then p/q = (a+c)/(b+d).

static int K_Limit = 12000;

static void makeFareyNeighbor(int a, int b, int c, int d, int& count)

{

if ((b + d) <= K_Limit)

{

count++;

makeFareyNeighbor(a, b, (a + c), (b + d), count);

makeFareyNeighbor((a + c), (b + d), c, d, count);

}

}

void ProjectEuler073(void)

{

int result = 0;

makeFareyNeighbor(1, 3, 1, 2, result);

cout << result << endl;

}