bijective function over $\mathbb{N}$ that isn't $f(X) = (X)$ I'm struggling to come up with a good example for a bijective function over $\Bbb N$. I've come up with:
$f(n) =\begin{cases}   
       1,& n=0\\  
       0, &n=1  \\
       n, &\text{otherwise}\\ \end{cases} $
Firstly, can you confirm this is acceptable, and secondly, does anyone have any other examples? (Perhaps a more beautiful one!)
 A: Yes, that works. You can generalize that 'reversal' idea:
$$f(n) = \begin{cases} 
2m +1 & \text{if }n=2m \\
2m & \text{if }n=2m+1
\end{cases}$$
A: Yes, it is acceptable.
And for example, how about:
$$f\left(x\right)=\begin{cases}
x-1 & x\in\mathbb{N}_{odd}\\
x+1 & x\in\mathbb{N}_{even}
\end{cases}$$
A: A more intricate example is a generalization from my comment. Let $a > 0$ then the bitwise xor 
$$f(n) = n \;  \mathrm{xor} \;a$$ is bijective.
Obviously the function and its graph depend on the parameter $a$. Here the function values for $n=0,1,\dots 10$ for several $a$
a= 1     1  0  3  2  5  4  7  6  9  8 11
a= 7     7  6  5  4  3  2  1  0 15 14 13
a= 11   11 10  9  8 15 14 13 12  3  2  1

A: To give a more interesting example, consider the set of primes numbers $p_1,p_2,p_3,\ldots$. By the fundamental theorem of arithmetic any positive integer $N$ greater than $1$ has a unique factorization into prime powers.
$$N= \prod_{k=0}^\infty p_k^{a_k(N)}$$
Where $a_k(N) =0$ for all but finitely many $k$.
Thus we can construct a bijection on $\mathbb N$ as follows: let $f(0)=0$. From now on, think of $f$ as a list. We are going to add numbers to this list in a block-wise fashion:
With the $k$-block, add all numbers to the list that aren't already on the list that are products of the first $k$ prime numbers such that the sum of the powers $a_k$ is smaller or equal to $k$. (For example in reverse lexicographic order)
The list begins like this:


*

*$k=0:\quad 0$

*$k=1:\quad 2^1,2^0$

*$k=2:\quad 2^2,2^13^1,3^2,3^1$

*$k=3:\quad 2^3,2^23^1, 2^25^1, 2^1 3^1 5^1,2^15^2,3^3,3^25^1,3^15^2,3^15^1,5^3,5^2,5^1 $

*$\ldots$


Putting them together we get the list:  
$$0,2,1,4,6,9,3,8,12,20,30,50,27,45,75,15,125,25,5,\ldots $$
Which looks kinda random, but is indeed a bijection on $\mathbb N$!
A: Here's a bijection involving a spiral:
First, put the numbers on a spiral (sorry this doesn't look any better ... my graphical illustration skills are limited .. maybe someone can make this look a bit better?)

And now take an infinite knight's path like this:

Here's a start (I'm starting again at $0$ ... but I could of course take any point as the starting point of the knight's path):

OK, and so the sequence starts with:
$0, 17, 6, 23, 10, 13, 4, 19, 22, 9, 2, 15, 18, 21, 8, 11, 14, 5, 20, 7, 24, 1, 12, 3, 16, ...$
This is not a nice function to describe algebraically (I'm not even going to try!), but clearly a bijection.
And by the way, instead of a knight's path, you could of course have done just another spiral, but starting in a different point, or spiraling counter-clockwise, or rotating the spiral 90, 180, or 270 degrees.  I just think it's neat that you can use a knight to cover the whole infinite plane! :)
A: About intricate bijections and spirals, see sequence $$0,\quad2,1,\quad5,4,3,\quad9,8,7,6,\quad14,13,12,11,10,\quad\ldots$$This is A061579 in OEIS, and is quite spiralish (see ‘formula’ on that page if you want one).
There are many more bijections in OEIS, but AFAIK they’re not tagged, and so aren’t easy to find.
