5
$\begingroup$

Consider the following set:

$S := \left\{\frac{a}{b} \colon a \in \{1,\ldots,A\}, b \in \{1,\ldots,B\} \right\}$

$S$ is the set of all rational numbers that can be represented by two integers $a$ and $b$ that are bounded by $A \geq 1$ and $B \geq 1$. For the sake of simplicity, we can also think of $S$ as a multiset such that the number of elements in $S$ is given by $A \cdot B$.

Do you see any possibility how to find the $k$-th smallest number in $S$ in time $\mathcal{O}(\log (A \cdot B))$ ?

Clearly, the smallest number if given by $\frac{1}{B}$ and, as long as $B \geq 2$, the second smallest number is given by $\frac{1}{B-1}$. But then things are getting interesting...

$\endgroup$
3
$\begingroup$

It is perhaps more natural to consider the set $S$. Let us further consider the case $A = B = n$ and the set $S \cap [0,1] = \mathcal{F}_n$, the $n$th Farey sequence; if we know $|\mathcal{F}_n|$ and can solve the problem for $\mathcal{F}_n$ then we can also solve it for the entire $S$. The set $\mathcal{F}_n$ has size $\Theta(n^2)$.

The fastest algorithm known for finding order statistics (i.e., the $k$th smallest element) in $\mathcal{F}_n$, due to Patrășcu and Pawlewicz, runs in time $\tilde{O}(n^{2/3})$. This is much slower than the complexity you're interested in, $O(\log n)$.

It is possible that considering the multiset instead of the set makes the problem easier.

$\endgroup$
  • $\begingroup$ Thank you for the reference. In this paper, which is references in the one you posted, the authors show that it would be possible to factorize a natural number in polynomial time if it would be possible to determine the element in the sequence at some index in polylog-time. However, their prove uses the property that the elements in the Farey sequence are completely reduced. So maybe the multiset version of the problem would work out well...Thanks so far. $\endgroup$ – user1742364 Sep 1 '15 at 9:28
2
$\begingroup$

I don't see how to achieve what you want for arbitrary $k$. However, for small $k$, it is possible to solve this problem efficiently. In particular, it's possible to find the $k$th smallest element in $O(k \log k)$ time.

Use a priority queue (min-heap). Initially, insert $1/B$ into the priority queue. Then, do the following $k$ times:

  • Remove the smallest element from the priority queue, say $a/b$. Output $a/b$, and then insert both $(a+1)/b$ and $1/(b-1)$ into the priority queue (assuming they're in $S$).

This does at most $2k$ insertions into the priority queue and $k$ delete-mins; also, the size of the priority queue is $O(k)$, so the total running time is $O(k \log k)$. This answer treats $S$ as a set rather than as a multiset.

$\endgroup$
  • $\begingroup$ Thanks for the response. For the moment, I will stick to Yuval's suggestion since $k$ can be as large as $\mathcal{\Theta}(A \cdot B)$ in my case. $\endgroup$ – user1742364 Sep 1 '15 at 9:22

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.