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.