How to encode a set of whole numbers $\{a_1,a_2,...,a_n\}$ such that given a number $x$ we can test if $x \in \{a_1,a_2,...,a_n\}$

Question

Suppose we have a set of whole numbers $\{a_1,a_2,...,a_n\}$. Is there a way to encode them into a new number $e$ such that we can use $e$ to test if a given number $x \in \{a_1,a_2,...,a_n\}$? So really I'm looking for two things:

1. Encoding function $$f(a_1,a_2,...,a_n)=e$$

2. Test function $$p_e(x)=true \iff x \in \{a_1,a_2,...,a_n\}$$

I'm using this in a computer program so the numbers can't get too big, and it would also be very beneficial to be something that can be implemented to run quickly. Thank you all, cheers.

Answer 1

Theoretically, given all $\{a_1,a_2,...,a_n\}$ are different since you stated it's a set, such a function is possible. $$f(a_1,a_2,...,a_n)=\sum\limits_{k=1}^n 2^{a_k}=E$$ In other words, the binary form of $E=(1001...0010...)_2$ has the property that

• at the position $a_k$ we have the digit $1$, for every $k=1..n$ and
• in all the other positions we have the digit $0$.

Now $$x \in \{a_1,a_2,...,a_n\} \Leftrightarrow 2^{x} \text{ & } E =2^x$$ where $\text{&}$ is the bitwise AND.