<p>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).</p>

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

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

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-17T01:43:23.130Z
2010-09-17T01:43:23.130Z
Yuval Filmus
<p>An extremely simple (but not optimal) solution is to just pick an appropriate set of 32-bit labels like</p>

<pre><code>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
</code></pre>

<p>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.</p>

<hr>

<p>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:</p>

<ol>
<li>Detect if there are any missing events.</li>
<li>Count the exact number of missing events.</li>
<li>If the number of missing events is at most $k$, find out what are the missing events.</li>
</ol>

<p>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.</p>

CC BY-SA 2.5
2010-09-17T09:09:29.497Z
2010-09-17T09:09:29.497Z
Jukka Suomela
<p>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.</p>

<p>Assign values based on a <a href="http://www.distributed.net/OGR/en" rel="nofollow">Golomb Ruler</a> - ``a set of non-negative integers such that no two distinct pairs of numbers from the set have the same difference''. </p>

<p>Here is a set of mark locations for a <a href="http://www.research.ibm.com/people/s/shearer/grpp.html" rel="nofollow">51-mark Golomb Ruler</a>:</p>

<pre><code>     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
</code></pre>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-17T18:50:07.840Z
2010-09-17T18:50:07.840Z
Handcraftsman
<p>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.</p>

<ol>
<li>Assign each event a sequential number starting at 2.</li>
<li>Calculate $c = (m+1)! \mbox{mod}~p$, where p is some prime number greater than m+1 but less than $2^{32}$.</li>
<li>When registering the events, simply multiply the numbers corresponding to the events sequentially modulo p. Call this result r.</li>
<li>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. </li>
</ol>

<p><strong>UPDATE</strong></p>

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

<ol>
<li>Assign each event a sequential number starting at 1.</li>
<li>Calculate $c = \sum_{j=1}^m j~ \mbox{mod}~2^{32} = \frac{j(j+1)}{2} \mbox{mod}~2^{32}$.</li>
<li>When registering the events, simply add the numbers corresponding to the events sequentially modulo $2^{32}$. Call this result r.</li>
<li>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. </li>
</ol>

CC BY-SA 2.5
2010-09-16T21:42:04.147Z
In this case, sums would be simpler than products. No need for modulo $p$, either...
Jukka Suomela
CC BY-SA 2.5
2010-09-16T21:48:57.493Z
Yes, sums modulo $2^{32}$ actually seems the best solution. The modulo arithmetic lets you go above $2^{16}$ events though, so it seems useful to keep.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-16T21:55:07.167Z
Anyway, I think we have here an interesting question: if you just assign labels $a_1, a_2, ..., a_n$ to $n$ events and calculate the sum modulo $2^{32}$, how many missing events can you identify? Obviously, if $n = 32$ we can detect any subset of events (by using labels that are powers of 2), but what about the original question with $n = 50$?
Jukka Suomela
CC BY-SA 2.5
2010-09-16T22:02:29.043Z
Well, a bound is simple enough. It is just the largest number y such that $\sum_{i=1}^y \frac{50!}{i!(50-i)!} \leq 2^{32}$.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-16T22:11:01.563Z
Sure, but is the bound achievable? How do you construct the labels?
Jukka Suomela
CC BY-SA 2.5
2010-09-16T22:51:18.500Z
I believe my first approach does ok. A quick calculation gives y=9. Now, since $51 \times 50 \times 49 \times 48 \times 47 < 2^{32}$ (take p ~ $2^{32}$), this means that simply factorising x should give the correct labels for up to 5 errors. I guess you can do better by looking at factorisations of x+k*p for $k \leq 2.6 \times 10^3$ and discarding any which involve primes < 51. For more than 5 missing events, however, I am not sure this will yield a unique result.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-17T00:08:43.893Z
@Joe: 4 times 5 and 2 times 10 have the same factorisation... If you use the first 50 primes and multiply modulo $p = 2^{31}-1$, it seems that you'll get a unique product for up to 4 missing events but not more.
Jukka Suomela
CC BY-SA 2.5
2010-09-17T00:23:47.433Z
Yes, that is of course true. I should have thought through my reply better. Primes would seem to work though (for about 4 or 5 events).
Joe Fitzsimons
CC BY-SA 2.5
2010-09-16T21:34:26.793Z
2010-09-16T21:56:39.020Z
2010-09-16T21:56:39.020Z
Joe Fitzsimons
<p>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).</p>

<p>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).</p>

<p>Can anyone think of a better way to do this?</p>

CC BY-SA 2.5
2010-09-16T21:13:58.737Z
Clearly you can't use a 32-bit value to encode which subset of 50 events is absent, if you can have any number of absences between 0 and 50. I think you should clarify your question to explain exactly what kind of situations you need to handle.
Jukka Suomela
CC BY-SA 2.5
2010-09-19T00:24:26.803Z
Thanks for all the great answers. The original problem (sort of unrelated but caused me to think of a different problem) was that I had a sequence of debug statements being printed in a loop, that I needed in place to diagnose an issue, but memory/space restrictions mandated that I couldn't just print to the logs and wait for the bug to occur.. so I started looking into ways I could combine 50 events (completely random choice of number) into an int that I could print every 50 iterations and which would tell me the specific loop and the condition that had failed.
Sridhar Iyer
CC BY-SA 2.5
2010-09-19T17:52:23.130Z
Well, in that case I think you should just combine 32 events into an int, one bit per event...
Jukka Suomela
<ds.algorithms>
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.
Sridhar Iyer
# 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.

(Asked by: username_0 on 2010-09-16)

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?

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: Clearly you can't use a 32-bit value to encode which subset of 50 events is absent, if you can have any number of absences between 0 and 50. I think you should clarify your question to explain exactly what kind of situations you need to handle.  
> **username_0**: Thanks for all the great answers. The original problem (sort of unrelated but caused me to think of a different problem) was that I had a sequence of debug statements being printed in a loop, that I needed in place to diagnose an issue, but memory/space restrictions mandated that I couldn't just print to the logs and wait for the bug to occur.. so I started looking into ways I could combine 50 events (completely random choice of number) into an int that I could print every 50 iterations and which would tell me the specific loop and the condition that had failed.  
> **username_1**: Well, in that case I think you should just combine 32 events into an int, one bit per event...  

---

## 4 answers

### Answer by username_4 on 2010-09-16. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_1**: In this case, sums would be simpler than products. No need for modulo $p$, either...  
> **username_4**: Yes, sums modulo $2^{32}$ actually seems the best solution. The modulo arithmetic lets you go above $2^{16}$ events though, so it seems useful to keep.  
> **username_1**: Anyway, I think we have here an interesting question: if you just assign labels $a_1, a_2, ..., a_n$ to $n$ events and calculate the sum modulo $2^{32}$, how many missing events can you identify? Obviously, if $n = 32$ we can detect any subset of events (by using labels that are powers of 2), but what about the original question with $n = 50$?  
> **username_4**: Well, a bound is simple enough. It is just the largest number y such that $\sum_{i=1}^y \frac{50!}{i!(50-i)!} \leq 2^{32}$.  
> **username_1**: Sure, but is the bound achievable? How do you construct the labels?  
> **username_4**: I believe my first approach does ok. A quick calculation gives y=9. Now, since $51 \times 50 \times 49 \times 48 \times 47 < 2^{32}$ (take p ~ $2^{32}$), this means that simply factorising x should give the correct labels for up to 5 errors. I guess you can do better by looking at factorisations of x+k*p for $k \leq 2.6 \times 10^3$ and discarding any which involve primes < 51. For more than 5 missing events, however, I am not sure this will yield a unique result.  
> **username_1**: @Joe: 4 times 5 and 2 times 10 have the same factorisation... If you use the first 50 primes and multiply modulo $p = 2^{31}-1$, it seems that you'll get a unique product for up to 4 missing events but not more.  
> **username_4**: Yes, that is of course true. I should have thought through my reply better. Primes would seem to work though (for about 4 or 5 events).  

---

### Answer by username_2 on 2010-09-17. Score: 5

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 by username_1 on 2010-09-17. Score: 5

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:

Detect if there are any missing events.
Count the exact number of missing events.
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 by username_3 on 2010-09-17. Score: 1

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.


---

