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.
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.