22 May
2012
22 May
'12
12:01 p.m.
Has anyone analyzed the expected size of bitmaps of the primes? Specifically, consider the set of primes less than some number N, and then represent those primes as "1" bits in a bit vector of length N. Then compress this bit vector using common techniques such as zip, gzip, 7zip, etc. What is the growth rate of such compressed bitmaps as a function of N? Are these schemes any better than a simple run-length encoding? Has anyone even performed any experiments? Thanks in advance for any info. P.S. Yes, I know, you can encode the entire infinite bitmap in a fixed/finite number of bits, where these bits encode a Turing Machine that spits out all of the primes. That's not what I'm asking here.