Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Counting > Countable > Counting Ordered Pairs of Integers

The set of ordered pairs of integers is countably infinite.  That means the ordered pairs of integers can be put in one-to-one correspondence with the counting numbers, which are the positive integers.  This helps us show that the set of rational numbers is countable.

Counting Ordered Pairs of Integers

How does this one-to-one correspondence work?  First, let's consider the "square spiral" of ordered pairs.  The origin is the 0th element of this sequence, and all the other ordered pairs are somewhere on the spiral.  Andrew Critch asked the key question on the Algebra-Online message board:

>
>
On 11/14/00 8:29:23 PM, Andrew Critch wrote:
Can ANYBODY help me find a function to find the nth element of this series?
{(1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1), (2,-1), (2,0), ...}

It's a square spiral circling out from the origin. Any help would be greatly appreciated.

OK, Here you go, Andrew.

I will give you a formula for finding xn and yn for any positive integer n, so that the point (xn,yn) is the nth element of the sequence you're describing.  There's also a calculator you can use to quickly find the nth ordered pair.

I will use intermediate variables in the calculation to make the explanation clear.

The variables I will use are:

Shell -- the number of the square, in other words its distance from the origin.

Leg -- a number 0, 1, 2, or 3 indicating which leg of the square the nth point belongs to.

Element -- a number from -Shell+1 to Shell giving the position of the nth point on the given leg of the given shell.

Now for the calculation...

Shell = integer((sqrt(n)+1)/2)

Leg = integer((n-(2*Shell-1)^2)/(2*Shell))

Element = (n-(2*Shell-1)^2)-2*Shell*Leg-Shell+1

xn = Leg==0? Shell: Leg==1? -Element: Leg==2? -Shell: Element

yn = Leg==0? Element : Leg==1? Shell : Leg==2? -Element : - Shell


If you have access to Microsoft Excel, then you can make a spreadsheet that calculates these values, and use an x-y scatter plot to depict the graph. I'll get you started, and you can always ask if you need more info...

In the first row, put your column labels: n, Shell, Leg, Element, x, y.

In the second row, put your formulas.

The cell in column A has no formula; just fill it with counting numbers.

The cell in column B, Shell, is =FLOOR((SQRT(A2)+1)/2,1)

The cell in column C, Leg, is =FLOOR((A2-(2*B2-1)^2)/2/B2,1)

The cell in column D, Element, is =(A2-(2*B2-1)^2)-2*B2*C2-B2+1

The cell in column E, x, is =IF(C2=0,B2,IF(C2=1,-D2,IF(C2=2,-B2,D2)))

The cell in column F, y, is =IF(C2=0,D2,IF(C2=1,B2,IF(C2=2,-D2,-B2)))

You can cut and paste these formulas from this message right into Excel, plot the x and y columns using a scatter plot, and within a minute or two, you'll be lookin' at the square spiral! Have fun.

Inverse Spiral Function

Then, much later, someone named Ofek emailed me to ask about the inverse.  That is, how can you get from an (x,y) pair to the distance from the origin, measured along the spiral?

Here's the answer:

Given (x,y),

shell is the maximum of the distance in either dimension from the origin, in other words: max(abs(x),abs(y))

leg -- if you think of the plane of ordered numbers as being inside a big "X", then the leg is the quadrant in that x.  In other words,

if (x,y) is closest to the positive x axis, then leg is 0
if (x,y) is closest to the positive y axis, then leg is 1
if (x,y) is closest to the negative x axis, then leg is 2
if (x,y) is closest to the negative y axis, then leg is 3

and a "tie" goes to the lower leg number (a tie between legs 3 and 0 goes to leg 3)

element is the directed distance from the axis, measured along the spiral.

Here are the calculations, which you can enter into your spreadsheet, assuming "x" is in column E, and "y" is in column F:

The cell in column G, Shell, is =MAX(ABS(E2),ABS(F2))

The cell in column H, Leg, is =IF(AND(F2<=E2,F2>-E2),0,IF(AND(F2>=-E2,F2>E2),1,IF(AND(F2>=E2,F2<-E2),2,3)))

The cell in column I, Element, is =IF(H2=0,F2,IF(H2=1,-E2,IF(H2=2,-F2,E2)))

The cell in column J, n, is =4*G2^2+(2*H2-3)*G2+I2

Now, no matter what integer values of (x,y) you type into the cells in columns E and F, you'll get the correct distance from the origin, measured along the spiral, in column J.

Andrew wrote back to say he didn't understand my terminology, so I provided an example, and a calculator that gives the x, y coordinates of the nth ordered pair.

Related pages in this website

The Peano Postulates -- Proving the properties of natural numbers using the Peano Postulates, which have been formulated so that zero is not included in the set of natural numbers.  (There's quite a debate about this point.)

Is Zero a Natural Number? -- a discussion of the fact that some authors include zero, and others do not.

Introduction to Counting -- explains what mathematicians mean by "counting" -- that is, putting sets in one-to-one correspondence.

Construction -- Construction of sets of numbers, starting with the original Peano Axioms, formulated so that zero is included in the set of natural numbers.

Set Theory -- an introduction to sets, including examples of some standard sets.

 


The webmaster and author of this Math Help site is Graeme McRae.