[14] We investigate transformations of complexity under the arithmetic operation ∗. Show that

(a) K(x ∗ y) ≤ K(x) + K(y) + O(1);

(b) If x and y are primes, then K(x ∗ y) = K(x, y) + O(1);

(c) K(x ∗ y) + log(x ∗ y) ≥ K(x, y) + O(1);

Comments. Item (c): consider the prime factorization of z := x ∗ y.

Enumerate all decompositions of z into two factors and let x, y be the jth decomposition. Use j and x ∗ y.