Algorithmic complexity of primes

  • Thread starter DavidK
  • Start date
  • #1
31
0

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

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
There are roughly (2^n / (n log 2)) primes of bit length n or less. (Since [itex]\pi(x) \approx x / \log x[/itex])

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, [itex]n - \mathop{\mathrm{lg}} n - \mathop{\mathrm{lg}} \log 2 \in \Theta(n)[/itex], so asymptotically, we haven't saved anything.
 
Last edited:

Related Threads on Algorithmic complexity of primes

  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
4
Views
6K
Replies
1
Views
3K
Replies
8
Views
6K
  • Last Post
Replies
1
Views
3K
Replies
6
Views
14K
  • Last Post
Replies
6
Views
6K
  • Last Post
Replies
8
Views
3K
  • Last Post
Replies
13
Views
4K
  • Last Post
Replies
2
Views
2K
Top