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

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?

• Sorry, what is it all about? For instance, what is $a$ and $b$, isn't it a one variable function you would like to see? – Berci Oct 17 '12 at 7:41
• You can use the Iverson bracket and simply write it as $f(a)=[a=2]+[a=3]$. :-) – Brian M. Scott Oct 17 '12 at 7:55
• f == isPrime ;) – wim Oct 17 '12 at 11:14
• Have you considered the function $f : \{1,2,3,4\} \to \{0,1\}$ such that $f(1)=0$, $f(2)=1$, $f(3)=1$, and $f(4)=0$? :) – Snowball Oct 17 '12 at 21:51
• @starovoitovs: You really should clearly state the intended purpose. Honestly, for most mathematical purposes, definition you've given in your question is probably what you really should be wanting to use. If your purpose is for fast implementation on a computer, then you really should say that, to let people who know about such things make good suggestions (and you should probably include how it's going to be used, as well). If your purpose is something else, then if you state it, people can give you answers to suit your needs rather than just having fun. – Hurkyl Oct 18 '12 at 0:03

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|$$

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)$.

• It has division by integers. – Asaf Karagila Oct 17 '12 at 15:13
• Write $1/2$ as $0.5$ ... – lhf Oct 17 '12 at 23:56
• I think the OP meant integer division, like 1/2 = 0. – asmeurer Oct 21 '12 at 1:36
• How does one arrive at this result? – Arjang Oct 21 '12 at 6:25
• Very ingenious, and quick! – Namaste Nov 29 '12 at 0:14

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

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

• To all: I had not seen Doug Stone's similar $f(x)=2x^2+3 \mod 5$ – coffeemath Oct 21 '12 at 6:20
• @coffeemath I recently realized that all the modulo solutions can be obtained from the initial Lagrange Interpolation $-\frac{1}{2}(x-1)(x-4)$. Under modulo 5 you get $2x^3+3$ and under modulo 3 you get $x^2+x+1$, which is what you have here. – Yong Hao Ng Oct 31 '12 at 10:41
• Interesting. So under mod 7 it would be $(-1/2)(x-1)(x-4)$ which since $-1/2=6/2=3$ would give $3(x^2-5x+4)$ or $3x^2-x-2$. And that works. I guess as long as 2 is invertible mod n we have the example. I wonder about when $n$ is even... – coffeemath Nov 28 '12 at 13:08

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

• Or similarly, $(x>>1)\&1$. Is the $\&$ operation cheaper than $\%$? – Yong Hao Ng Oct 21 '12 at 5:46
• @YongHaoNg It can be. It depends on the underlying hardware and, especially, how efficient the compiler is. – Rick Decker Dec 7 '12 at 1:16
• I see, thanks for the info. – Yong Hao Ng Dec 8 '12 at 9:35

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.

• +1 for Karnaugh map, now an example of it to fit this instance. – Arjang Oct 21 '12 at 6:09
• Okay let me try to figure out how to draw a table. :) – Yong Hao Ng Oct 21 '12 at 6:12

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.

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={0,0,1,1,0};


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

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|)$$

• Or $f(x)=4-max(x,5-x)$ in the same vein as your "simpler". But I liked the powers of $i$ version, since they cycle around the circle, and since one needs two in a row, using the line $y=x$ etc... – coffeemath Oct 21 '12 at 4:08

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.

• If someone knows how to make the elements of those vectors line up, please edit and fix. I just used SymPy's $\LaTeX$ generation to get that. – asmeurer Oct 21 '12 at 1:49
• Perhaps for equally spaced inputs and symmetric outputs one would expect degree 2. – coffeemath Oct 21 '12 at 3:34

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.

• ...which is Jasper's answer. – lhf Oct 21 '12 at 1:53
• @lhf: on the specified domain, all of these functions are the same. This is a nice derivation of the answer Jasper Loy gave. – robjohn Oct 21 '12 at 8:02
• @robjohn You mean that $L(x)=2x^3+3$ under modulo 5 and $L(x)=x^2+x+1=(x-1)^2$ under modulo 3 right? I found out about this while answering a similar question elsewhere. Are the polynomials unique in the chosen domain? – Yong Hao Ng Oct 31 '12 at 10:47
• @YongHaoNg: I mean that on the given domain, $\{1,2,3,4\}$, all of the various representations give the same function:\begin{align}1\to0\\2\to1\\3\to1\\4\to0\end{align} – robjohn Oct 31 '12 at 13:28