Uniformly distributed rationals

Is there any algorithm, function or formula $f(n)$, which is a bijection between the positive integers and the rationals in $(0,1)$, with the condition, that for all real numbers $a,b,x$ with $0<a<b<1<x$, if we let $i(x)$ be the number of distinct integers $0<n_j<x$ which satisfy $a<f(n_j)<b$, then we have $\lim_{x\rightarrow\infty}i(x)/x=b-a$?

Solution 1:

van der Corput is a bit of overkill. It gives a sequence with an especially low discrepancy, but that's more than what's needed for uniform distribution.

There is a theorem of von Neumann that says that any countable set of reals dense in $(0,1)$ can be ordered in such a way as to become a uniformly distributed sequence. One way to do this is to enumerate the set any old way, say, $s_1,s_2,\dots$, and also write down a list of intervals $I_1,I_2,\dots$, where the first two intervals partition $(0,1)$ into two equal pieces, the next three partition $(0,1)$ into three equal pieces, etc. Then for each $j$, $j=1,2,\dots$, let $u_j$ be the first unused $s_j$ in $I_j$. Then $u_1,u_2,\dots$ can be proved to be a uniformly distributed ordering of your dense set.

Solution 2:

You are looking for an equidistributed sequence of rationals that uses every rational exactly once. The Van der Corput sequence mentioned by GEdgar comes close, except that it misses some of the rationals. But you can just throw in the missing numbers, as long as you spread them out.

For instance, the binary Van der Corput sequence uses all the dyadic rationals. If you enumerate the non-dyadic rationals and insert the $k$th one into the sequence at position $2^k$, say, you can check that the new sequence is still equidistributed. The key is that of the first $N$ values in the sequence, only $o(N)$ have been changed.