# Project Euler 71: Listing reduced proper fractions in ascending order of size.

We now have more than 70 problems under our belt and ready to attack the next one. Not that I really care about the number of problems, but this one is really really fun I think. It is easy to understand and have a really beautiful solution based on simple algebra. But lets get on with it, the problem reads

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 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 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

If we just wanted to search all the proper fractions in the search space we would have to search in the ball park of $5\cdot10^11$ not something I am dying to do. Of course we could stop once we get about 3/7 and that would about half the search space, but still. So let’s look at another method.

## Search one fraction for each denominator

Let us for a moment just generalise the theory a little and instead of using 3/7 we will use the general proper fraction a/b such that a<b. For any given denominator q we need to find the p such that p/q gives the largest fraction less than a/b.

In other words we have

$\displaystyle \frac{p}{q} < \frac{a}{b} \Leftrightarrow pb < aq$

And since we are dealing with integer we know that the due to the inequality there is a difference on minimum 1 which allows us to rewrite as

$\displaystyle pb \leq aq -1\Leftrightarrow p \leq \frac{aq -1}{b}$

So the largest p that fulfils the description is

$\displaystyle p = \left\lfloor\frac{aq -1}{b}\right\rfloor$

The reason for subtracting 1 is to avoid problems in case the right hand side of the equation is an integer and thus yielding an equality rather than an inequality.

Now we have found a method to calculate p and thus reduce the number of fractions we need to check to around a million.

### Checking that a solution is better than the previously best

We now know that our fraction p/q < a/b but we still need to check if the new solution p/q is better than the previously best found solution  r/s. We could of course just calculate the fraction, but since I like to work with integers rather than floating point operations we can rewrite the check to such that if

$\displaystyle \frac{r}{s} < \frac{p}{q} \Leftrightarrow rq < ps$

the we have a new best solution. This rewriting can once again only be done because we know that both s and q are positive.

### Coding the theory

The corresponding C# code is really simple. One little trick though, if that if we start from smallest denominator we can be sure that the fraction is always reduced, since any non reduced fraction has already been found with the lower denominator. The code looks like

long a = 3;
long b = 7;
long r = 0;
long s = 1;
int limit = 1000000;

for (int q = limit; q > 2; q--) {
long p = (a * q - 1) / b;
if (p * s > r * q) {
s = q;
r = p;
}
}


Executing the following code gives us

The proper fraction closest to 428570/999997 is 3/7
Solution took 21 ms


which is a pretty decent time to get for a problem.

## Better bounds

Even though the solution presented runs fast enough, my intuition tells me that the solution is likely to be in the upper part of the denominators since a large denominators gives smaller distance between the fractions p/q and (p+1)/q compared to small values of q. So if we start from above and count down we are likely to hit the solution fast, but this only helps us if we can show that it is not possible to find a better solution. So let us try to analyse the problem.

If we have a candidate solution for the problem p/q then the distance to the fraction a/b which is given is

$\displaystyle \frac{a}{b} - \frac{p}{q} = \frac{aq - pb}{bq}$

Due to the inequality $\frac{a}{b} > \frac{p}{q}$ it follows that the numerator must be positive. This gives us

$\displaystyle \frac{aq -pb}{bq} \geq \frac{1}{bq}$

So if we have a current best solution r/s the solution p/q is better if and only if

$\displaystyle \frac{as - rb}{bs} > \frac{aq-pb}{bq} \geq \frac{1}{bq}$

holds true. Which means that

$\displaystyle \frac{as -rb}{bs} > \frac{1}{bq} \Leftrightarrow \frac{s}{as - rb} < q$

This gives us a lower bound for which we can aim for. if as-rb is large then the lower bound wont be raised much, but the smaller it is the larger a lower bound on q is. And if as-rb = 1 then there wont exist smaller denominators which can provide a better solution.

### Implementing the lower bound

Adding a dynamic lower bound is not something that changes the code dramatically, but one thing should be said. We can’t be sure that it is a reduced fraction any more, so we need to reduce the result once we find it. Apart from that the C# code is very similar to the above.

long a = 3;
long b = 7;
long r = 0;
long s = 1;
int limit = 1000000;
long lowerbound = 2;
int q = limit;

while( q >= lowerbound){
long p = (a * q - 1) / b;
if (p * s > r * q) {
s = q;
r = p;
lowerbound = s / (a * s - b * r);
}
q--;
}

long factor = gcd(r, s);
r /= factor;
s /= factor;


The running time is infinitely better than the previous shown code

The proper fraction closest to 428570/999997 is 3/7
Solution took 0 ms


## Wrapping up

I presented you with a brute force approach, and one where we have a better bound on the search space so we don’t have to investigate every single denominator. As usual you are welcome to download the source code for the problem, so you can see all of it including the gcd function.

For this exact problem I don’t think you can find faster or better solutions, but if you have let me know. Also if you have questions, comments or found mistakes leave a comment on the blog and I will look into it.

### Posted by Kristian

SuprDewd

I did a binary search on the Farey sequence.

using System;
using System.Diagnostics;

