Kolmogorov complexity of primes vs. composites in the limit? If we take two natural numbers of roughly equivalent magnitude where one is prime and the other is composite, will the Kolmogorov complexity of one or the other tend to be higher as we approach infinity?
I originally suspected primes would be incrementally more complex (I believe this is true for small numbers), but I have no idea about what to expect with arbitrarily large numbers.
My one observation is that if you take $p\in\mathbb P$ large enough, then its K-complexity immediately has an upper bound of $K(\pi(p))+C$, where $C$ is some constant necessary to encode the enumeration of primes, so we do know that every sufficiently large prime is at least somewhat compressible.
Since many nearby composites are bound to be algorithmically random, perhaps there's a case to be made that primes are actually simpler in the limit. On the other hand, if you're considering the mean complexity over some range of numbers, it seems likely there are similar counterarguments about exploiting the factorability of composites.
 A: Indeed the probability that the Kolmogorov complexity of a uniformly random prime with $n$ bits is less than that of a uniformly random composite with $n$ bits goes to $1$ as $n\to\infty$.
The average Kolmogorov complexity of all $2^{n-1}$ numbers with $n$ bits is at least $n-1$, since we can’t do better overall than encode each of them in $n-1$ bits (dropping the initial $1$ they have in common). (I don’t know a formal proof for that, but it would seem to follow from the fact that for equiprobable symbols a Huffman code with equal bit lengths is optimal – you can’t save bits overall by shortening the descriptions of some compressible numbers because that wastes coding space for others, e.g. shortening one number’s description by one bit forces at least two other descriptions to be extended by one bit.)
As you note, the Kolmogorov complexity of primes (for some fixed description language) is at most $\log_2\pi\left(2^n\right)+C\approx\log_2\frac{2^n}{\log 2^n}+C=n-\log_2n+C'$ for some constant $C$. Similarly, the Kolmogorov complexity of composites is at most $n+D$ for some constant $D$. Now let $x$ denote the fraction of numbers with $n$ bits with Kolmogorov complexity at most that of the above upper bound for primes. Then the average Kolmogorov complexity of all $2^{n-1}$ numbers with $n$ bits is at most
$$
x(n-\log_2n+C')+(1-x)(n+D)=n+D+x(C'-D-\log_2n)\ge n-1\;.
$$
For sufficiently large $n$, the coefficient of $x$ is negative, and solving for $x$ yields
$$
x\le\frac{D+1}{\log_2n+D-C'}\to_{n\to\infty}0\;.
$$
Thus, while the proportion of composite numbers goes to $1$, the proportion of numbers with Kolmogorov complexity below the upper bound for primes goes to $0$, so eventually almost all composite numbers have higher Kolmogorov complexity than all primes.
