Изменения

Предположим, что простых чисел конечное число. Тогда любое число <tex>n = {p_1}^{\alpha_1}{p_2}^{\alpha_2}\dots{p_k}^{\alpha_k}</tex>, где <tex>k</tex> {{---}} это некоторая константа. Возьмём <tex>n</tex> наибольшей колмогоровской сложности. Тогда <tex>KS(n) \geqslant \log_2 n</tex>, но также <tex>KS(n) \leqslant 2 k \log_2 \log_2 n + c</tex>, т.к. <tex>\alpha_i \leqslant \log_2 n</tex>. Но это неравенство не будет выполняться на достаточно больших <tex>n</tex>, противоречие.

}}

== Источники ==