Project Euler 73: How many fractions lie between 1/3 and 1/2 in a sorted set of reduced proper fractions?

Project Euler 73: How many fractions lie between 1/3 and 1/2 in a sorted set of reduced proper fractions?

Written by on 3 December 2011

Topics: Project Euler

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, 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 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 for d ≤ 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 F8.

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.

9 Comments For This Post I'd Love to Hear Yours!

  1. SuprDewd says:

    The brute force solution is acting weird again 🙂

  2. Rory says:

    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.

  3. Rory says:

    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.

  4. Kristian says:

    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

  5. anant says:

    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

  6. Kristian says:

    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

  7. anant says:

    Thanks Krisitan. Yes it helped.

  8. Lou says:

    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.

  9. IamLupo says:

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

    http://pastebin.com/Xny8N8Vb

Trackbacks For This Post

  1. Euclidean algorithm – Problema 72 « Programmer's Blog

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.