0
$\begingroup$

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.

$\endgroup$

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.