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

Question

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

X(n) = {a.X(n-1) + c} mod m

where 0 < m, 0 <= a < m, 0 <= c < m, 0 <= 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 <= k <= n) of the set {X(0), X(1), ..., X(n)} very fast? (faster than O(n) - based by sorting algorithm)

Answer 1

Assuming you're not storing the k lowest items during generation ...

If (n >= m) and the constants meet the criteria for a full period (ref here) then the k-th smallest item will be k-1.

If (n >= m) and the constants do not meet the criteria or (n < m) then you need to do a linear search which can terminate if the k-th lowest to date is k-1.