The squares of an infinite chessboard are numbered successively as follows: in the lower left corner (first row, first column) we put 0 (zero), and then in every other square we put the smallest nonnegative integer that does not appear to its left in the same row or below it in the same column. See it partially filled:

            |   |   |   |   |   |   |   |   |
            +---+---+---+---+---+---+---+---+--
            | 5 |   |   |   |   |   |   |   |
            +---+---+---+---+---+---+---+---+--
            | 4 | 5 |   |   |   |   |   |   |
            +---+---+---+---+---+---+---+---+--
            | 3 | 2 | 1 |   |   |   |   |   |
            +---+---+---+---+---+---+---+---+--
            | 2 | 3 | 0 | 1 |   |   |   |   | 
            +---+---+---+---+---+---+---+---+--
            | 1 | 0 | 3 | 2 | 5 |   |   |   |
            +---+---+---+---+---+---+---+---+--
            | 0 | 1 | 2 | 3 | 4 | 5 |   |   | 
            +---+---+---+---+---+---+---+---+--

Find the law that rules the numbers that fills the chessboard, so that in seconds, you can evaluate the number that is, for example, in the intersection of the 1000th row and the 100th column.

(In reply to neat by Josh70679)

the trick is, if you're looking for an entry (i,j), look at the binary representation of i-1 and j-1.  Look at all the places where these two numbers differ (ie. where there's a 1 in one, and a 0 in teh other).  Make a binary number with 1's in all of these places.  I posit that this is the entry you're looking for.  BTW: i'm assuming the lower left box is (1,1) not (0,0).  if you're using (0,0), you don't need to subtract 1.  This gives (100,1000) = 900 in the (1,1) representation, or 908 in the (0,0) rep.

Anyone want to check if i'm right?

Posted by Josh70679 on 2005-10-28 13:27:23