Wednesday, December 12, 2012

An equation for enumerating integers

In my last post I described Cantor's way of proving that some infinite lists are bigger than others. I said that his is done by showing that a number of infinite lists, which are called countably infinite, can be paired up with every natural number from 0 onward. I shall now describe an equation that gives the integer that is paired up with a particular natural number.

The integers are (..., -2, -1, 0, 1, 2, ...)
We can pair up integers with natural numbers by pairing all the even natural numbers with positive integers and all the odd natural numbers with negative integers, like this:
0:0, 1:-1, 2:1, 3:-2, 4:2, ...

An equation which maps the natural numbers to the integers in this way is as follows:
y = -(x+1)/2*(x mod 2) + x/2*((x+1) mod 2)

"mod" is an operator called a modulo operator which gives the resulting remainder for a number divided by another. For example 4 mod 2 gives 0 and 5 mod 2 gives 1.

"x mod 2" will give 1 when x is odd and 0 when x is even.
"(x+1) mod 2" will give 1 when x is even and 0 when x is odd.

These are used in order to multiply them with terms that will deal with either the odd natural numbers or the even natural numbers.

"-(x+1)/2" will work when x is odd and will return -1 for 1, -2 for 3, -3 for 4, etc.
"x/2" will work when x is even and will return 1 for 2, 2 for 4, 3 for 6, etc.

These are used to pair up the negative integers with the odd natural numbers and the positive integers with the even natural numbers.

"-(x+1)/2*(x mod 2)" will give the negative integers for odd natural numbers and 0 for even natural numbers, as "-(x+1)/2" will be multiplied by 1 for odd naturals and by 0 for even naturals.
"x/2*((x+1) mod 2)" will give the positive integers for even natural numbers and 0 for odd natural numbers, as "x/2" will be multiplied by 1 for even naturals and by 0 for odd naturals.

By adding them together, since both terms will alternate between 0 and their signed integers, the sum will be an alternating sequence of positive and negative numbers for every natural number x. When x is 0, the result of the sum will also be 0 as both terms will be multiplied by 0.

The equation in Python 3 is as follows:
for x in range(20):
 print(x, ":", -(x+1)//2*(x % 2) + x//2*((x+1) % 2))

And here is the output:
0 : 0
1 : -1
2 : 1
3 : -2
4 : 2
5 : -3
6 : 3
7 : -4
8 : 4
9 : -5
10 : 5
11 : -6
12 : 6
13 : -7
14 : 7
15 : -8
16 : 8
17 : -9
18 : 9
19 : -10

No comments:

Post a Comment