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) |
(2) Ù (4) Þ ai+1 = dai-1¢- midai¢ = d(ai-1¢- miai¢) |
| (5) |
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) |
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) |
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¢.
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:
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) |
(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) |
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¢:
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.
ax - by = a(x¢+mb) - b(y¢+ma) |
| (37) |
So x and y satisfy ax-by = n.
Now suppose that there exist u and v such that
and
Þ ax - by - (au - bv) = n - n = 0 |
| (42) |
Claim 6 Ù (44) Þ y-v = ac¢ |
| (45) |
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
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
(55) Þ |
a b
|
- |
u v
|
< |
a b
|
- |
x y
|
|
| (57) |
(57) Ù (58) Þ |
n bv
|
< |
1 by
|
|
| (59) |
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
which contradicts (60).
Case 2: k = 0
k = 0 Ù (61) Þ u = nx and v = ny |
| (64) |
which contradicts (54) since n > 1.
Case 3: k > 0
k > 0 Ù (61) Þ v ³ ny + b |
| (66) |
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:
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
(71) Ù (72) Þ |
bc -1 a
|
= |
cf + 1 e
|
|
| (73) |
Þ |
bce - e ae
|
= |
acf + a ae
|
|
| (74) |
Solving for d, we get
(77) Ù (78) Þ |
ad +1 b
|
= |
de - 1 f
|
|
| (79) |
Þ |
adf + f bf
|
= |
bde - b bf
|
|
| (80) |
Finally, using (76) and (82) we get,
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:
Proof.
By Theorem 2, |
c d
|
= |
a+e b+f
|
|
| (86) |
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
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 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.
Since x must be an integer, we get
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.