Given a positive strictly monotonically increasing infinite sequence $n_1, n_2, \dots$ with Kolmogorov complexity

$$K(n_i)\geq\lceil\log_2 n_i\rceil/2\,.$$

If $q_i$ is the greatest prime number that divides $n_i$, I've been asked to show to show that the set $Q=\{q_i\}_{i>0}$ is infinite. How do I do this?

My idea was to assume if it is finite, then we can write all $n_i=p_1^{r_1}...p_k^{r_k}$. So all the the information is encoded by $(r_1,...,r_k)$. We can recover the number by a program merely with input $r_1,...,r_k$. And I want to deduce such program can have length shorter that the given function.


Your Answer

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

Browse other questions tagged or ask your own question.