The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Compress storage space of primes?
Replies: 12   Last Post: Sep 14, 2013 11:58 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Peter Percival

Posts: 2,623
Registered: 10/25/10
Re: Compress storage space of primes?
Posted: Sep 14, 2013 3:35 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply wrote:

Three preliminary points: (i) the signature of what you're replying to
should not appear in your reply; (ii) please delete the extraneous blank
lines; (iii) those blank lines are put in by Google groups, you may wish
to post using a news client to a news server.

>> I was talking about compressing the result of a prime generating
>> algorithm, not the algorithm itself.

My reply was not wholly serious, but it had a bit of a serious point.
This sequence: 2, 3, 5, 7, 11, 13, 17, 19, ... goes on for as long as
you want; you may have many gigabytes of it. An algorithm that
generates those numbers (perhaps expressed in your favourite programming
language or perhaps expressed in plain English) will only be a few bytes
long. Since the algorithm will reproduce as much of the sequence as you
want it *is* a compression of the sequence. What do you require of the
compressed version (let's call it C) of your data (D)? Two things, I
think: (i) that C occupies less space than D (preferable a lot less),
and (ii) that from C you can recover D without loss. The prime
generating algorithm C is perfect for a sequence of primes D.

Further to (i), I should remark that no compression method can compress
everything; there will be some data D such that C is longer!

> Storing a bit string of 0,1 for prime none primes is of course a way.
> But then you you would have to convert everyone when looking for a
> prime in a range.
> So it will be very ineffective searching for a prime of x digits
> where x is rather big. Even storing the full value there will be some
> search before getting to a prime in a high digit place.

Sorrow in all lands, and grievous omens.
Great anger in the dragon of the hills,
And silent now the earth's green oracles
That will not speak again of innocence.
David Sutton -- Geomanc ies

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.