[losvedir]

Yes, exactly, and very clearly written! The trick is at the bottom beneath "SPOILER", but unfortunately I can't think of a good hint that gets you partway there.

I learned of the method as part of the proof that the cartesian product of a countable set is still countable. (i.e. that if the integers are countable, then the set of all pairs (Z,Z) is countable, where Z is an integer.) If you're interested, you can look at Cantor's work on the different magnitudes of infinities. For instance, you'll notice that if (Z,Z) is as infinite as Z, then the set of all rational numbers is "as infinite" as the set of all integers, since a rational number is just one integer divided by another. But what about the real numbers? Cantor showed with a cute diagonalization proof that they are "more infinite". Is anything more infinite than the reals? (Yes) Is there some level of infinity between the rationals and the reals? (I forget, but I think this is unanswerable, or rather, can be proved both ways) Those are some of the questions he worked on.

SPOILER The trick is to think of a big square, with 0,-1,1,-2,2,etc going along the top and 0,-1,1,-2,2,etc going down the left side. Then the ordering is done by infinitely zig-zagging your way down from the top left to the bottom right.

[xenophanes]

Thanks! I worked out a different way, too.

SPOILER

For just positive numbers, have the first number count up to the second number. Then increment the second number and reset the first to 0. Then adjusting for negatives is no big deal. Pretty simple in concept. Here's non-simple ruby code for calculating the pair for any step directly:

  def inefficient(n)
    count = 0
    while n > count
      count += 1
      n -= count
    end
    [n, count]
  end
  
  def with_negatives(n)
    # wastes some steps trying to get the negative version of 0. whatever.
    tmp = inefficient(n/4)
    if n%4 == 1
      tmp[0] *= -1
    elsif n%4 == 2
      tmp[1] *= -1
    elsif n%4 == 3
      tmp[0] *= -1
      tmp[1] *= -1
    end
    tmp
  end
  
  50.times {|n| puts "#{n}: " + with_negatives(n).inspect}

[xenophanes]

Worked out the math to get rid of the loop.

  def efficient(x)
    num = (Math.sqrt(2 * x + 0.25) - 0.5).floor
    num2 = (num**2 + num)/2
    [x-num2, num]
  end

Edit: Or:

  def efficient2(x)
    num = (Math.sqrt(2 * x + 0.25) - 0.5)
    num2 = ((num - num.floor) * num).round
    [num2, num.floor]
  end