Function that sends $1,2,3,4$ to $0,1,1,0$ respectively

Question

I already got tired trying to think of a function $f:\{1,2,3,4\}\rightarrow \{0,1,1,0\}$ in other words:

$$f(1)=0\\f(2)=1\\f(3)=1\\f(4)=0$$

Don't suggest division in integers; it will not pass for me. Are there ways to implement it with modulo, absolute value, and so on, without conditions?

Answer 1

Another one (a bit more complicated than the parabola) is: $$f(x)=\frac{2}{\sqrt{3}}\sin\bigg(\frac{\pi}{3}(x-1)\bigg)$$

This one generates: $0,1,1,0,-1,-1,0,...$

---

And another simple one:

$$f(x)=1.5-\left | 2.5-x\right|$$

Answer 2

Seeing the zeroes of the function and its symmetry, one tries to fit a quadratic curve to get $f(x)=-0.5(x-1)(x-4)$.

Answer 3

Heaviside functions (using the appropriate convention) should work too. Use

$f(x) = U(x-1) - U(x-2)$

where $U$ is the Heaviside step function.

Answer 4

If you have bit operations, just return the two's bit of the input. So $y=x \gt \gt 1 ;\ \ f(x)=y\%2$

Answer 5

From a mathematical point of view, describing such a function is trivial: $$ f(x)=\begin{cases} 0 & \text{if } x \in \{1,4\} \\ 1 & \text{if } x \in \{2,3\} \\ \end{cases}.$$ It's not a particularly slick formula for the function, but it's certainly straightforward. An alternative is to search for "magic numbers". For example: $$f(x)=2x^2+3 \mod 5.$$ To find this function, I just let my computer search until the numbers happened to match.

If you're looking for an efficient implementation of this function, in C say, any one of these would compute the function:

char f=(x&2)>>1;
char f=(x>>1)%2;  // this is Ross Millikan's suggestion
char f=(x>>1)&1;

Here & is bitwise and, >> is right bit-shift by one, and % is the mod operation.

If you only need an if(f!=0) { ... } statement (i.e., "if $f(x)\neq 0$"), then this would suffice:

if(x&2) { ... }

An alternative to the above is simply storing the values in memory. E.g. via:

char f[5]={0,0,1,1,0};

whenceforth, if you want to compute $f(x)$, you can just recall f[x] from memory.

Answer 6

Here's a simple one using only mods and a square

$f(x)=(x-1)^2 \mod 3$

Answer 7

Something more complex maybe? $$f(x)=\max(0, \text{Im}\, i^{x-1}-\text{Re}\, i^{x-1})$$

Or something simpler:

$$f(x) = 1 - \max(0, 2-x, x-3)$$

Similarly (in the vein of the $|x-2.5|$ answers):

$$f(x) = 3-\max(2, |2x-5|)$$

Answer 8

Given any set of $n$ points and values, you can always construct a polynomial of degree less than or equal to $n-1$ that goes through all the points. See http://en.wikipedia.org/wiki/Polynomial_interpolation.

Using the method from there, we get

$$\left[\begin{smallmatrix}1 & 1 & 1 & 1\\8 & 4 & 2 & 1\\27 & 9 & 3 & 1\\64 & 16 & 4 & 1\end{smallmatrix}\right] \left[\begin{smallmatrix}a_{3}\\a_{2}\\a_{1}\\a_{0}\end{smallmatrix}\right] = \left[\begin{smallmatrix}0\\1\\1\\0\end{smallmatrix}\right]$$

Multiplying by the inverse matrix on the left on both sides gives

$$\left[\begin{smallmatrix}a_{3}\\a_{2}\\a_{1}\\a_{0}\end{smallmatrix}\right] = \left[\begin{smallmatrix}0\\- \frac{1}{2}\\\frac{5}{2}\\-2\end{smallmatrix}\right]$$

meaning that the resulting polynomial is $- \frac{1}{2} x^{2} + \frac{5}{2} x -2$ (indeed, if you factor this, you get the same thing as Jasper Loy). You can easily check that this polynomial works. Note that in this case, the polynomial had degree one less than we were expecting.

Answer 9

Look the example for Lagrange Interpolation, then it is easy to construct any function from any sequence to any sequence.

In this case :

$$L(x)=\frac{1}{2}(x-1)(x-3)(x-4) + \frac{-1}{2}(x-1)(x-2)(x-4)$$ wich simplifies to: $$L(x)=\frac{-1}{2}(x-1)(x-4)$$ which could possibly explain Jasper's answer, but since the method for derivation was not mentioned can not say for sure.

Answer 10

Since you tagged "binary" in your question, you might also want to recall that Karnaugh map is a standard way to map inputs to outputs with just complement, AND and OR gates. (Or "~", "$\&$" and "|" bit-wise operators in C)

For example, you can define $a,b,c$ to be bits at position 2,1,0 here to use the map.
If you draw out the map, this is what it looks like:

$$\begin{array}{c|c|c|c|c|c|} & &bc &bc &bc &bc\\ \hline & & 00 & 01 & 11 & 10\\ \hline a& 0 & \text{X} & 0 & 1 & 1 \\ \hline a& 1 & 0 & \text{X} & \text{X} & \text{X} \\ \hline \end{array}$$ Explanation: X denotes values that cannot occur (normally called "Don't care" I think). We want to focus on representing the "1"s, which is represented by the entries $\bar abc$ and $\bar a b\bar c$. (Notice that you only get "1" for one of the variables, they cannot occur together.)
They can be combined: $\bar a bc + \bar a b \bar c=\bar a b (c+\bar c)=\bar a b$.
Getting rid of the $\bar a$ is possible when you noticed that its alternative row has no entries. (i.e. the 2 entries below are "X"s)

Using this idea you can construct any function for any bigger variable.
It is probably not going to be the most efficient implementation, but you can get the solution fast. From there, you may do some reduction using logical operations and the final result should be decent.