Fraction Counting Problem

Brian Rothstein

Dec 27, 1999

1  Problem

For example, with N = 5 the algorithm should output: ¹/₅,¹/₄, ¹/₃, ²/₅, ¹/₂, ³/₅,²/₃, ³/₄, ⁴/₅.

2  Background

2.1  Euclidean Algorithm

a₀ = m₁a₁+ a₂, 0 < a₂ < a₁
a₁ = m₂a₂ + a₃, 0 < a₃ < a₂
.
.
.
a_n-2 = m_n-1a_n-1 + a_n, 0 < a_n < a_n-1
a_n-1 = m_na_n + a_n+1, a_n+1 = 0.

Here we have m_i = a_i-1 div a_i and a_i = a_i-2 mod a_i-1 where div and mod represent integer division and remainder operations. This set of equations represents Euclid's algorithm which is used to find the greatest common divisor (GCD) of two numbers. Specifically, a_n = GCD(a₀,a₁). I'll prove the validity of this statement and some additional useful facts in the next subsections.

2.2  Common Divisors of a₀ and a₁

What this says is that if a₀ and a₁ are divisible by d, then all of the a_i's are divisible by d.

Proof.

So by induction, the claim is proven.

Claim 2. If a_i = da_i¢ and a_i+1¢ = da_i+1¢ then a₀ = da₀¢ and a₁ = da₁¢.

What this says is that if a number, d, divides two consecutive a_i's, then it divides a₀ and a₁ as well.

Proof.

So by induction, the claim is proven.

2.3  Greatest Common Divisor of a₀ and a₁

What this says is that the Euclidean algorithm is guaranteed to terminate and therefore guranteed to find the GCD of a₀ and a₁.

Proof.

So after at most a₀ steps, a_i will equal 0.

Claim4. a_n is the Greatest Common Divisor of a₀ and a₁.

What this means is that a₀ = a_na₀¢ and a₁ = a_na₁¢ and there is no number d, such that d > a_n and a₀ = da₀¢¢ and a₁ = da₁¢¢.

Proof.

So a_n is a divisor of a₀ and a₁.

Now assume that $d such that d > a_n and a₀ = da₀¢ and a₁ = da₁¢.

which contradicts the Euclidean algorithm's statement that 0 < a_n < a_n-1. So, a_n must be the GCD of a₀ and a₁.

2.4  Linear Integer Equations

Proof.

2.5  Fundamental Theorem of Arithmetic

What this says is that if a divides bc and a and b have no common divisors, then a must divide c.

Proof.

Claim 6 is the basis for the Fundamental Theorem of Arithmetic which states that any integer can be uniquely factored into a product of prime numbers (i.e. there is a unique prime number representation for every integer.)

It's obvious that an integer can be factored into a product of primes. One simply has to continue extracting factors from the integer and factors from the factors until all that's left is primes.

However, the Fundamental Theorem of Arithmetic states that given an integer a = p₁p₂ ···p_n where p₁, p₂,..., p_n are prime numbers, there is no other representation, a = q₁q₂ ···q_k where q₁, q₂, ..., q_k are prime numbers and the q's and k differ from the p's and n (except, of course, for simple rearrangement of the terms.)

The Fundamental Theorem of Arithmetic, itself, is not necessary for solving the fraction counting problem, so I will only outline the proof.

Suppose that a = p₁p₂ ···p_n where p₁, p₂,..., p_n are prime numbers and a = q₁q₂ ···q_k where q₁, q₂, ..., q_k are prime numbers.

Then we have that p₁p₂ ···p_n = q₁q₂···q_k. By Claim 6, p₁ must divide one of the q_i's (in fact, it must divide it exactly since these are prime numbers and thus have no factors in common except themselves.)

Cancel out p₁ and q_i and repeat the process for p₂, p₃,..., p_n in order to discover that the terms match exactly.

2.6  Complete Solutions to Certain Linear Integer Equations

Proof.

By Claim 6, we can find integers r and s such that

Claim 8. All possible solutions to ax - by = n are given by:

Proof.

So x and y satisfy ax-by = n.

Now suppose that there exist u and v such that

and

3  Properties of the Fraction Counting Sequence

3.1  Theorem 1

Proof.   Given ^a/_b, we're interested in finding the closest fraction, ^x/_y, which is less than ^a/_b and satisfies the constraints of the problem, namely y £ N and GCD(x,y) = 1.

I claim that solving

for x and y gives the desired closest fraction.

By Claim 5, ay¢-bx¢ = 1 is soluble since GCD(a,b) = 1.

Also, from Claim 8, we have ay-bx = 1 where y = y¢+mb and x = x¢+ma so we can find an appropriate m such that y = y¢+mb, y £ N, and y+b > N.

Now assume that there exist u and v such that

Using these assumptions we find

By Claim 8, we have

Now we examine 3 cases: k < 0, k = 0, and k > 0.

Case 1: k < 0

which contradicts (60).

Case 2: k = 0

which contradicts (54) since n > 1.

Case 3: k > 0

which contradicts (53).

So there are no u and v which meet the constraints of the problem such that ^x/_y < ^u/_v < ^a/_b and av - bu > 1. This completes the proof.

3.2  Theorem 2

This fact is attributed to John Farey who discovered it in 1816 after it had escaped the notice of such great number theorists as Euler and Fermat. For this reason the fraction counting series is usually referred to as the Farey series.

Proof. Using Theorem 1, we obtain the following two equations:

Solving for c, we get

Solving for d, we get

Finally, using (76) and (82) we get,

4  Solution

4.1  Determining the Next Fraction in the Sequence

Theorem 3 If ^a/_b and ^c/_d are two consecutive fractions in the fraction counting sequence such that ^a/_b < ^c/_d, then the next fraction, ^e/_f, in the sequence can be determined as follows:

Proof.

In order to prove (85), consider the function

The constraints of the problem state that we can make x as big as we want so long as xd - b £ N.

Since x must be an integer, we get

4.2  The Fraction Counting Algorithm

void FractionCount(int N) {
    int a,b,c,d,e,f,x;

    a = 0; b = 1;
    c = 1; d = N;

    while(c < d)
    {
        printf("%d/%d",c,d);

        x = (N + b)/d;
        e = x*c - a;
        f = x*d - b;

        a = c; b = d;
        c = e; d = f;

        if(c < d) printf(", ");
    }
    printf("\n");
}

The proof of the algorithm follows almost directly from Theorem 3. There's a small catch, though, because we start out with ^a/_b = ⁰/₁, and we only defined the Euclidean Algorithm in terms of 0 < a £ b. However, we can define GCD(0,n) = n for n > 0. It's a simple exercise to show that Claim 5 still holds in this case which implies that Claims 6, 7, and 8 hold as well.