# Algorithmic complexity of primes

## Main Question or Discussion Point

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?

Related Linear and Abstract Algebra News on Phys.org
Hurkyl
Staff Emeritus
Gold Member
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.

Last edited: