Wythoff Array

[John Conway]

On Fri, 9 Jun 2000 karttu at megabaud.fi wrote:
> 
> Aha! By the way, how does Wythoff relate to that array,
> and who was/is Beatty?

   I called it after Wythoff because if one breaks the main body 
the table into pairs thus:

          ---------------------
         | 1  2| 3  5| 8 13|...
         | 4  7|11 18|29 47|...
         | 6 10|...
         | .......

then these are precisely the "safe combinations" in Wythoff's
game (whose definition you can find in "Winning Ways", say).

   Now Wythoff proved that these are precisely the pairs

       [n.tau , n.tau^2]   ( [] = integer part),

where  tau  is the golden number  "(1+root5)/2"  (I prefer this
traditional notation to the more common "phi", from which it
follows that every positive integer appears just once in a
pair of this form.

    Beatty (and others both before and after him - I think
including Wythoff himself!)  generalized this to the observation
that for any pair of irrational numbers  rho, sigma  related
by the condition  1/rho + 1/sigma = 1,  every positive integer
appears just once in a pair of the form

      [n.rho, n.sigma].

   So sequences of the form  [n.rho]  have become known as
"Beatty sequences"  ([n.sigma] being the conjugate one to this).

    John Conway