Fraction Counting Problem

Brian Rothstein

Dec 27, 1999

1  Problem

We are all familiar with counting in integers. If given an integer, N, it's relatively easy to write an algorithm which prints out the integers 1..N in order. A similar problem exists in fractions. Given a number, N, find an algorithm which prints out, in order and in reduced form, all of the fractions between 0 and 1 with denominator less than or equal to N.

For example, with N = 5 the algorithm should output: 1/5,1/4, 1/3, 2/5, 1/2, 3/5,2/3, 3/4, 4/5.

2  Background

2.1  Euclidean Algorithm

Given two integers a0 and a1, 0 < a1 £ a0, consider the following sequence of equations:

a0 = m1a1+ a2, 0 < a2 < a1
a1 = m2a2 + a3, 0 < a3 < a2
.
.
.
an-2 = mn-1an-1 + an, 0 < an < an-1
an-1 = mnan + an+1, an+1 = 0.

Here we have mi = ai-1 div ai and ai = ai-2 mod ai-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, an = GCD(a0,a1). I'll prove the validity of this statement and some additional useful facts in the next subsections.

2.2  Common Divisors of a0 and a1

Claim 1. If a0 = da0¢ and a1 = da1¢ then ai = dai¢ for all i.

What this says is that if a0 and a1 are divisible by d, then all of the ai's are divisible by d.

Proof.

Base Case: a0 = da0¢ and a1 = da1¢.
(1)
Now assume that ai-1 = dai-1¢ and ai = dai¢.
(2)
By the Euclidean algorithm, ai-1 = miai + ai+1
(3)
Þ ai+1 = ai-1 - miai
(4)
(2)  Ù (4) Þ ai+1 = dai-1¢- midai¢ = d(ai-1¢- miai¢)
(5)
Þ ai+1 = dai+1¢
(6)

So by induction, the claim is proven.

Claim 2. If ai = dai¢ and ai+1¢ = dai+1¢ then a0 = da0¢ and a1 = da1¢.

What this says is that if a number, d, divides two consecutive ai's, then it divides a0 and a1 as well.

Proof.

Assume that ai = dai¢ and ai+1¢ = dai+1¢.
(7)
By the Euclidean algorithm, ai-1 = miai + ai+1
(8)
(7) Ù(8) Þ ai-1 = midai¢+ dai+1¢ = d(miai¢+ ai+1¢)
(9)
Þ ai-1 = dai-1¢
(10)

So by induction, the claim is proven.

2.3  Greatest Common Divisor of a0 and a1

Claim 3. There exists an n such that an ¹ 0 and an+1 = 0.

What this says is that the Euclidean algorithm is guaranteed to terminate and therefore guranteed to find the GCD of a0 and a1.

Proof.

By the Euclidean algorithm, 0 £ ai+1 < ai for i ³ 1.
(11)
Þ 0 £ ai+1 £ ai - 1
(12)
Þ 0 £ ai+1 £ a0 - i
(13)

So after at most a0 steps, ai will equal 0.

Claim4. an is the Greatest Common Divisor of a0 and a1.

What this means is that a0 = ana0¢ and a1 = ana1¢ and there is no number d, such that d > an and a0 = da0¢¢ and a1 = da1¢¢.

Proof.

By the Euclidean algorithm, an-1 = mnan +an+1, an+1 = 0.
(14)
Þ an+1 = 0 ·an and an = 1 ·an
(15)
(By Claim 2) Þ a0 = ana0¢ and a1 = ana1¢.
(16)

So an is a divisor of a0 and a1.

Now assume that $d such that d > an and a0 = da0¢ and a1 = da1¢.

(By Claim 1) Þ an = dan¢
(17)
d > an Þ an = an¢ = 0
(18)

which contradicts the Euclidean algorithm's statement that 0 < an < an-1. So, an must be the GCD of a0 and a1.

2.4  Linear Integer Equations

