[math-fun] compressed bitmaps of the primes?
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.
Well, I do have a sieve program that outputs bitmaps, but these bitmaps represent a sequence of 30 integers with a single byte (the eight values mod 30 that are not divisible by 2, 3, or 5.) Running this to a 1GB data file (representing all primes less than 32,212,254,720) and compressing the resulting file, I see the following sizes: 1073741824 primes.dat 798639547 primes.dat.bz2 761814389 primes.dat.gz 761814523 primes.zip I'm a bit surprised the compressors don't do better; just using arithmetic coding and the probability of a zero or one bit should give about a 0.639 compression ratio, but the best we see above is 0.709. On Tue, May 22, 2012 at 11:00 AM, Henry Baker <hbaker1@pipeline.com> wrote:
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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
The unique simple group of order 168 -- call it G_168 -- is the second-smallest nonabelian simple group (after A_5) and of special interest for a number of reasons. It happens to be isomorphic to (==) both PSL(2,F_7) and PSL(3, F_2), abbreviated as PSL(2,7) and PSL(3,2). This is one of only two non-trivial coincidences among the PSL(n, p^k) groups. (The other is that PSL(2,4) == PSL(2,5).) QUESTION: What is the most direct proof that PSL(2,7) == PSL(3,2) ? This almost seems like pure accident, since almost all PSL groups are simple and non-abelian, and there aren't many such groups of low order. But maybe there is a proof that makes the isomorphism seem natural? --Dan P.S. One reason this group is interesting is that it's isomorphic to Aut(K), the group of conformal automorphisms of the surface of genus 3 having the largest automorphism group for its genus. This is the first example of a Riemann surface of genus g whose that attains the Hurwitz bound (for g >= 2) of 84(g-1). It is realized by the Klein quartic K, the complex projective "curve" defined by the locus of roots of the homogeneous polynomial X^3 Y + Y^3 Z + Z^3 X, where [X:Y:Z] is the homogeneous coordinates of a point in the complex projective plane CP^2.
I don't know the answer, but it might be here: http://math.ucr.edu/home/baez/klein.html On Tue, May 22, 2012 at 1:29 PM, Dan Asimov <dasimov@earthlink.net> wrote:
The unique simple group of order 168 -- call it G_168 -- is the second-smallest nonabelian simple group (after A_5) and of special interest for a number of reasons.
It happens to be isomorphic to (==) both PSL(2,F_7) and PSL(3, F_2), abbreviated as PSL(2,7) and PSL(3,2).
This is one of only two non-trivial coincidences among the PSL(n, p^k) groups. (The other is that PSL(2,4) == PSL(2,5).)
QUESTION: What is the most direct proof that PSL(2,7) == PSL(3,2) ?
This almost seems like pure accident, since almost all PSL groups are simple and non-abelian, and there aren't many such groups of low order.
But maybe there is a proof that makes the isomorphism seem natural?
--Dan
P.S. One reason this group is interesting is that it's isomorphic to Aut(K), the group of conformal automorphisms of the surface of genus 3 having the largest automorphism group for its genus. This is the first example of a Riemann surface of genus g whose that attains the Hurwitz bound (for g >= 2) of 84(g-1).
It is realized by the Klein quartic K, the complex projective "curve" defined by the locus of roots of the homogeneous polynomial X^3 Y + Y^3 Z + Z^3 X, where [X:Y:Z] is the homogeneous coordinates of a point in the complex projective plane CP^2.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
I saved a monthly article about this a while back, which you can find here: https://skydrive.live.com/redir?resid=BFE66889F486A021!384&authkey=!ANW_sA8a... Sorry I can't give a more precise reference. --Jim On Tue, May 22, 2012 at 3:29 PM, Dan Asimov <dasimov@earthlink.net> wrote:
The unique simple group of order 168 -- call it G_168 -- is the second-smallest nonabelian simple group (after A_5) and of special interest for a number of reasons.
It happens to be isomorphic to (==) both PSL(2,F_7) and PSL(3, F_2), abbreviated as PSL(2,7) and PSL(3,2).
This is one of only two non-trivial coincidences among the PSL(n, p^k) groups. (The other is that PSL(2,4) == PSL(2,5).)
QUESTION: What is the most direct proof that PSL(2,7) == PSL(3,2) ?
This almost seems like pure accident, since almost all PSL groups are simple and non-abelian, and there aren't many such groups of low order.
But maybe there is a proof that makes the isomorphism seem natural?
--Dan
P.S. One reason this group is interesting is that it's isomorphic to Aut(K), the group of conformal automorphisms of the surface of genus 3 having the largest automorphism group for its genus. This is the first example of a Riemann surface of genus g whose that attains the Hurwitz bound (for g >= 2) of 84(g-1).
It is realized by the Klein quartic K, the complex projective "curve" defined by the locus of roots of the homogeneous polynomial X^3 Y + Y^3 Z + Z^3 X, where [X:Y:Z] is the homogeneous coordinates of a point in the complex projective plane CP^2.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Dan Asimov -
Henry Baker -
James Buddenhagen -
Mike Stay -
Tom Rokicki