Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
6  
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
2  
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

7 Answers 7

up vote 10 down vote accepted

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer
5  
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).$$

share|improve this answer

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.