# Connecting information entropy to the prime number theorem for compression of numbers?

1. Prime number theorem states how often primes occur (approx. how densely they are distributed).
2. The Shannon theorem of information entropy gives us a lower bound of how much data is at least required to store some information.
3. Prime factorization theorem allows us to uniquely map each positive integer number to a set of prime exponents.

Can these things be combined somehow to create a number system which is on average more efficient, than say for example the binary number system?

• Define "more efficient". – Gerry Myerson Oct 20 '18 at 11:10
• @GerryMyerson : require less bits on average to store a number. – mathreadler Oct 20 '18 at 11:15
• How many bits does the binary number system require on average to store a number? – Gerry Myerson Oct 20 '18 at 11:19
• @GerryMyerson if we just use first or second complements it's $\lceil\log_2(N)\rceil$ bits where $N$ is the number of maximal size we want to be able to represent. – mathreadler Oct 20 '18 at 11:21
• OK, you're introducing a couple of new concepts into the discussion. One, if you have a known distribution on the numbers then you want to do a Huffman encoding, q.v. Two, if you don't want to just store the numbers, but you want to do arithmetic on them, then sure representing by prime decomposition beats binary for multiplication, but it loses bigtime for addition and subtraction. You really have to decide what it is you want to do, before you can ask a sensible question. – Gerry Myerson Oct 20 '18 at 21:51