# I need to find an equation to assign a whole, nonnegative ID to every coordinate in an infinite grid.

I have a math problem I've been trying to solve for a few months. The problem is that I need a function that will take the input of a coordinate pair (from all quadrants [+x +y , +x -y , -x -y , -x +y]) and output a whole nonnegative number with no repeats. I basically need a function that will give me an ID for EVERY coordinate on an INFINITE grid.

The way I started to attack this problem is to form a pattern in which the coordinates would be numbered. I made it so (0,0) is 1, (0,1) is 2, and (-1, 1) is 3 in a spiral pattern around the origin.

After I labeled a coordinate grid with all the 'IDs' or output numbers I started to try to find patterns in the numbers and try to come up with the functions that would give me the correct ID for each of the coordinate pairs. I have found two functions that will each correctly give me a quarter of the infinite coordinate grids IDs .

They are:

If x ≥ |y| ID= [(2x+1)^2] -(x-y)

And

If -x ≥ |y| ID= [(2x)^2] +(x-y)+1

I've been working on this for months and I really need some help. If anyone is willing to take a look and see if you can find anything I will be so greatful.

You want a bijection $$f:\Bbb Z\times\Bbb Z\to\Bbb N$$. Consider the following two bijections $$g:\Bbb Z\to\Bbb N$$ $$n\mapsto\begin{cases}2n,&\text{if n is positive}\\ 1-2n,&\text{otherwise}\end{cases}$$ $$h:\Bbb N\times \Bbb N\to \Bbb N$$ $$(u,v)\mapsto2^{u-1}(2v-1)$$

Check that $$g$$ and $$h$$ are bijections. Now, desired function $$f$$ is $$h\circ (g\times g)$$.

Here is a Matlab implementation of the formula(s) one finds in this OEIS sequence mentionned in math.stackexchange.com/q/2388808 [I have understood now that your question isn't there] giving a spiral of numbers :

% Program A
a(1)=0;b(1)=0;
text(a(1),b(1),num2str(1))
for n=2:99
t=mod(floor(sqrt(4*(n-2)+1)),4)*pi/2;
a(n) = a(n-1) + sin(t);
b(n) = b(n-1) + cos(t);
text(a(n),b(n),num2str(n))
end;


(this could be converted into complex numbers notations, but I think it wouldn't bring necessarily a big plus).

The "direct access" you desire is given by the following formulas, very close to yours, each one specific to a quadrat :

   % Program B
clear all;close all;
axis(6*[-1,1,-1,1]);axis equal;
N=4;% for a (2N+1) x (2N+1) grid
for x=0:N
for y=0:N
if x<=y
r=4*y^2+3*y+1+x;
else
r=4*x^2-3*x+1-y;
end;
text(x,y,num2str(r));
end;
end;
for x=-N:0
for y=0:N
if abs(x)<=abs(y)
r=4*y^2+3*y+1+x;
else
r=4*x^2-x+1+y;
end;
text(x,y,num2str(r));
end;
end;
for x=-N:0
for y=-N:0
if abs(x)<abs(y)
r=4*y^2+y+1-x;
else
r=4*x^2-x+1+y;
end;
text(x,y,num2str(r));
end;
end;
for x=0:N
for y=-N:0
if abs(x)<abs(y)
r=4*y^2+y+1-x;
else
r=4*x^2-3*x+1-y;
end;
text(x,y,num2str(r));
end;
end;


Remark : I could have described the operations more formaly, instead of having displayed them into a program, but for the sake of understanding, the result is the same). I am also fairly certain that this program can be shortened ; here again, a more compact form could result in a less understandable message.

Fig. 1. This spiral can be the result as well of Program A or Program B.

I end this answer by something that is rather independent, but has its own aesthetics. If lines 6 and 7 of Program A are replaced by

a(n) = a(n-1) + cos(t) - sin(t);
b(n) = b(n-1) + cos(t) + sin(t);


one gets the $$45°$$ oriented spiral represented in fig. 2. (do you have an idea of the "trick of the trade" behind this slight modification ?)

Fig. 2.

• I have given a second spiral which is maybe the one you were looking for... – Jean Marie Mar 26 at 5:10
• I'm sorry for not explaining things very well, I'm in 9th grade. I'm not looking for a function to make the spiral, I'm looking for a function that will take x and y and out put the corresponding number on the spiral. (0,0) is 1. if I input 0 0 into the function [(2x+1)^2] -(x-y) the output will be 1, which is what I want. – Anderz Muecke Mar 26 at 13:18
• I understand. As a consequence, I have completely revamped my answer. Is it satisfactory now ? – Jean Marie Mar 26 at 16:31
• The fact that it is second degree polynomials that bring a response doesn't come by surprise (when you think to Ulam's spiral and phenomena like the sequence of primes having the form $n^2+n+41$ – Jean Marie Mar 26 at 18:32
• You haven't answered me though my program B gives (now) the formulas for each quadrant. If I input (x,y) after checking in which quadrant it is, I can compute the value to be placed there... – Jean Marie Mar 28 at 21:41