## Generating a strange sequence

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Larson, Moderators General, Prelates

### Generating a strange sequence

User deleted post, which is against the forum rules, so I found the cache and am reposting this. Thanks, Google!
deleted post wrote: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
Last edited by ninjalemon on Mon Jan 30, 2012 3:17 am UTC, edited 1 time in total.
ninjalemon

Posts: 1
Joined: Wed Jan 25, 2012 11:16 pm UTC

### Re: Generating a strange sequence

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

Posts: 83
Joined: Mon Feb 09, 2009 3:51 pm UTC

### Re: Generating a strange sequence

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 = 1denom = 1dir = 1x = 1while 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 + 1end`

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.
EvanED wrote:be aware that when most people say "regular expression" they really mean "something that is almost, but not quite, entirely unlike a regular expression"

language blag

MHD

Posts: 630
Joined: Fri Mar 20, 2009 8:21 pm UTC
Location: Denmark

### Re: Generating a strange sequence

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

PM 2Ring

Posts: 2589
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia