Algorithmic complexity of primes

[DavidK]

Every number can be considered a bit string. For a bit string one can define some algorithmic complexity (the shortest algorithm/program that reproduces the desired bit string). Can something be said, in general, about difference in complexity for primes as compared to composites?

 

[Hurkyl]

There are roughly (2^n / (n log 2)) primes of bit length n or less. (Since $\pi(x) \approx x / \log x$)

The best possible compression scheme is to represent each prime by its index, so that we use the positive integers less than roughly (2^n / (n log 2)) to represent the primes. It takes roughly (n - lg n - lg log 2) bits to denote such numbers.

(A good descriptive complexity scheme will be worse than this by some fixed additive constant)

However, $n - \mathop{\mathrm{lg}} n - \mathop{\mathrm{lg}} \log 2 \in \Theta(n)$, so asymptotically, we haven't saved anything.