Analytic/ asymptotic size of rationals

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
Quizatzhaderac
Posts: 1798
Joined: Sun Oct 19, 2008 5:28 pm UTC
Location: Space Florida

Analytic/ asymptotic size of rationals

Postby Quizatzhaderac » Mon Apr 29, 2019 9:19 pm UTC

Let N be the set of natural numbers less than or equal to x.
Let p and q by any two numbers in N.
Let R be the set of numbers produced by all combinations of p/q.
As x approaches infinity, what does |R| approach?

The size(N) is obviously x.
The size(R) has the upper bound <= x2, as there are x2 combinations of p and q, but there are redundancies ( ex 1/2 and 2/4), so we should be able to get a better upper bound.

size(R) has the lower bound >=x, because every integer is a rational.
Another lower bound would be 2(π(x)^2-π(x)) (π(x) being the prime counting function), as each combination of different primes can be guaranteed to be a unique rational, as can it's inverse.
The thing about recursion problems is that they tend to contain other recursion problems.

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Analytic/ asymptotic size of rationals

Postby Xanthir » Mon Apr 29, 2019 9:54 pm UTC

Given any set of equal-value fractions, exactly one of them will be maximally reduced, which we can take as the "canonical" fraction for that value. "Maximally-reduced" means that the numerator and denominator are coprime; if they're not coprime, they share a factor and can be further reduced.

The question thus reduces to asking what the probability is of two numbers less than X being coprime. Apparently, this approaches approximately 61%.

Interestingly, that wikipedia page also contains a simple method of exhaustively and uniquely generating all coprime pairs, which is pretty dang cool.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Eebster the Great
Posts: 3463
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: Analytic/ asymptotic size of rationals

Postby Eebster the Great » Tue Apr 30, 2019 3:09 am UTC

It's not just about .61, but ezactly 1/ʒ(2) = 6/π2 (quoting the article), which gives the limit of the cardinality of the set of rationals with numerator and denominator at most x as x approaches infinity of exactly 6x22.

User avatar
PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Analytic/ asymptotic size of rationals

Postby PM 2Ring » Tue Apr 30, 2019 1:33 pm UTC

On a closely related note, see Farey sequence.
The Farey sequence of order n is the sequence of completely reduced fractions, either between 0 and 1, or without this restriction, which when in lowest terms have denominators less than or equal to n, arranged in order of increasing size.

User avatar
Quizatzhaderac
Posts: 1798
Joined: Sun Oct 19, 2008 5:28 pm UTC
Location: Space Florida

Re: Analytic/ asymptotic size of rationals

Postby Quizatzhaderac » Tue Apr 30, 2019 8:38 pm UTC

Thanks, that was exactly what I was looking for.
The thing about recursion problems is that they tend to contain other recursion problems.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 14 guests