# Kolmogorov complexity of a sequence of prime numbers

Let's say $p_1, p_2, p_3, \ldots$ is the increasing sorted sequence of all prime numbers. Prove that there exists a constant $n_0 \in \mathbb{N}$, so that for all $n \ge n_0$: $$K(p_n) < \log_2(p_n) − 2.$$ Hint: Prime number theorem: $p_n \in \Theta (n \ln n)$.

I think, I could have a program A, which generates $p_n$ in $n\ln n$. I could just give A the index of my prime number and it would generate it.

Another idea of mine was to prove it by contradiction and assume the opposite is true but I can't really make that work. My biggest problem is that I can't find an upper limit to the representation of prime numbers and start from there. Normally I'd just use the factorization for integers…

Any help is appreciated!

• What do you mean by "generates $p_n$ in $n\ln n$"? Neither the prime number theorem nor Kolmogorov complexity is about running time. – Yuval Filmus Feb 2 '17 at 13:46
• I pretty much meant what you're stating in your answer but I couldn't really bring it together because I got confused with the running time… – Seen Feb 2 '17 at 13:59

Since we can generate $p_n$ given $n$, $K(p_n) \leq K(n) + O(1) \leq \log_2 n + O(1)$. The prime number theorem implies that $p_n = \Theta(n\ln n)$, and so $\log_2(p_n) = \log_2 n + \log_2\log_2 n \pm O(1)$. You take it from here.
• It doesn't really matter, since $\ln n = \ln 2 \cdot \log_2 n$. So both expressions coincide, the difference being swallowed by the $O(1)$ error term. – Yuval Filmus Feb 2 '17 at 14:17
• @YuvalFilmus, I may misunderstand what your notation is supposed to mean, but I don't see how the difference between $\log_2 n$ and $\ln n$ can be bounded by a constant term for all $n$. – Pontus Feb 3 '17 at 9:37