4
$\begingroup$

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!

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ What do you mean by "generates $p_n$ in $n\ln n$"? Neither the prime number theorem nor Kolmogorov complexity is about running time. $\endgroup$ – Yuval Filmus Feb 2 '17 at 13:46
  • $\begingroup$ 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… $\endgroup$ – Seen Feb 2 '17 at 13:59
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry to bother but tbh I'm actually not that skilled in the use of logarithms. Shouldn't it be log2(n)+log2(ln(n))? Should I solve for n or just replace log2(n) with log2(pn / log2(n)? $\endgroup$ – Seen Feb 2 '17 at 14:08
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 2 '17 at 14:17
  • $\begingroup$ Ah ok. I think I got it now :) thanks for the help $\endgroup$ – Seen Feb 2 '17 at 14:42
  • $\begingroup$ @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$. $\endgroup$ – Pontus Feb 3 '17 at 9:37
  • $\begingroup$ @Pontus It's bounded by a constant factor. After you take the logarithm, the difference becomes a constant term. $\endgroup$ – Yuval Filmus Feb 3 '17 at 10:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.