The Prime Wavelet Tree: Compressing the Carmichael Numbers

We present two number-theoretic compression techniques. The first is $\mathit{\text{local}}$, and compresses individual numbers. The second is $\mathit{\text{global}}$, and compresses the entire set of numbers using a $\mathit{\text{prime}}\mathit{\text{wavelet}}\mathit{\text{tree}}$, which is a data structure of independent interest. Our techniques apply to any set of numbers satisfying a Korselt-like criterion. We demonstrate our compression techniques using the recently completed tabulation of all $\mathrm{308,279,939}$ Carmichael numbers less than ${10}^{24}$ that occupies $18.4$ gigabytes as text. When combined with standard compression techniques and a heuristic choice of divisors, the resulting file is $588.7$ megabytes ($31.2$ times smaller than the text file). The initial $80$-bit numbers now use about $15.3$ bits.