# How to calculate the k-th smallest number of a linear congruential generator

According to Wikipedia, a linear congruential generator is defined by the recurrence relation below:

$X_{n} = (a \times X_{n-1} + c) \mod m$

where $0 < m, 0 \le a < m, 0 \le c < m, 0 \le X_{0} < m$ are integer constants that specify the generator.

If the value of $a$, $c$, $m$, $X_{0}$, and $n$ are given, can I determine the $k$-th smallest value ($1 \le k \le n$) of the set $\{X(0), X(1), ..., X(n)\}$ very fast? (faster than $O(k)$ - based by sorting algorithm)

-
Since $n$ is fixed and $k \le n$, whatever algorithm you use will be $O(1)$. –  Robert Israel Oct 11 '13 at 15:16