Is entropy of prime numbers smaller?

Question

Seems that entropy (in information theory) can be expressed as a measure of how unpredictable is each bit of information.

I have done a little experiment: I've measured entropy of the binary representation of numbers, and averaged the results for primes and composite numbers.

To calculate entropy, I use Shannon entropy, which can be expressed as $-\sum_{i}P(x_i)·log_2 (P(x_i))$. This relates the appearance of each symbol (0 or 1) with how much it was expected to appear. For example, 5 is 101 in binary, so 1 is expected 2 times and 0 is expected once. From there, $P(0)=1/3$ and $P(1)=2/3$, and the entropy of 5 is 0.918296 bit/symbol.

Here are the results, showing range and average entropy for primes and composites:

1-9  Avg:  Primes: 0.4796 bit/symbol (4 items)  Composites: 0.7296 bit/symbol (5 items)
1-99  Avg:  Primes: 0.7795 bit/symbol (25 items)  Composites: 0.8763 bit/symbol (74 items)
1-999  Avg:  Primes: 0.8801 bit/symbol (168 items)  Composites: 0.9210 bit/symbol (831 items)
1-9999  Avg:  Primes: 0.9276 bit/symbol (1229 items)  Composites: 0.9403 bit/symbol (8770 items)
1-99999  Avg:  Primes: 0.9481 bit/symbol (9592 items)  Composites: 0.9541 bit/symbol (90407 items)
1-999999  Avg:  Primes: 0.9580 bit/symbol (78498 items)  Composites: 0.9625 bit/symbol (921501 items)

Seems that primes have less entropy than composite numbers. I cannot go any further with my computer but, is there any reason why entropy in prime numbers should follow a particular rule?

(Source available at: https://gist.github.com/jjmontesl/2dcf59267b1a5f3827a4)

Answer 1

This can be easily explained as this:

Shannon entropy: The distance of an n dimensional rectangular solid object from an n dimensional hypercube of the same circumference.

If you take a close look at the formula of entropy: $-\sum_{i}P(x_i)*log_2(P(x_i))$, you can see that it has a maximum when the probabilities of all $x_i$ are exactly even, in this case it is for $x_1=x_2=1/2$.

Shannon entropy is here nothing more than the area of a rectangle with some rearranged sites of a circumference 4, the nearer to a perfect square the bigger will be it's entropy since a square always has the maximal area.

For the general case, Shannon entropy is the volume of the n-dimensional hyperrectangle of a circumference $3*2^{n-1}$, the further the arrangement of the sites is apart of a hypercube, the less is the volume and the entropy as such.

Now your question is easy to explain, since binary numbers like $111000, 110100,110010,101100,101010,100110$ can never be a prime number, since they are divisible by 2, while at the same time, the remaining combinations which are not divisible by two: $110001,101001,100101,100011$, can still be composite.

Answer 2

The prime number is often stated as $\pi(x) \approx \frac{x}{\log x}$ meaning that the number of primes less than $x$ is that much.

However we can have probabilistic interpretation as $\frac{\pi(x)}{x} = \frac{1}{\log x}$ so the odds of a randomly chosen number at random is $\frac{1}{\log x}$. But what exactly is $\log x$ it is more or less the number of digits of $x$ so the prime number basically says:

$$ \mathbb{P}[n \text{ is prime}] = \frac{1}{\#\text{ of digits of }n}$$

Please look at Don Zagier's work in The First 50 Million Primes where he discusses computer simulations related to the prime number theorem.