# 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?

## Answers and Replies

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