Say you have a large number of items, each of which could belong to multiple groups, and you’d like to assign to each item an integer which is able to encode its group memberships. The number of items could be vast, but say the number of groups is fairly small – less than a few hundred – and each item could be a member of many groups (say <= 5).
A simple way to do this, is to assign to the groups a set of numbers which are pairwise not divisible by each other: call this \(g_1,...,g_M\). Then, if an item is in groups 1,4 and 7 (for example), its item number can be set to the product of the groups it is a member of: \(n_i = g_1\cdot g_4 \cdot g_7\). To verify whether the item is a member of group \(j\), we can test \(0 \equiv n_i \pmod{g_j}\), and that’s all. This works because by construction the group numbers are not divisible by each other, so it is not possible for \(g_j\) to divide \(n_i\) if it is not factor of \(n_i\). All we have to do is now is generate \(M\) pairwise non-divisible numbers.
It helps if the numbers we assign to the groups are small, since we will be multiplying them to make our item numbers, so let’s start at 2 and collect as many as needed to make up \(M\). In doing so, notice that we would inevitably collect all the prime numbers since they do not divide anything else by definition. Notice also that any number can be expressed as a product of primes (i.e. \(x = p_1^{c_1}p_2^{c_2}...p_n^{c_n}\) where \(p_n \le x\)), so there cannot be any extra numbers between the primes that meet our non-divisibility requirement.
Here is a simple implemenation in Python with Sympy.
from sympy import sieve
from itertools import islice
from math import prod
# 100 groups
Gs = list(islice((p for p in sieve),100))
# An example group membership
In = [23, 44, 87]
# Checksum for some item i.
n_i = prod([Gs[i] for i in In])
# Assert that member of only In groups.
for j in range(100):
assert( (n_i % Gs[j] == 0) == (j in In) )
print(n_i)
> 8012581