Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Counting the Rationals Quickly

Expand Messages
  • Lance Fortnow
    In the November 1989 issue of American Mathematical Monthly Yoram Sagher presented a note Counting the Rationals giving a simple 1-1 mapping from the
    Message 1 of 1 , Mar 1, 2004
    • 0 Attachment
      In the November 1989 issue of American Mathematical Monthly Yoram Sagher presented a note "Counting the Rationals" giving a simple 1-1 mapping from the positive rationals onto the positive integers. Let m/n be a rational with gcd(m,n)=1. Let q1, ..., qk be the prime factors of n. Sagher defined his 1-1 mapping as
      f(m/n) = m2n2/ (q1q2··· qk)
      With this mapping, Sagher notes you can easily determine the 1015th positive rational as 10-8.

      Unfortunately inverting Sagher's function appears to require factoring. Can one find a 1-1 mapping from the positive integers onto the positive rationals that is easy to compute in both directions? Think about it or keep reading for my solution.

      Let p(i,j) = i + j(j-1)/2. The function p is an easily computable and invertible bijection from pairs (i,j) with 1≤i≤j to the positive integers. We define our 1-1 mapping from the positive integers to the positive rationals by the following algorithm.

      1. Input: n
      2. Find i and j such that n = p(i,j).
      3. Let g = gcd(i,j) (easily computable via Euclid's algorithm)
      4. Let u = i/g and v=j/g.
      5. Output: g-1+u/v
      Since 1≤i≤j we have 1≤u≤v making the output unique and the function easily invertible.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 3/1/2004 08:48:31 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.