Crikey Math

Having fun exploring mathematics

  • Home
  • About
  • Blog
  • Contribute
en English
af Afrikaanssq Albanianam Amharicar Arabichy Armenianaz Azerbaijanieu Basquebe Belarusianbn Bengalibs Bosnianbg Bulgarianca Catalanceb Cebuanony Chichewazh-CN Chinese (Simplified)zh-TW Chinese (Traditional)co Corsicanhr Croatiancs Czechda Danishnl Dutchen Englisheo Esperantoet Estoniantl Filipinofi Finnishfr Frenchfy Frisiangl Galicianka Georgiande Germanel Greekgu Gujaratiht Haitian Creoleha Hausahaw Hawaiianiw Hebrewhi Hindihmn Hmonghu Hungarianis Icelandicig Igboid Indonesianga Irishit Italianja Japanesejw Javanesekn Kannadakk Kazakhkm Khmerko Koreanku Kurdish (Kurmanji)ky Kyrgyzlo Laola Latinlv Latvianlt Lithuanianlb Luxembourgishmk Macedonianmg Malagasyms Malayml Malayalammt Maltesemi Maorimr Marathimn Mongolianmy Myanmar (Burmese)ne Nepalino Norwegianps Pashtofa Persianpl Polishpt Portuguesepa Punjabiro Romanianru Russiansm Samoangd Scottish Gaelicsr Serbianst Sesothosn Shonasd Sindhisi Sinhalask Slovaksl Slovenianso Somalies Spanishsu Sudanesesw Swahilisv Swedishtg Tajikta Tamilte Teluguth Thaitr Turkishuk Ukrainianur Urduuz Uzbekvi Vietnamesecy Welshxh Xhosayi Yiddishyo Yorubazu Zulu

The diagonal of the Wythoff array

March 9, 2018 By Gary Ernest Davis

New delights and unexpected connections

The late, great, Bill Thurston once wrote:

William Thurston

“Mathematics has a remarkable beauty, power, and coherence, more than we could have ever expected. It is always changing, as we turn new corners and discover new delights and unexpected connections with old familiar grounds.”

 

In the hope of capturing a small glimpse of Thurston’s vision of turning new corners and discovering new delights, I want to talk a little about an interesting sequence of whole numbers.  So enchanting is this sequence that it holds numerous opportunities for investigation by school students, and challenges for research mathematicians.

 

The Wythoff array

The sequence I want to discuss comes from the so-called Wythoff array.

This is an infinite array of whole numbers, the beginning of which looks as follows:

The first row might look familiar: it is, apart from a missing “1”, just the sequence of Fibonacci numbers. As we know, the Fibonacci numbers F_n are determined by the recurrence F_{n+2}=F_{n+1}+F_n and the initial conditions for F_1 and F_2 .

As you can check from the beginning of the array, shown above, the numbers in each row, are, after the first two, just the sum of the two preceding numbers in the row.  Each row, in other words, is just a variant of the Fibonacci sequence: what changes is the pair of initial conditions – the first two numbers – in each row.

This infinite array was named after the Dutch mathematician Willem Abraham Wythoff (1865 – 1939), although Wythoff himself did not write down the array:  D. R.Morrison, in a 1980 article, “A Stolarsky Array of Wythoff Pairs”,  named the array after Wythoff because of Wythoff’s investigations of Wythoff’s game.

The entries in the Wythoff array are easily describable in terms of a recurrence for the entry A_{m,n} in the m^{th} row and n^{th} column:

where \phi =(1+\sqrt{5})/2 and where , for a real number x, \lfloor x\rfloor is the floor of x: the greatest integer \leq x.

There is a way to write the entries of the Wythoff array directly in terms of the Fibonacci numbers, detailed in 1994 by Clarke Kimberling:

The Wythoff array has several interesting features, not the least of which is that every positive integer occurs exactly once in exactly one row of the array.

Question: Can you devise a method (an algorithm?) which, given a positive integer n , finds the position (i,j) – the i^{th} row and j^{th} column – of n.

The diagonal elements

We will denote the diagonal entry A_{n,n} of the Wythoff array by W_n. The recurrence for the general entries of the Wythoff array then gives the following formula to calculate the diagonal entries:

The diagonal entries W_n can also be written in terms of a Fibonacci-like recurrence, but with variable coefficients:

where the coefficients e_n, f_n are rational numbers dependent on n .

To see that this possible and to get an explicit formula for e_n and for f_n   we simply substitute  W_n =\lfloor n \phi \rfloor F_{n+1} + (n-1)F_n into W_{n+2} = e_nW_{n+1}+f_nW_n, use the relation F_{n+1}=F_{n+1}+F_n and equate coefficients of F_{n+1} andF_n.

The result is:

The e_n and f_n are rational numbers and their first few values are:

A plot of e_n and f_n shows irregular oscillatory behavior around the number 1 (e_n in blue and f_n in red):

Computations

It is easy enough to implement the Wythoff array in a spreadsheet.

Here’s the result of calculating the first 10\times 10 entries of the Wythoff array in Excel, using the built-in Excel floor(- ,1) function:

and here are the Excel formulas for the first 4 rows and columns:

Calculations for the diagonal entries W_n are also easy to implement in Excel:

http://www.crikeymath.com/wp-content/uploads/2017/09/crikey.wav

 

 

Filed Under: Uncategorized

Recent Posts

  • Does the DNA test say guilty or not guilty?
  • The Turtleback Diagram for Conditional Probability
  • Numbers that, base 2, are blindingly obviously divisible by 3
  • A mysterious sequence of 1s and 2s
  • Does one have to be a genius to do mathematics? Neither necessary nor sufficient.
  • Alexander Bogomolny
  • Binary disjoints of an integer
  • A cycle of length 5 for iterated squaring modulo a prime
  • The diagonal of the Wythoff array
  • Leonardo Bigollo, accountant, son of Bill Bonacci

Archives

Copyright © 2023 · Dynamik Website Builder on Genesis Framework · WordPress · Log in