3
$\begingroup$

Take a list of the first $n$ primes $P_n=\{2,3,5,7,11,\ldots\}$ and convert the sequence into a binary string

$$S_n = 101110111\ldots$$

Compress the string with your favorite compression algorithm (the details don't matter) and let the size of the string after compression be $C(S_n)$. Compare this to the average over permutations $\pi$ of the string $\left < C(\pi S_n) \right >$, or random strings of 0, or 1 of the same length $C(R_N)$. Why does it seem to be true that

$$ C(S_n) < \left < C(\pi S_n) \right > \approx C(R_N) $$

implying that primes are compressible!

For example, when $N=2^{21}$, using zlib as a compression algorithm and average over 20 trials:

$$ \frac{C(S_n)}{\left < C(\pi S_n) \right >} \approx .761 $$

What is this "redundant data"?

$\endgroup$
5
$\begingroup$

It turns out that storage of primes can be compressed by an arbitrary amount, though the storage needed is exponential in the compression factor.

Note: This has been corrected and been made more precise.

Let $p_n$ be the $n$-th prime (with $p_1 = 2$), and let $P_n$ be the product of the first $n$ primes, so that $P_1 = 2, P_2 = 6, P_3 = 30, P_4 = 210$.

If we do a sieve of Eratosthenes, sieving out multiples of the first $n$ primes, all that are left are the first $n$ primes and the numbers relatively prime to $P_n$.

For example, for $n=2$, the numbers left are $2, 3$, and the forms $6m+1$ and $6m+5$. For $n=3$, the numbers left are $2, 3, 5$ and the forms $30m+1,7,11,13,17,19,23,$ and $29$.

For general $n$, the numbers remaining are of the form $P_nm+q_i$, where the $q_i$ are the numbers from $1$ to $P_n-1$ relatively prime to $P_n$.

To illustrate, I will use the case $n=3$.

Each block of 30 numbers in a range $30m+1$ to $30m+29$ can have as most $8$ primes as shown above. Therefore, only one bit is needed for each of these $8$ possibilities, to indicate whether or not that value is actually prime. Therefore, storage of primes can be compressed by a factor of $\frac{8}{30} \approx 0.267$.

Here is what happens for general $n$.

The $P_n$ values in the range from $mP_n$ to $(m+1)P_n-1$ are compressed to $\phi(P_n)$ bits, where $\phi(m)$ is Eu;er's phi function (though he lets me use it) that counts the number of integers from $1$ to $m$ relatively prime to $m$.

Since $\phi(P_n) = \prod_{i=1}^n (p_i-1) $, the compression factor is $\dfrac{\phi(P_n)}{P_n} =\prod_{i=1}^n (1-\dfrac1{p_i}) $. Since this goes to zero (because $\sum_{i=1}^n \dfrac1{p_i} \sim \ln \ln n $ - this is Merten's theorem), the amount of compression can be arbitrarily large, though about $e^n/n$ bits are needed.

To see this, by one of the corollaries of the prime number theorem, $P_n \sim e^n$, and $\dfrac{\phi(P_n)}{P_n} =\prod_{i=1}^n (1-\dfrac1{p_i}) \approx e^{-\ln \ln n} = 1/\ln n $. Therefore, each block of $P_n$ values can be represented by about $\frac{P_n}{n}$ bits.

Therefore, using a sieve with the first $n$ primes and the numbers relatively prime to $P_n$ can compress the primes by about a factor of $n$.

Therefore the primes can be compressed by an arbitrary amount, though the amount of storage needed is exponential in $n$.

A number of years ago, I used this idea with $n=4$, so I got a compression of $\frac{1\cdot 2\cdot 4\cdot 6}{2\cdot 3\cdot 5\cdot 7} =\frac{8}{35} $.

$\endgroup$
  • $\begingroup$ Ah I think I see now, despite the representation (e.g. the variants purposed by Ted) a compression algorithm that relies on a block scheme (like zlib) will naturally fall into a length commensurate with the block. Nice insight - thanks! $\endgroup$ – Hooked Sep 29 '13 at 22:39
1
$\begingroup$

Primes are always odd, so the last bit is always 1 (except for the initial prime 2, of course). So there is definitely some redundancy.

Another consideration is that your description scheme (listing all the bits of every number) is not optimal. To describe any subset of $\{1,2,\ldots,n\}$ takes at most $n$ bits, since there are $2^n$ such subsets. We just have one bit corresponding to each number telling us whether that number is in or out of the subset.

For the particular subset you are considering (the primes), under the description scheme you are using (listing the bits in succession), there are about $\frac{n}{\ln n}$ elements (Prime Number Theorem), and each one has about $\log_2{n}$ bits. So the number of bits in your description is approximately $\frac{n}{\ln n}(\log_2{n}) = n (\log_2{e})\approx 1.44 n.$

$\endgroup$
  • $\begingroup$ Just tested this idea by removing the last bit of each prime numbers binary representation and the ratio is still ~.80, so this doesn't quite answer the question. $\endgroup$ – Hooked Sep 29 '13 at 6:14
  • $\begingroup$ See edits for another consideration, probably has much greater effect than the 1 bits at the end. $\endgroup$ – Ted Sep 29 '13 at 6:31
  • $\begingroup$ every prime also starts with a $1$, so the first bit is also always $1$. $\endgroup$ – mercio Sep 29 '13 at 7:24
  • $\begingroup$ @Ted I've reran the results with the more efficient representation you've suggested. In this case we still have the same ~80% ratio between the prime sequence and the permuted sequence, but now both sequences compress far better than the random sequence (presumably due to the fact that there are more 0's than 1's). So I really appreciate the effort, but neither explanation describes why the prime sequence compresses over a permutation of the same sequence. $\endgroup$ – Hooked Sep 29 '13 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.