Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Algorithmic complexity of primes

  1. Feb 27, 2006 #1
    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?
  2. jcsd
  3. Feb 27, 2006 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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: Feb 27, 2006
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook