# Is there a way to map an infinite grid onto the natural numbers efficiently? [duplicate]

I have a grid of cells that extends infinitely in all four directions. I need a way to map the coordinates of each cell to a unique positive integer efficiently. Can this be done non-sequentially? In other words, what is a function that is a bijection between $(\mathbb{Z},\mathbb{Z})$ and $(\mathbb{N})$?

• I'm confused. Do you want to create an "array" with single integer indices which can access any ordered pair of integers, i.e. the $5$th entry might be $(2, 2)$? – Chris Jul 9 '17 at 22:23
• Take $(n,m)\to2^n3^m$. Not very performant in all aspects, but this was not part of your question. Computing the "index" is fast. – M. Winter Jul 9 '17 at 22:29
• @Chris Sorry, I probably could have worded this better. Feel free to edit it if you have better wording ideas. In effect, you're right, only this "array" needs to have some way to convert between the values. I.E I can't calculate them all and store them in a lookup table. Also, the coordinates can be negative ( e.g. $(-4, 7)$) but the resulting integer cannot. – Daffy Jul 9 '17 at 22:29
• You may map $(x,y)$ to $2^{x_+} 3^{y_+} 5^{x_-} 7^{y_-}$ where $x_+ = \max(0,x)$, $x_- = \min(0,x)$ and similarly for $y$. – Joel Cohen Jul 9 '17 at 22:29
• @JoelCohen The question doesn't state explicitly, but I imagine the asker wants a bijective correspondence (the use of the word "index" hints at that, for example) – Carl Schildkraut Jul 9 '17 at 22:34

I don't think this question is a duplicate of this other question - the aim is different - but the bijection there can be modified to fit this question.

First, define a mapping from $\mathbb{Z}$ to $\mathbb{N}$ as follows:

$$0 \mapsto 1$$

$$n \mapsto 2n\ \ (n>0)$$

$$-n \mapsto 2n+1\ \ (n>0)$$

So, the ordering is $0,1,-1,2,-2,\cdots$. Then, we use the mapping described in this question - given your (now positive) integer pair $(i,j)$, map it to $2^{i-1} (2j-1)$. Since each positive integer can be factored into a power of $2$ and an odd number uniquely, this is a bijective mapping.

For example, your pair $17,85$ would first map to the positive integer pair $34,170$. Then, we would map it to

$$2^{34}\cdot(2\cdot 170-1) = 5823975653376.$$

This might not be optimal if you want to actually calculate lots of correlations, but the underlying calculations are simple in nature.

• That technically works, but I need it to be more efficient. Assuming (0,0) is 0 and the numbering is done Ulam Spiral style, $(34,170)$ should be somewhere under 23120. – Daffy Jul 9 '17 at 22:34
• @Daffy if you want a way to compute the nth point on the number spiral in your link, maybe you should ask for that specifically? "efficient" can mean different things in different contexts. – stewbasic Jul 9 '17 at 22:40
• @Daffy A closed form for the Ulam Spiral can be found here. To change it from something taking $\mathbb{N}^2$ to something taking $\mathbb{Z}^2$, simply use the same mapping from $\mathbb{Z}$ to $\mathbb{N}$ described here. – Carl Schildkraut Jul 9 '17 at 22:43
• @CarlSchildkraut That doesn't work for negative coordinates. – Daffy Jul 9 '17 at 22:46
• @stewbasic You're right. Should I open that as a new question? – Daffy Jul 9 '17 at 22:46