# Function satisfying $x = f(f(x))$ and $x \not= f(x)$

Is there a function that would satisfy the following conditions?:

$\forall x \in X, x = f(f(x))$ and $x \not= f(x)$,

where the set $X$ is the set of all triplets $(x_1,x_2,x_3)$ with $x_i \in \{0,1,\ldots,255\}$.

I would like to find a function that will have as an input RGB color values (triplets) and return the original color after two applications of the function.

-
How about $f(x_1, x_2, x_3) = (255 - x_1, 255 - x_2, 255 - x_3)$? – ofer Dec 4 '11 at 6:53
@ofer: You should post your comment as an answer so that I can mark it as the accepted answer. I agree with PZZ's comment in his answer in terms of simplicity and speed of your answer. Also, since PZZ's solution modifies the colors by only $\pm 1$ unit, the color change would be much less noticeable then $255-x$ in most cases. I prefer the larger color change. – Kavka Dec 4 '11 at 7:17
Ok. I'll add it as an answer. – ofer Dec 4 '11 at 7:56
There is such a concept as "complementary colors". If cyan is the complement of red, then red is the complement of cyan. So applying the complement function twice will take you back to where you started. And I think complementation may be exactly what ofer's example does. – Michael Hardy Dec 4 '11 at 17:31

$f(x_1,x_2,x_3)=(255−x_1,255−x_2,255−x_3)$ should do the work.

-

If you prefer the large color change, you should rather take $$f(x,y,z)= (x+128 \bmod 256,y+128 \bmod 256,z+128 \bmod 256).$$

-

I think $f(x,y,z) = (x + 1, y, z)$ if $x$ is even and $f(x,y,z) = (x-1, y, z)$ when $x$ is odd does the trick. Suppose $x$ is even. Then $x+1$ is odd so $$f(f(x,y,z)) = f(x+1,y,z) = (x,yz)$$ and similarly when $x$ is odd. That the function has no fixed points is obvious because $x \neq x+1$ and $x \neq x-1$ for all integers $x$. Moreover, if $x \geq 0$ is odd then $x\geq 1$ and if $x \leq 255$ is even then $x \leq 254$ so $f$ maps your set into itself.

EDIT: ofer's comment gives a function that is faster to compute and less complicated. So you should probably use that.

-
Oh, you beat me by 16 sec. – Paul Dec 4 '11 at 7:02

If you are doing these calculations on a computer and can get away from insisting on interpreting $x_1$, $x_2$, $x_3$ as integers in the range $[0,255]$, consider thinking of $x_1$, $x_2$, $x_3$ as eight-bit bytes or vectors of length $8$ over $\mathbb F_2$ to be a bit more formal about it. Then, for any three bytes $a$, $b$, $c$ with at least one being nonzero, $$f(x_1, x_2, x_3) = (x_1\oplus a, x_2\oplus b, x_3\oplus c)$$ has the desired properties that \begin{align*} f(f(x_1, x_2, x_3)) &= f(x_1\oplus a, x_2\oplus b, x_3\oplus c)\\ &= (x_1\oplus a\oplus a, x_2\oplus b\oplus b, x_3\oplus c \oplus c)\\ &= (x_1, x_2, x_3), \end{align*} and $(x_1, x_2, x_3) \neq f(x_1, x_2, x_3)$. As an added bonus (not necessarily important to math.SE readers), the XOR operation on bytes is a machine-language instruction on most computers and in some cases can be faster than the ADD instruction which is often defined for full (multiple-byte) words only.

Note that $f(x_1,x_2,x_3)=(255−x_1,255−x_2,255−x_3)$ as suggested by @ofer is just $f(x_1,x_2,x_3) = (x_1 \oplus \mathbf 1, x_2\oplus \mathbf 1, x_3\oplus \mathbf 1)$ where $\mathbf 1 = (1,1,1,1,1,1,1,1)$ is the eight-bit all-ones byte.

-

$$f(x) = 5-x$$

$$f(x) = \frac{16}{x}$$

There are tons, scads, bushels, truckloads, imponderable multitudes, of functions like this. You could fill a fathomless abyss up to here with them.

They're called "involutions".

(Except, technically, the ones that satisfy $f(x)=x$ are also involutions.)

-
While I agree with your general point, you should probably give examples which satisfy the OPs condition. They want $f:X \to X$. – user12014 Dec 4 '11 at 8:06

What about this: Define $$g(x)=x-1\mbox{ if }x\mbox{ is odd; and }x+1\mbox{ if } x \mbox{ is even.}$$ Then $g$ maps from $\{0,1,\ldots,255\}$ to $\{0,1,\ldots,255\}$. Note also that $g(x)\neq x$ for all $x\in\{0,1,\ldots,255\}$, and $g(g(x))=x$. Now we can define $f$ as the following: $$f(x_1,x_2,x_3)=(g(x_1),x_2,x_3).$$

-

If $f(x)=1-x$, then $f(f(x))=1-(1-x)=x$ (applied to each component).

-
This doesn't map $\mathbb{N}^3$ into $\mathbb{N}^3$. But maybe this is not a problem for the OP. – user12014 Dec 4 '11 at 6:44
Elements of $x$ and $f(x)$ have to be a positive integers though. – Kavka Dec 4 '11 at 6:47
True, for some reason I didn't see that $0,\dots,255$ was specified. – dls Dec 4 '11 at 6:59
You can do it modulo 256 then. – ofer Dec 4 '11 at 7:22