Simple storage problem (math)

[bigpooch]

Suppose you have a "business card" CD and let's assume it
can hold 55 MB which we'll take as 440 million bits. Let's
also not worry about "CD rot" (or maybe we have decided to
make three copies and use a "majority rule" in case of any
loss of integrity).

Show that you can "essentially" store all the prime numbers
less than 2.29 x 10^9 on the CD.

[ncray]

For the first 5 bits of the disc, map the integers to whether they are prime or not

integers: 1 2 3 4 5
is prime? 0 1 1 0 1

After that, you kill all multiples of 2, 3, and 5
1/2 of all integers are multiples of 2
1/2 of the integers are odd, and out of the odd integers, 1/3 are multiples of 3, so 1/6 of the remaining integers are odd multiples of 3
1/16 of all integers are multiples of 5 and not of 2 and 3

So we have thrown out 1/2 + 1/3 + 1/16 = 0.8958333 of all integers

Now map the remaining integers to whether they are prime or not
Integers:
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25...
Remaining integers after throwing out multiples of 2, 3, 5:
7 11 13 17 19 23 29 31 37 41 43 47 49
Is prime?
1 1 1 1 1 1 1 1 1 1 1 1 0

So we only need approximately (1-0.8958333) * 2.29*10^9 = 2.39*10^8 bits, which is easily less than 4.4*10^8.

So the first couple bits end up looking like:
0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0
.........|....................................
To the left of the | represents primality of 1, 2, 3, 4, 5
To the right represents primality of integers > 5 which are not multiples of 2, 3, 5.

[bigpooch]

Not quite, but you are on the right track.

Out of the integers between 7 and n, 1/2 are not divisible
by 2, (1/2)(2/3) = 1/3 are not divisible by 2 or 3, and
(1/2)(2/3)(4/5) = 4/15 are not divisible by 2, 3 or 5.

That's not quite the ratio desired, but the answer should
now be obvious.

[furyshade]

there is an equation n/ln(n) which will estimate the number of primes less than n, so the answer is 2.29e9/ln(2.29e9) for the approximate number of non primes. i dont know about the storage space stuff but the approx number of primes is 106,255,539

[gumpzilla]

[ QUOTE ]
there is an equation n/ln(n) which will estimate the number of primes less than n, so the answer is 2.29e9/ln(2.29e9) for the approximate number of non primes. i dont know about the storage space stuff but the approx number of primes is 106,255,539

[/ QUOTE ]

The majority of those are going to be 8,9,10 digit numbers, which will take 24-30 bits to store. Naively storing all of them is going to exceed your bit budget considerably.

[Phil153]

[ QUOTE ]
there is an equation n/ln(n) which will estimate the number of primes less than n, so the answer is 2.29e9/ln(2.29e9) for the approximate number of non primes. i dont know about the storage space stuff but the approx number of primes is 106,255,539

[/ QUOTE ]
That's just an estimate though - a bounding function exists and should be used if we want a rigorous answer (it's on wikipedia if anyone is interested).

[pzhon]

[ QUOTE ]
[ QUOTE ]
there is an equation n/ln(n) which will estimate the number of primes less than n, so the answer is 2.29e9/ln(2.29e9) for the approximate number of non primes. i dont know about the storage space stuff but the approx number of primes is 106,255,539

[/ QUOTE ]
That's just an estimate though - a bounding function exists and should be used if we want a rigorous answer (it's on wikipedia if anyone is interested).

[/ QUOTE ]
It's much easier to compute the number of primes than to determine what they are. For example, you can use inclusion-exclusion from a list of primes up to the square root of the number, and it's not hard to produce a list of primes under sqrt(2.29 billion) < 50,000. Once the number is computed, it can be written at the start.

There are 111,720,807 = k primes less than 2,290,000,000= n. n choose k has about 193.86 million digits in decimal, or about 644 million digits in binary. That's a bit too large to fit inside 440 million bits.

So, using that there is only one even prime, the other 111,720,806 are a subset of the 1,145,000,000 odd numbers. The number of such subsets has about 528 million digits in binary. Doing the same for 3 gives a subset of size 111,720,805 out of a set of size roughly n * 1/3. The number of such subsets has about 458 million digits in binary. Taking out the numbers divisible by 5 gives a subset of 111,720,804 of a set of size roughly n * 4/15. The number of such subsets has about 419 million digits in binary, so a particular subset can be expressed as a binary number with under 420 million binary digits.

[bigpooch]

This is interesting, but does use the knowledge about the
exact number of primes <2.29 x 10^9, although it's quite
easy to compute.

Without having to compute this (perhaps you simply want to
fit as many primes in the CD but don't know EXACTLY how much
space you have), you could consider those positive integers
that are relatively prime to (2x3x5x7x11x13) = 30030. For
every consecutive 30030 numbers, only 5760 are comprime or
a ratio of 576/3003 = 192/1001, so for 440 million bits,
the primes up to about 440 million x 1001/192 or about
2 292 958 000 can be essentially stored on the CD.

OTOH, if there is an upper bound for which primes need to
be found, computing the exact number of primes helps reduce
the amount of space significantly.

[Siegmund]

For sufficiently large numbers, it becomes more efficient to store the sizes of the gaps between them, that to store zeroes and ones for the possible candidates. You are not THAT far from reaching this bound -- in fact, I wouldn't be surprised if you already had. (That is, gumpzilla isn't THAT far off base with his suggestion - the numbers just aren't quite big enough to use it from the start. Maybe store bits as above up to 100 million, and storing gap sizes later, would be more compact.)

Or - putting it another way - except for the first few lines, that 440-million-bit file mentioned above consists almost entirely of bytes containing eight 0s, or seven 0s and a 1.

That means your easiest solution, rather than applying a third kind of encoding to the list... Applying even the simplest kind of file compression to your list would let you fit at least another billion into your 55MB.

[pvn]

You can just write a program that finds prime numbers and leave the rest of the space on the CD for nekkid pix.