Prove that there are at most finitely many random (Kolmogorov random) prime numbers 
Prove that there are at most finitely many random (Kolmogorov random) prime numbers. A number is Kolmogorov random if
$$K(n) ≥ K(\operatorname{bin}(n)) ≥ \lceil \log_2(n+1)\rceil - 1.$$
Hint: You can use the prime number theorem.

I tried to prove it by contradiction but I couldn’t connect the prime number theorem and the definition of Kolmogorov randomness.
 A: You need to use both the prime number theorem and the fact that there exists a Turing machine computing the function $p_n$ given by the $n^{th}$ prime. This means the Kolmogorov complexity of a prime $p = p_n$ is bounded by the Kolmogorov complexity of $n$ plus a constant (for the size of this Turing machine). The PNT gives that $n \approx \frac{p}{\log p}$ from which it follows that $K(p)$ is approximately bounded by
$$K \left( \frac{p}{\log p} \right) + C \le \left\lceil \log_2 \frac{p}{\log p} \right\rceil + C$$
This grows like $\log_2 p - \log_2 \log p + C$ and as $p \to \infty$ the $\log_2 \log p$ term eventually (if very slowly) overtakes the constant term. So we conclude that sufficiently large primes are not Kolmogorov random, because they can be described by the Turing machine computing $p_n$ + the index $n$, which eventually becomes small enough compared to $p_n$ to compress it nontrivially.
This argument is very general and shows more generally that there are only finitely many Kolmogorov random elements of any increasing computable sequence $a_n$ such that $\lim_{n \to \infty} \frac{a_n}{n} = \infty$, or something like that.
