Explicit Bijection from N to NxN

[phoenixthoth]

for this post, let N = {1, 2, 3, ...}.

Q: explicitly write down a closed form bijection with domain N and range N x N. (no need to prove its a bijection... just write down the formula.)


this may lead you off track, but the way i did it was to first find a formula from N x N to N and then invert it.
let (m, n) be an element of N x N and q = 1/2.
then the map is given by (m,n) |-> x, where
x = q m^2 +q n^2 + m n - q m - 3 q n + 1.
maybe I'm admitting how much i lack in algebra skillz by saying this, but i found it hard to invert this function... i did cheat and used mathematica to do the algebra i asked of it, but it didn't actually find the inverse by itself. i only used it to simplify expressions and isolate variables. i also used this site as a reference: http://www.research.att.com/~njas/sequences/ . thus i will say to you that no holds are barred; do it by any means necessary!

for double sums, we have something like this:
S = Sum[ f(m,n) , (m,n) ε NxN ].
if g is a bijection from N to NxN, we can straighten out this sum (assuming convergence of the original, we can add any way we please):
S = Sum[ f(g(x)), x ε N ], turning the double sum into a single sum. the catch is the formula for g ain't pretty so I'm not sure how useful this is... at least one can use single integral formulas to now estimate double sums and predict error although perhaps multivariable error estimates for double sums already exist (they probably do)...

i guess the next step is to find a bijection from N to NxNxN... i get an icky feeling all over when i think about that.

 

[phoenixthoth]

let g(x) = (m(x), n(x)) be the desired map from N to NxN.

let be the round function (rather than the usual greatest integer function).

then
m(x) = (2x + [SQRT(2x)] - [SQRT(2x)]^2)/2
n(x) = (2 - 2x + [SQRT(2x)] + [SQRT(2x)]^2)/2

for example, the 666th point in NxN is (36,1) and the millionth point is (1009, 406).