An infinite subsequence of random numbers in Kolmogorov sense Is it possible to construct an infinite increasing sequence of random naturals (in Kolmogorov sense) that is a subsequence of another sequence? Ok, in general I suppose not, e.g. for prime numbers. But:

I want to prove that sequence $\{ax+b\}_{x\in\mathbb{N}}$ contains an infinite subsequence of random numbers. (This is, more-or-less, a statement in an exercise).

EDIT: The actual statement is to show that $\limsup\limits_{x\to\infty}\frac{C_U(ax+b)}{\log (ax+b)}=1$.

I believe the existance of infinitely many random numbers in general, stems from the fact that for a given $k$ we have $|\{x\in\{0,1\}^k: C_U(x)&lt; k\}|&lt; 2^k$ because there are less binary strings of length $\leq k-1$ which may represent input to $U$. So no matter how large a binary representation, we can always find a random number with such a representation (in terms of its length). So, assuming longer $x$ means larger number it represents, we have infinitely many random numbers.

But what about here? We'd want those numbers to be of very specific form. Is there a way to do that? Could you give me a hint?
If $x$ is Kolmogorov random then $C_U(ax+b) \geq \log x - O(\log a + \log b + 1)$ (why?), and so
$$
\frac{C_U(ax+b)}{\log (ax+b)} \geq \frac{\log x - O(\log a + \log b + 1)}{\log x + O(\log a + \log b + 1)} = 1 - O\left(\frac{\log a + \log b + 1}{\log x}\right).
$$
Since there are infinitely many Kolmogorov random numbers $x$, your result follows.