Complexity of large numbers. Let A(n) be the set of positive integers x for which a terminating program p of length less than or equal to n bits exists that outputs x. Let B(n) be the complement of A(n) [i.e., B(n) is the set of integers x for which no program of length less than or equal to n outputs x]. Let M(n) be the maximum integer in A(n), and let S(n) be the minimum integer in B(n). What is the Kolmogorov complexity K(M(n)) (approximately)? What is K(S(n)) (approximately)? Which is larger (M(n) or S(n))? Give a reasonable lower bound on M(n) and a reasonable upper bound on S(n).