Does anyone have the closed form for the Cantor-Snake function and its inverse?
By Cantor-Snake, I mean the bijection that maps the Naturals to the Rations - the classic proof that the rationals are denumerable.
I recall seeing the function as follows:
Consider the Natural Numbers, N = { 1,2,3,4... }
Consider the table of (N x N):
| 0 | 1 | 2 | ... |
| 1 | 2 | 3 | ... |
| 2 | 3 | 4 | ... |
And so on. We see that we could map 1 to (0,0), 2 to (0,1), 3 to (1,0), and so, "snaking" through the table. It's clearly surjective, and that's enough to have a bijection in this case (onto from Naturals to an infinite set proves the existence of a bijection).
I want the closed form for that snake function and its inverse. When working with that Rationals proof, we have to skip fractions that reduce - I don't want to skip those, I want to hit all of N cross N.
Thoughts?
The Cantor pairing function does what you need. $(x,y) \to z=\frac 12(x+y)(x+y+1)+y$ is a bijection. To invert it, let $w$ be the largest natural such that $\frac 12w(w+1) \le z,$ Let $t=\frac 12w(w+1), y=z-t, x=w-y$