Generating a strange sequence

[ninjalemon]

User deleted post, which is against the forum rules, so I found the cache and am reposting this. Thanks, Google!

In my Logic class for CS, my professor gave us an interesting puzzle to think about and I'm totally stumped and was curious if anybody else has seen this before.

His question was "How did I generate the following sequence, and why is it useful or important?"

With the sequence being 1/2, -1/2, 1/3, -1/3, 3/2, -3/2, 2/3, -2/3

I can't think of why this may be important, or what the next numbers in this sequence could be?

To stop you from deleting it again, I have removed your editing rights ~~Felstaff

[DrZiro]

Does it have something to do with proving that the rational numbers are countable?

[MHD]

This is pretty close to a combination of the coutnability of the Interegers and the countability of the rationals.

To refer to a set as "countable" is to say that all the elements can be assigned a unique natural number sequentially.
(In technical terms a bijection exists between the set and the naturals numbers, or a subset thereof.)

The alphabet is countable (the alphabet is also finite, and finite sets are countable)

Code: Select all

1  2  3  4  5  6  7  8  9  ...
a  b  c  d  e  f  g  h  i  ...

We can also count the negative integers.

Code: Select all

   1  2  3  4  5  6  ...
  -1 -2 -3 -4 -5 -6  ...

Now, counterintuitively we can count all the integers/whole numbers.

Code: Select all

1  2  3  4  5  6  7  8  9  ...
0  1 -1  2 -2  3 -3  4 -4

Here comes the tricky part. Now we want to count the rationals, but let's make it easy and count only the rational numbers with natural numbers as numerator and denominator.
This can be done with the algorithm:

Code: Select all

num = 1
denom = 1
dir = 1
x = 1

while true do
  if denom == 1 then
    num = num + 1
    dir = -dir
  else if num == 1 then
    denom = denom + 1
    dir = -dir
  else
    num = num + dir
    denom = denom - dir
  end

  print x, ":", num, "/", "denom"
  x = x + 1
end


Draw a coordinate system with two axes, X and Y. At every point (x, y) for natural numbers x and y, you write the fraction x/y. Then you put your pencil down at 1/1, count "one" and draw a line parallel to the X axis to 2/1 counting "two", then a diagonal line to 1/2 counting "three", then a line parallel to the Y axis to 1/3 counting "4", then a diagonal the other way to 2/2 (which is equal to 1/1, so we disregard it), then again a diagonal line to 3/1 counting "five", then a line paralell to the X axis to 4/1 counting "six" ...

What your professor has done is essentially the same thing, only using the integer counting above to also count in the negative rationals.

[PM 2Ring]

You might want to re-check that code, MHD. It appears to contain a bug or two.