# Is entropy of prime numbers smaller?

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)

• Could you summarize, maybe with a small example or two, how you calculate the entropy of a number? – Barry Cipra Oct 1 '15 at 19:22
• Thanks for your comment. I added information about how I calculated entropy to the question. – jjmontes Oct 1 '15 at 19:39
• Thanks for the explanation. It's possible what you're seeing is actually due to the fact that even numbers are guaranteed to have a $0$ to balance out the lead $1$ while odd numbers are not. I'd recommend rerunning your program over just the odds, to see what happens. – Barry Cipra Oct 1 '15 at 19:52
• I can't make sense of your definition of Shannon entropy. What is the range of $i$? Is it $0$ to $1$? What is the logarithm base? Is it $2$? Would I be right in thinking that your definition always gives a value $\le 1$? Surely large numbers should have bigger entropy? – TonyK Oct 1 '15 at 19:57
• @jjmontes, I think there's a bug in your program: It looks like you're only computing $-P(0)\ln(P(0))$, not $-P(0)\ln(P(0))-P(1)\ln(P(1))$. That is, I finally figured out that $0.366204=-(1/3)\ln(1/3)$. This begins to make sense of the averages you're getting, since $-(1/2)\ln(1/2)=0.34657$. Basically what's happening is that large numbers, whether prime or composite, tend to have half $0$'s in their binary expansion. – Barry Cipra Oct 1 '15 at 20:25

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}$$