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.