Associated Topics || Dr. Math Home || Search Dr. Math

### Counting Positive Rational Numbers

```
Date: 09/09/2001 at 15:43:35
From: Alfred Lauzon
Subject: Counting the positive rational numbers

In Hardy's book _Pure Mathematics_, on p. 1, he gives a formula for
counting the positive rational numbers p/q when they are arranged in a
triangular matrix and counted down diagonally from the top row,
resulting in the series

1/1, 2/1, 1/2, 3/1, 2/2, 1/3, 4/1, 3/2, 2/3, 1/4, ...

Then p/q is the [1/2(p+q-1)(p+q-2)+q]th term of the series.

I can see that the formula does work for the few numbers I've tried,
but how can it be proved for all such numbers?
```

```
Date: 09/10/2001 at 15:22:23
From: Doctor Peterson
Subject: Re: Counting the positive rational numbers

Hi, Alfred!

This is the sort of thing that is "obvious" if you are looking at it
the right way. If we make a chart of the index in this sequence, we
have

\p|
q \| 1  2  3  4  5
----+---------------
1  | 1  2  4  7 11
2  | 3  5  8 12
3  | 6  9 13
4  |10 14
5  |15

and so on. We are making a sequence of diagonal rows, each of which
ends (at the lower left) with the triangular number T[n], where n is
the row number (1 for the first row, containing only "1"), and

T[n] = n(n+1)/2

The fraction p/q is in row number p+q-1; for instance, to get to 3/2
from 1 we go down two rows and across 1 more, making a total of 3 rows
away from row 1: (3-1)+(2-1)+1 = 4.

The previous row, row p+q-2, ends with T[p+q-2]; in my example this is
the 6 at the end of row 3. Now we have to add q to this index to get
to the entry for p/q in the next row: 6 + 2 = 8 gives us the index for
3/2. In general, the index for p/q is

T[p+q-2] + q = (p+q-2)(p+q-1)/2 + q

And that's what Hardy probably saw immediately, and expects us to see,
too.

(I don't have the book; I assume he does something about the fact that
this count doesn't take into account equivalent fractions.)

- Doctor Peterson, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory
High School Sequences, Series

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search