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

### Counting Unique Rational Numbers

```Date: 11/16/2008 at 14:32:50
From: Jonathan
Subject: unique rationals p/q with p and q <= n

I'm stumped on a question in number theory that has turned out to be
more difficult than I'd expected.  Here it is:

How many unique simple forms of rational numbers are there of the
form p/q, where p and q are non-zero whole numbers less than or equal
to n?  For example, 1/2 and 2/4 have the same simple form, so they are
not considered unique.  The answer should be a function of n.

It's obviously connected to factorization and hence prime numbers.
That makes it difficult.

A similar type of question is: how many primes are less than or equal
to n?  A standard approximation is n/ln(n).

Starting from this, one guess is that the answer is approximately n *
n/ln(n).  But I think I've shown that it's bigger than that.

Another intriguing finding is that the answer can be written as the
series:

k1*n/1 + k2*n/2 + k3*n/3 + k4*n/4 + k5*n/5 + ... + kn*n/n

This is the harmonic series with each term multiplied by a unique
constant shown here as k1, k2, etc.  But the constants are a bizarre
sequence related to prime factorization, and hence they're very
difficult to predict.

Each k sub i is equal to i minus the number of whole numbers less
than or equal to i that share common factors with i.  E.g., for i=6,
the numbers 2,3,4 and 6 share common factors, hence k sub 6 = 6-4 = 2.

One way to approach it would be to write a computer program (or use
Mathematica) to compute the answer for the first, say, ten thousand
values of n.  Then try to plot it and compare to some possible
solutions and see if it seems to converge on something.

Another reasonable guess might be:

n * (n - n/ln(n)) = n^2 - n^2/ln(n)

Has this been done before?  If you can find a reference, I would be
eternally grateful.  This problem has been obsessing me.

```

```
Date: 11/17/2008 at 15:39:18
From: Doctor Vogler
Subject: Re: unique rationals p/q with p and q <= n

Hi Jonathan,

Thanks for writing to Dr. Math.  That's a very interesting question.
I would suggest analyzing it as follows:

There are, of course, n^2 pairs of positive integers (p, q) with p and
q not larger than n.  Of those floor(n/2)^2 of them will have both p
and q divisible by 2.  So we should subtract that from the initial
n^2.  (The floor function, also known as the greatest integer
function, means to round DOWN to the nearest integer.)

Wikipedia: Floor Function
http://en.wikipedia.org/wiki/Floor_function

Similarly, there are floor(n/3)^2 pairs with p and q both divisible by
3.  We should similarly count floor(n/r)^2 for every prime r.  But
notice that we have also double-counted the pairs with p and q both
divisible by 6, so we should add those back in, so as to only subtract
them once.  Continuing this analysis, we end up with the result of the
Inclusion-Exclusion Principle

Wikipedia: Inclusion-Exclusion Principle
http://en.wikipedia.org/wiki/Inclusion-exclusion

namely that the number you want is

f(n) = n^2 - sum floor(n/r)^2 + sum floor(n/rs)^2
- sum floor(n/rst)^2 + ...,

where the first sum is over all primes r, the second over all pairs of
distinct primes (r, s), and so on.  In fact, you can write this much
more succinctly using the Mobius mu function

Wikipedia: Moebius Function
http://en.wikipedia.org/wiki/Moebius_function

oo
f(n) = sum mu(k) * floor(n/k)^2
k=1

where the sum is over all positive integers k (from 1 to infinity, as
written).

When n is not too large, you can compute this sum explicitly by
computing the value of mu(k) (or looking it up in a table) for all k
up to n.  (For k > n, floor(n/k) = 0, so all terms with k > n are zero.)

When n is large, so that an exact computation is not very feasible, a
simple approximation pays big:  If you remove the floor function that
rounds to an integer (which causes the mu(k) = 1 terms to get larger
by a fraction and the mu(k) = -1 terms to get smaller by a fraction),
then you get the approximation

oo
sum mu(k) * (n/k)^2 = n^2 * product (1 - p^-2) = n^2 * 6/pi^2
k=1                        primes p

where the last product is over all primes p.

Wikipedia: Coprime
http://en.wikipedia.org/wiki/Coprime

In fact, we can also bound the difference.  We can prove that (writing
abs for absolute value and int for an integral)

abs(f(n) - n^2 * 6/pi^2)

oo                      oo
= abs( sum mu(k)floor(n/k)^2 - sum mu(k)(n/k)^2 )
k=1                     k=1

oo
< sum (n/k)^2 - floor(n/k)^2
k=1

n         oo
< sum 1  +  sum (n/k)^2
k=1      k=n+1

n         oo    k
< sum 1  +  sum   int (n/x)^2 dx
k=1      k=n+1  k-1

oo
=   n    +  int (n/x)^2 dx
n

= 2n.

This means that f(n) equals n^2 * 6/pi^2 plus some small number which
is smaller than 2n.  (Note that when n is large, 2n is a lot smaller
than n^2.)  So that means that f(n) is approximately 60.8% of n^2.

back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
http://mathforum.org/dr.math/

```

```
Date: 11/17/2008 at 17:54:03
From: Jonathan
Subject: Thank you (unique rationals p/q with p and q <= n)

Thanks for pointing me to the definition of coprime.  I understand
now.
```
Associated Topics:
College Number Theory

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