primes_entropy.py

#!/usr/env/python

import math
from itertools import count, islice

# Running this program shows:
# 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)


def is_prime(n):
    if n < 2: return False
    return all(n % i for i in islice(count(2), int(math.sqrt(n)-1)))


def entropy(num):

  count = [0, 0]
  binary = ""

  curr = num
  while curr != 0:
    last_bit = curr & 1
    binary = str(last_bit) + binary
    count[last_bit] += 1
    curr = curr >> 1
    
  numbits = count[0] + count[1]
  p0 = float(count[0]) / numbits
  p1 = float(count[1]) / numbits
  ent = - ( ((p0 * math.log(p0, 2)) if p0 > 0 else 0) + \
        ((p1 * math.log(p1, 2)) if p1 > 0 else 0 ))

  #print "%f %s" % (ent, binary)        
  return (ent, binary)


def stat_primes(max_num):

  tots = { False: 0.0, True: 0.0 }
  ncount = { False: 0, True: 0 }

  for i in range(1, max_num, 2):  # Using only odd numbers

    if i % 2 == 0:
      pass

    (ent, binary) = entropy(i)
    prime = is_prime(i)

    tots[prime] += ent
    ncount[prime] += 1
    
  print("%d-%d  Avg:  Primes: %.4f bit/symbol (%d items)  Composites: %.4f bit/symbol (%d items)" % (
        1, max_num - 1,
        tots[True] / ncount[True], ncount[True],
        tots[False] / ncount[False], ncount[False] ))
  
stat_primes(10)  
stat_primes(100)  
stat_primes(1000)  
stat_primes(10000)  
stat_primes(100000)  
stat_primes(1000000)  
#stat_primes(10000000)  
#stat_primes(100000000)