Search All of the Math Forum:

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

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

 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

jonas.thornvall@gmail.com wrote:

Three preliminary points: (i) the signature of what you're replying to
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

Date Subject Author
9/13/13 JT
9/13/13 JT
9/13/13 Peter Percival
9/13/13 JT
9/13/13 JT
9/14/13 Peter Percival
9/14/13 Victor Porton
9/14/13 JT
9/14/13 JT
9/14/13 JT
9/14/13 JT
9/14/13 JohnF
9/14/13 JT