_{1}, ..., q

_{k}be the prime factors of n. Sagher defined his 1-1 mapping as

^{2}n

^{2}/ (q

_{1}q

_{2}··· q

_{k})

^{15}th 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.

- Input: n
- Find i and j such that n = p(i,j).
- Let g = gcd(i,j) (easily computable via Euclid's algorithm)
- Let u = i/g and v=j/g.
- Output: g-1+u/v

## No comments:

## Post a Comment