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$?

  • 2
    $\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$ – Aleksei Kulikov Jun 11 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 at 3:16

It has been conjecture that the ratio is:


But proof is still missing.

| cite | improve this answer | |
  • $\begingroup$ Is this a reformulation of the comment by Aleksei Kolikov? $\endgroup$ – Dieter Kadelka Jun 21 at 8:01
  • $\begingroup$ No it was computed independently on de.sci.mathematik, but its essentially the same approach. And also the same unsolved gap, whether filtering gcd(x,y)=/=1 changes the result. $\endgroup$ – Mostowski Collapse Jun 21 at 11:59
  • 2
    $\begingroup$ Did you search under the bed? When something is missing in 8 out of 10 cases, it's under the bed/sofa/cupboard of something. $\endgroup$ – Asaf Karagila Jun 21 at 12:19
  • 1
    $\begingroup$ There could be changes in co-prime density, like close to Golden ratio. Dunno. For a visualization see here: en.wikipedia.org/wiki/Coprime_integers#/media/File:Coprime8.svg $\endgroup$ – Mostowski Collapse Jun 21 at 13:42
  • 1
    $\begingroup$ It is maybe more natural to have at denominator just $k$, which results in dividing by $2$ the posted limit. So for the interval [a,b] the limit of frequencies $\lim_{k\to\infty} \#\{k: a\le q_j\le b,1\le j\le k\}/k $ should be $\frac1{a+1}-\frac1{b+1}$ (if co-primality is independent) $\endgroup$ – Pietro Majer Nov 18 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.