1
$\begingroup$

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)

$\endgroup$
  • 1
    $\begingroup$ Could you summarize, maybe with a small example or two, how you calculate the entropy of a number? $\endgroup$ – Barry Cipra Oct 1 '15 at 19:22
  • 1
    $\begingroup$ Thanks for your comment. I added information about how I calculated entropy to the question. $\endgroup$ – jjmontes Oct 1 '15 at 19:39
  • 2
    $\begingroup$ 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. $\endgroup$ – Barry Cipra Oct 1 '15 at 19:52
  • 1
    $\begingroup$ 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? $\endgroup$ – TonyK Oct 1 '15 at 19:57
  • 2
    $\begingroup$ @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. $\endgroup$ – Barry Cipra Oct 1 '15 at 20:25
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. From that paper, though, I couldn't really deduce whether Shannon entropy of the of prime numbers up to N should be lower than the entropy of the composites in the same interval, or in general, if my observation is meaningful at all or can be explained :-?. $\endgroup$ – jjmontes Jan 15 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.