Find a function that combines a set of integers and outputs an integer. This output can be used to deduce the absence of any integer in the set.

Question

Lets say that I have 50 events that generate some unique number (you are free to choose the number, but they should all fit in a 32 bit variable). I want to combine those numbers into a single number(32 bit), which can be used to find the absence of an event (i.e. a number).

If it was just ~10 events, I could have just used prime numbers and multiplied them, but multiplying first 50 primes results in 1.9x10^91 (which will not fit in a 32 bit variable).

Can anyone think of a better way to do this?

Answer 1

Well, is it only one missing event you want to detect? It you need to be able to detect the presence or absence of all 50 events, this means distinguishing between $2^{50}$ possibilities which obviously cannot be done with 32 bits. However if you wish to just detect a single missing event, here is a way that will work. Assume you have m events.

1. Assign each event a sequential number starting at 2.
2. Calculate $c = (m+1)! \mbox{mod}~p$, where p is some prime number greater than m+1 but less than $2^{32}$.
3. When registering the events, simply multiply the numbers corresponding to the events sequentially modulo p. Call this result r.
4. To determine if an event is missing, calculate $x = (c \times r^{-1}) \mbox{mod}~p$. If $x=1$ then no events are missing, otherwise $x$ is the label for the missing event.

UPDATE

A simpler solution (coming from Jukka's comment) is simply to do the following:

1. Assign each event a sequential number starting at 1.
2. Calculate $c = \sum_{j=1}^m j~ \mbox{mod}~2^{32} = \frac{j(j+1)}{2} \mbox{mod}~2^{32}$.
3. When registering the events, simply add the numbers corresponding to the events sequentially modulo $2^{32}$. Call this result r.
4. To determine if an event is missing, calculate $x = (c - r) \mbox{mod}~2^{32}$. If $x=0$ then no events are missing, otherwise $x$ is the label for the missing event.

Answer 2

You can use "binomial encoding" (I forgot the real name). As Joe suggested, we can store the information "the set contains all numbers but for those in S" for any S of size at most 9. The question is how to find a bijection between subsets of $[50]$ of size at most 9 and numbers between 0 and 13432735555 (as it happens).

Let's generalize by replacing 50 with $n$ and 9 with $k$. We use the notation

$$ D(m,t) = \sum_{s=0}^t \binom{m}{t} $$

This quantity satisfies Pascal's identity $D(m,t) = D(m-1,t) + D(m-1,t-1)$ (but different initial conditions: $D(0,t) = 1$). We can use this to encode all subsets of size at most $k$ using the numbers up to $D(m,t)$ by using the first $D(m-1,t)$ numbers for the case in which $0 \notin S$, and the next $D(m-1,t-1)$ for the case in which $0 \in S$; continue recursively.

An alternative way is to first encode the size of the set (implicitly) and then use binomial coefficients instead of their running sum. In that approach, the first $\binom{n}{0}$ integers are used for $|S|=0$, the next $\binom{n}{1}$ are used for $|S|=1$, and so on; once in the given range, we do the same thing as before (with binomial coefficients). The advantage of this variant is that smaller sets get smaller numbers.

Answer 3

An extremely simple (but not optimal) solution is to just pick an appropriate set of 32-bit labels like

809304A4 81086020 85408488 86001692 8847B001 90345788 B5B20840 E0300CB0
F2509412 00201046 00220002 002881C5 00401294 00473641 00908800 00E03790
010488F0 01100801 0110A012 01444A06 02B81688 04212440 044818B8 05EC2980
080000C8 08C27034 08C41000 10900521 13408948 14A00284 19189450 1CA9C469
20100542 20901B3A 210760A5 21450B84 22904411 283A0220 2C850080 31400049
34C44604 407C4260 4A465204 5CE00080 6080166C 61A93080 62080010 6300084B
68490802 6CA08029

and then take XOR of all labels that are present. I think this particular set of labels allows you to identify up to 5 missing events. This might be close to the spirit of your question; the part of "combining" the numbers is extremely simple.

---

However, something to keep in mind with any approach. As you can't identify an arbitrary set of missing events with 32-bit labels, then you might have different kinds of weaker goals like these:

1. Detect if there are any missing events.
2. Count the exact number of missing events.
3. If the number of missing events is at most $k$, find out what are the missing events.

For example, this particular approach solves the goal 3 (for $k = 5$) but not necessarily goals 1 and 2. It would be good if you clarified what are the exact requirements.

Answer 4

It isn't clear to me from the question whether more than one event could be missing. Here I propose a solution for the case where only 1 event is missing.

Assign values based on a Golomb Ruler - ``a set of non-negative integers such that no two distinct pairs of numbers from the set have the same difference''.

Here is a set of mark locations for a 51-mark Golomb Ruler:

     1     8    26    39   149   223   247   355   384   419
   439   485   506   508   548   585   644   650   761   900
   936   950  1018  1035  1040  1110  1168  1217  1244  1289
  1322  1337  1480  1489  1492  1508  1670  1732  1785  1815
  1826  1858  1912  1983  2043  2095  2099  2146  2156  2190

The maximum value if all 50 events are present is 2190. Subtract the value returned by the function from this to determine which distance is missing and look it up to determine which event is missing.

Example: If the function return value is 2183 then the missing value is the one with distance 2190-2183 = 7. The 2nd mark has distance 7 therefore the event associated with that mark was not seen.