Last active
March 28, 2022 01:58
-
-
Save jjmontesl/2dcf59267b1a5f3827a4 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment