Apologies for the length question. Those acquainted with the analytics industry will know that the next big thing in the information technology world will be the Big Data revolution where huge volumes of data will be processed. Big Data revolution will imply huge requirement of storage space/memory hence it is critical to store data as efficiently as possible. We want to store data in the smartest way that requires the least amount of storage. The following question is on the application of mathematical ideas to reduce the amount of storage memory required to store information of a particular kind.


**Problem**: This is a consumer information storage problem. There are $k$ customers and $n$ books. Each customer can buy one or more books (**without repetition**). We want to identify the book purchased by a given customer using the minimum number of memory required for storage. *We do not seek to improve the time complexity, we only seek to reduce storage space required*.


**Method 1 - Traditional approach**: This is the common and default approach. Give each book a $d$ digit code and create a field in the data base where the code of the books purchased by the customer in entered, separated by commas. So in the worst case when a customer has brought all $n$ books, we will need $D = nd+d-1$ characters to store this information (including $d-1$ commas) about the customer. 


**Method 2. Using prime numbers**: Assign a unique prime number to each of the books, 2 denotes the first book, 3 the second, $\ldots$ and $p\_n$ denotes the $n$-th. Every customer $C\_i$ assigned a number $N\_i$ which is equal to the product of the prime numbers corresponding to books purchased. By factoring $N\_i$, unique factorization theorem ensures that we can identify the exactly the books purchased by the customer. More over two customers will have a common book if and only if they have a common factor. The greater the number of common factors, the greater is the similarity between the customers. This this method in principle carries more business information. Let us do the heuristics for the number of characters needed. In the worst case when the customer $C\_i$ has purchased all the $n$ books,
$$
N\_i = p\_1 p\_2 \ldots p\_n < p\_n^n.
$$
(*This inequality can be strengthened using the estimates of the Chevyshev function of the first kind but right now, that is not the objective as I only want to demonstrate the underlying idea*). Hence the number of characters required is
$$
D\_i = \log\_{10} N\_i < n\log\_{10}p\_n < nd + d - 1
$$


for $p\_n < 10^d$ which is a safe assumption since most of the UPC code numbers given to products sold in the market have multiple digits. Hence with a small number of books say $<100$ we expect method 2 to use lesser number of character (hence memory) to store the same information. For example if I have 10 books them to store the information about a customer who purchased all the 10 books, method one with a 2 digit code for each book will require 21 characters where as method 2 will require only 10 characters. Unfortunately when there are a large number of books, the products of primes grows very fast and we may end up requiring more memory space than in method 1. Hence this method is not scale-able.


**Method 3**: We can do better than method 2. Let the $k$-th book be given the number $2^{k}$. Every time a customer buys a unique book, we add its corresponding number. Since a number can be decomposed as the sum of non-repeating powers of two in only one way, we can identify the exact books purchased by the customer $C\_i$ by decomposing his/her total sum $S\_i$. For example if the sum of the book numbers for a customer is 154, since $154=2^7 + 2^4 + 2^3 + 2^1$, we know that the customer has purchased the first, third, fourth and the seventh book. So instead of storing the code of these four books or the product of three primes, I can just store the three digit number 154 which will give me the same information. In the worst case when the customer has purchased all the n books,


$$
S\_i = 2^1 + 2^2 +\ldots + 2^n = 2^{n+1} - 2
$$


$$
D\_i < \log\_{10}(2^{n+1}-2) < n\log\_{10}2 + 1
$$


Thus with method 3, we can store the same information using the least number of characters thus far. Also two customers will have a book in common if and only if the decomposition of their sum contains an identical power of 2.


**Questions**: Is there are better method of identifying the books uniquely using less than $n\log\_{10}2$ characters? I think that if there is indeed a better method, it could possible be using some of the property of integers.



Mathematical techniques to reduce the amount of storage memory
This is one of the basic problems that led to the field of [information theory](http://en.wikipedia.org/wiki/Information_theory). It would take a while to explain all that is known about this, but the following will get you started.


Suppose we assign each book $b$ a binary string $\sigma\_b$ such that no two strings are prefixes of each other (like telephone numbers). Then a consumer's purchases can be encoded by concatenating these strings back-to-back (without separating tokens or other marks). The total number of bits used to encode all the customer's purchases is $\sum\_b n\_b|\sigma\_b|$, where $n\_b$ is the number of times book $b$ has been purchased. We now have the optimization problem of minimizing this sum subject to the constraint that no two strings are prefixes of each other. This seemingly complex constraint actually has a simple existence criterion, namely the necessary fact that $\sum\_b 2^{-|\sigma\_b|} \leq 1$. So the whole thing boils down to finding $$\min \sum\_b n\_b \ell\_b \quad\text{subject to}\quad \sum\_b 2^{-\ell\_b} \leq 1,$$ where $\ell\_b$ is the length of the binary string used to encode the book $b$.


Generalizing a bit, we can think of $p\_b = 2^{-\ell\_b}$ as a probability associated to the book $b$. Translating the above becomes the problem of finding $$\max \sum\_b n\_b \log p\_b \quad\text{subject to}\quad \sum\_b p\_b = 1,$$ where $p\_b \in [0,1]$ are no longer restricted to being powers of $\frac12$. This continuous optimization problem has solution $p\_b = n\_b/n$, where $n = \sum\_b n\_b$ is the total number of books sold. Assuming that this solution happens to be such that the probabilities $p\_b$ are all powers of $\frac12$, the total number of bits used is $$n \log\_2 n - \sum\_b n\_b\log\_2 n\_b.$$ Dividing by $n$ to get the average number of bits used per book sold we get $$\log\_2 n - \sum\_b \frac{n\_b}{n} \log\_2 n\_b = - \sum\_b p\_b \log\_2 p\_b.$$ This is the [Shannon entropy](http://en.wikipedia.org/wiki/Entropy_%28information_theory%29) of the distribution $p\_b = n\_b/n$ and this is an absolute lower bound for lossless encoding of this kind of data. Even if the probabilities are not powers of $\frac12$ encodings arbitrarily close to this bound can be achieved through [arithmetic coding](http://en.wikipedia.org/wiki/Arithmetic_coding). In the situation you describe, it seems likely that the distribution $p\_b$ is not known in advance, which is the main difficulty with achieving this optimal bound in practice.