Claim 5. Given two integers a0 and a1, 0 < a1 £ a0, the following equation is soluble for integers x and y:
a0x - a1y = GCD(a0,a1)
(19)

Proof.

Base Case: a0 = a0 ·1 - a1 ·0,  a1 = a0 ·0 - a1 ·-1.
(20)
Now assume that ai-1 = a0xi-1 - a1yi-1,  ai = a0xi - a1yi.
(21)
By the Euclidean Algorithm, ai-1 = miai + ai+1
(22)
Þ ai+1 = ai-1 - miai
(23)
(21)  Ù (23) Þ ai+1 = a0xi-1 - a1yi-1 - mi(a0xi - a1yi)
(24)
Þ ai+1 = a0(xi-1 - mixi) - a1(yi-1 -miyi)
(25)
So by induction, ai = a0xi - a1yi for all i. Indeed, an = a0xn - a1yn. But by Claim 4, an = GCD(a0, a1).

2.5  Fundamental Theorem of Arithmetic

Claim 6. Given positive integers, a, b, and c such that bc = aa¢ and GCD(a,b) = 1, we have c = ac¢.

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

Proof.

By Claim 5, we can find x, y such that ax - by = GCD(a,b) = 1
(26)
Þ c(ax - by) = c
(27)
Þ acx - bcy = c
(28)
Þ acx - aa¢y = c
(29)
Þ c = a(cx - a¢y) = ac¢
(30)

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 = p1p2 ···pn where p1, p2,..., pn are prime numbers, there is no other representation, a = q1q2 ···qk where q1, q2, ..., qk 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 = p1p2 ···pn where p1, p2,..., pn are prime numbers and a = q1q2 ···qk where q1, q2, ..., qk are prime numbers.

Then we have that p1p2 ···pn = q1q2···qk. By Claim 6, p1 must divide one of the qi's (in fact, it must divide it exactly since these are prime numbers and thus have no factors in common except themselves.)

Cancel out p1 and qi and repeat the process for p2, p3,..., pn in order to discover that the terms match exactly.

2.6  Complete Solutions to Certain Linear Integer Equations

Claim 7. Given two integers a and b such that GCD(a,b) = 1, the following equation is soluble for integers x¢ and y¢:

ax¢- by¢ = n
(31)

Proof.

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

ar - bs = GCD(a,b) = 1.
(32)
Þ n(ar - bs) = n
(33)
Þ a(nr) - b(ns) = n
(34)
Þ x¢ = nr,  y¢ = ns
(35)

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

x = x¢+mb, y = y¢+ma
(36)

Proof.

ax - by = a(x¢+mb) - b(y¢+ma)
(37)
= ax¢+amb - by¢-bma
(38)
= ax¢-by¢ = n
(39)

So x and y satisfy ax-by = n.

Now suppose that there exist u and v such that

au - bv = n
(40)

and

\mid u-x \mid   <  b.
(41)
Þ ax - by - (au - bv) = n - n = 0
(42)
Þ a(x-u) - b(y-v) = 0
(43)
Þ a(x-u) = b(y-v)
(44)
Claim 6  Ù (44) Þ y-v = ac¢
(45)
Þ a(x-u) = bac¢
(46)
Þ (x-u) = bc¢
(47)
(41)  Ù (47) Þ c¢ = 0
(48)
Þ  x = u
(49)
(43)  Ù (49) Þ y = v
(50)
So x = x¢+mb and y = y¢+ma are the only solutions to ax - by = n.

3  Properties of the Fraction Counting Sequence

3.1  Theorem 1

For any two consecutive fractions in the fraction counting sequence, a/b < c/d, cb - ad = 1. Or equivalently, c/d - a/b = [1/ bd].

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

ay-bx = 1
(51)

y £ N and y+b > N
(52)

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

v £ N,
(53)

GCD(u,v) = 1,
(54)

x
y
< u
v
< a
b
,
(55)

