Permutations
\gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\set#1{\delim\{{#1}\}} \gdef\ceil#1{\delim\lceil{#1}\rceil} \gdef\unit#1{\ \text{#1}}
n!
From CB22:
The challenge is to construct a data structure for storing a permutation that takes less space than the trivial data structure, specifically 1.44 n fewer bits, while retaining the ability to quickly evaluate the permutation.
Take a permutation over 2^{32} elements. This can be represented as a vector of 2^{32} 32-bit integers, taking 17.2\unit{GB}. In theory it can be stored in
\ceil{\log_{256} 2^{32}! } = 16.4 \unit{GB}
We can do better if we build an approximate lookup that returns a set of n elements, one of which is the permutation. Split the permutation in blocks of size n. If we ignore the order within the blocks, they can be stored in \ceil{\log_{256} {2^{32} \choose n} } bytes. If we pick a blocksize of 1427 we get 4096\unit{B}, a disk block.
