Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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.

See also the last section of

  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.

If you have any questions about this or need more help, please write
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/