Cantor's famous sequence

$\frac{1}{1},\frac{1}{2},\frac{2}{1},\frac{1}{3},\frac{3}{1},\frac{1}{4}, \frac{2}{3},\frac{3}{2},\frac{4}{1}, \frac{1}{5},\frac{5}{1},\frac{1}{6}, ...$

provides a bijection between natural numbers and positive rational numbers or cancelled fractions.

About half of the fractions $q_i$ lie within $0 < x \leq 1$. What is the limit of the ratio

$\lim\limits_{k\to\infty}\frac{|\{x ∈ \mathbb{R}| n < x \leq n+1\} ∩ \{q_1, q_2, ..., q_k\}|}{|\{x ∈ \mathbb{R} | 0 < x \leq 1\} ∩ \{q_1, q_2, ..., q_k\}|}$ for $n \in \mathbb{N}$?

Is there an $n$ for which the limit is $0$? And if so, what is the first such $n$?

  • 3
    $\begingroup$ If I understood the construction correctly I would guess that the limit is $4S$ where $S$ is the area of the triangle bounded by the lines $y = nx$, $y = (n+1)x$ and $x+y=1$. At least if we didn't skip non-reduced fractions it would be this limit for sure and I would assume that coprimality condition do not make much harm. $\endgroup$ Jun 11, 2020 at 11:22
  • 1
    $\begingroup$ It is likely easier to work with the fraction where the inequality is just $n \leq x$; assuming that limit exists, the limit in your question is just the difference of consecutive terms. And I'm pretty sure it shouldn't be hard to see that in each "sweep", approximately half of the fractions are below $1$ while approximately $\frac{1}{n}$ of them are larger than $n$, which leads to the answer given by Mostowski Collapse. $\endgroup$
    – user44191
    Jun 21, 2020 at 3:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.