
Re: Compress storage space of primes?
Posted:
Sep 14, 2013 3:35 AM


jonas.thornvall@gmail.com 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