public class Program
{
public static bool FractionLessThan(int ln, int ld, int rn, int rd)
{
return ln * rd < rn * ld;
}

public static void Main()
{
Stopwatch sw = Stopwatch.StartNew();

int ln = 0, ld = 1,
rn = 1, rd = 1,
mn = 0, md = 0;

while (ld + rd <= 1000000)
{
mn = ln + rn;
md = ld + rd;

bool left = (mn == 3 && md == 7) || !FractionLessThan(mn, md, 3, 7);

if (left)
{
rn = mn;
rd = md;
}
else
{
ln = mn;
ld = md;
}
}

sw.Stop();
Console.WriteLine(mn + "/" + md);
Console.WriteLine(sw.ElapsedMilliseconds + "ms");
}
}

Kristian

Hi SuprDewd

What a brilliant solution to the problem as well. I didn’t know of Farey sequences until after I wrote about the problem. So thanks alot for enlightening me once again.

On my computer your solution finishes in 0ms as well, so that is really nice and fast. Well done.

/Kristian

SuprDewd

Problems 72 and 73 are also related to Farey sequences.
Farey sequences can also be used to solve Diophantine equations more efficiently when using brute force in some Project Euler problems.
I really think Farey sequences are examples of beautiful math 🙂

Kristian

I solved Problem 72 without using Farey sequences, but I hope you will post your solution for it once it is published, so everyone can learn even more.

[…] Mathblog has a good post on the solution to this problem, with the code in C##. […]

Rory

Neighbors in the standard Farey sequence are described in Section 3 of http://arxiv.org/abs/0801.1981 , see Lemma 3.1.

anant

Hi Kristian,

Once again I would need your help. I am not able to understand the last inequality in your explanation.How did r and s help in getting lowerbound for q?

Thanks
Anant

Kristian

Hi Anant

I am glad you asked that question, since I saw I had made several mistakes in the post. I have tried to update the last part of the post and I hope that helps on the understanding.
It took me a good while to figure out my mistakes and correct them, so no wonder you couldn’t follow me.

/Kristian

anant

Hi Kristian,

Thanks for the edit. Now it is clear how r and s gave new lowerbound of q.

Anant

Bowen Kerins

One of the amazing things about the Farey sequence is the presence of “badly summed fractions” — 3/7 is the first fraction between 2/5 and 1/2 and 3/7 = (2+1)/(5+2). Finally, a reason to do fractions the way some kids want to. (One justification is this is like those “mixture” problems, I add a 2/5 solution and a 3/7 solution together and…)

So, if you want the next one to the left of 3/7, you can start from 2/5 and see what would go between them:

2/5 — 5/12 — 3/7
5/12 — 8/19 — 3/7
8/19 — 11/26 — 3/7
11/26 — 14/33 — 3/7

Clearly we’re going to continue this way for a long time, with the goal denominator being the one just before 1 million. 999999 is a multiple of 7 (and also 9 and 11 and 13), so the final denominator is 999997. To get the final numerator, multiply that number by 3/7 and round down; the numerator is 428570.

Related and unrelated: what fraction will you eventually reach if you keep going “right and left” in the sequence:

1/1, then the next one that comes to the left, then the next new one that comes to the right, then the next new one that comes to the left…

Bjarki Ágúst

Bowen Kerins: Wow, this is neat. After a couple of iterations of alternatively going left and right, the fraction seems to be converging to the reciprocal of the Golden Ratio, which is about 0.618034.

Also, if I start going right instead of left, the fraction seems to converge to the Golden Ratio itself, which is about 1.61803.

blerik

I solved this by hand. I figured I would need a 3/7 fraction with a denominator as close as possible to 1.000.000.

So I did:
factor = |1.000.000 / 7|
numer = factor * 3
denom = factor * 7

Then I stepped the numer one to the left:
numer -= 1

And I simplified (which was unneccessary), and that was the answer…

hongtengyin

my code works

limit = 1000000
times = (limit - 5) / 7
the_numerator = 2 + 3 * times
print the_numerator

Marc

I just did it by hand noting that the best solution would be something like:
(3*x -1)/(7*x)

Noting that 1.000.000 leaves 1 modulo 7, 999.999 should be the start.
999.999 is a multiple of 7, giving a rest of 142.857.
(142857*3)/(142857*7) = 3/7

immediatly to the left is then 142857*3-1 = 428570 – which is the right answer.

David Gillies

Call the Farey sequence for denominator <= n F(n). Farey sequences have the property that if neighbouring fractions have the values a/b and c/d, then the first time a fraction will appear between them it will be in the sequence F(b + d) and have the value (a + c)/(b + d). We note in F(8) the leftward neighbour of 3/7 is 2/5. Thus, we get the following trivial code (written in plain C).

#include <stdio.h>

int main(void)
{
unsigned int a = 2, b = 5, c = 3, d = 7;
while (b + d < 1000000)
{
a += c;
b += d;
}
printf("%u/%u\n", a, b);
return 0;
}

Result: 428570/999997 in about a microsecond.

Tharaka

Superb method…!
Thanks