av - bu = n,  n > 1.
(56)

Using these assumptions we find

(55) Þ a
b
- u
v
< a
b
- x
y
(57)

(56) Þ a
b
- u
v
= n
bv
(58)

(57)  Ù (58) Þ n
bv
< 1
by
(59)
Þ n < v
y
(60)

By Claim 8, we have

u = nx + ka and v = ny + kb for some integerk.
(61)

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

Case 1: k < 0

k < 0  Ù (61) Þ v < ny
(62)
Þ n ³ v
y
(63)

which contradicts (60).

Case 2: k = 0

k = 0  Ù (61) Þ u = nx and v = ny
(64)
Þ GCD(u,v) ³ n
(65)

which contradicts (54) since n > 1.

Case 3: k > 0

k > 0  Ù (61) Þ v ³ ny + b
(66)
(52)  Ù (66) Þ v > N.
(67)

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

For any three consecutive fractions, a/b < c/d < e/f, in the fraction counting sequence the following (amazing) fact holds:

c
d
= a+e
b+f
(68)

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:

bc - ad = 1,
(69)

de - cf = 1.
(70)

Solving for c, we get

(69) Þ d = bc - 1
a
(71)

(70) Þ d = cf + 1
e
(72)

(71)  Ù (72) Þ bc -1
a
= cf + 1
e
(73)

Þ bce - e
ae
= acf + a
ae
(74)

Þ bce - e = acf + a
(75)

Þ c = a + e
be - af
(76)

Solving for d, we get

(69) Þ c = ad + 1
b
(77)

(70) Þ c = de - 1
f
(78)

(77)  Ù (78) Þ ad +1
b
= de - 1
f
(79)

Þ adf + f
bf
= bde - b
bf
(80)

Þ adf + f = bde - b
(81)

Þ d = b + f
be - af
(82)

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

c
d
=
a + e
be - af

b + f
be - af
= a+e
b+f
.
(83)

4  Solution

4.1  Determining the Next Fraction in the Sequence

Suppose we know two consecutive fractions, a/b < c/d, in the fraction counting sequence. The goal is to find the next fraction, e/f, 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:

e = xc - a,  f = xd - b
(84)
x = (N+b) div d
(85)

Proof.

By Theorem 2,   c
d
= a+e
b+f
(86)

Þ c(b+f) = d(a+e)
(87)

By the constraints of the problem,  GCD(c,d) = 1.
(88)

(88)  Ù Claim 6 Þ b+f = xd
(89)
(87) Ù (89) Þ cxd = d(a+e)Þ a+e = xc
(90)
(89)  Ù (90) Þ e = xc - a, f = xd - b
(91)
which proves (84).

In order to prove (85), consider the function

f(x) = xc - a
xd - b
(92)
Differentiating f(x), we find
f¢(x) = c(xd-b) - d(xc-a)
(xd - b)2
= ad - bc
(xd- b)2
(93)
a
b
< c
d
Þ ad < bc Þ ad - bc < 0
(94)
(93)  Ù (94) Þ f¢(x) < 0  for all x for which f¢(x) is defined.
(95)
Therefore, f(x) is monotonically decreasing with x. Also,

lim
x ® ¥ 
f(x) =
lim
x ®¥ 
xc - a
xd - b
=
lim
x ® ¥ 
c- a
x

d - b
x
= c
d
(96)
And since e/f = f(x) for some x, we want to pick the largest possible x within the constraints of the problem in order to get e/f as close as possible to c/d. If we didn't pick such an x then we could find a larger x which would give us a smaller fraction thus contradicting the problem statement since we wouldn't have all fractions in order.

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

Þ xd £ N + b
(97)

Þ x £ N + b
d
(98)

Since x must be an integer, we get

x = (N+b) div d
(99)
which proves (85).

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 = 0/1, 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.


File translated from TEX by TTH, version 2.25.
On 27 Dec 1999, 23:28.