Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Wythoff array
open-in-new
<h2 id="values">Values</h2> <p>The Wythoff array has the values </p> 1 2 3 5 8 13 21 ⋯ 4 7 11 18 29 47 76 ⋯ 6 10 16 26 42 68 110 ⋯ 9 15 24 39 63 102 165 ⋯ 12 20 32 52 84 136 220 ⋯ 14 23 37 60 97 157 254 ⋯ 17 28 45 73 118 191 309 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ {\displaystyle {\begin{matrix}1&2&3&5&8&13&21&\cdots \\4&7&11&18&29&47&76&\cdots \\6&10&16&26&42&68&110&\cdots \\9&15&24&39&63&102&165&\cdots \\12&20&32&52&84&136&220&\cdots \\14&23&37&60&97&157&254&\cdots \\17&28&45&73&118&191&309&\cdots \\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\ddots \\\end{matrix}}} (sequence A035513 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>). <h2 id="equivalent-definitions">Equivalent definitions</h2> <p>Inspired by a similar Stolarsky array previously defined by Stolarsky (1977), Morrison (1980) defined the Wythoff array as follows. Let φ = 1 + 5 2 {\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}} denote the <a href="/facts/Golden_ratio/anloSRmD">golden ratio</a>; then the i {\displaystyle i} th winning position in <a href="/facts/Wythoff%2527s_game/FAc7P5Jz">Wythoff's game</a> is given by the pair of positive integers ( ⌊ i φ ⌋ , ⌊ i φ 2 ⌋ ) {\displaystyle (\lfloor i\varphi \rfloor ,\lfloor i\varphi ^{2}\rfloor )} , where the numbers on the left and right sides of the pair define two complementary <a href="/facts/Beatty_sequence/fteXvhIo">Beatty sequences</a> that together include each positive integer exactly once. Morrison defines the first two numbers in row m {\displaystyle m} of the array to be the Wythoff pair given by the equation i = ⌊ m φ ⌋ {\displaystyle i=\lfloor m\varphi \rfloor } , and where the remaining numbers in each row are determined by the Fibonacci recurrence relation. That is, if A m , n {\displaystyle A_{m,n}} denotes the entry in row m {\displaystyle m} and column n {\displaystyle n} of the array, then </p> A m , 1 = ⌊ ⌊ m φ ⌋ φ ⌋ {\displaystyle A_{m,1}=\left\lfloor \lfloor m\varphi \rfloor \varphi \right\rfloor } , A m , 2 = ⌊ ⌊ m φ ⌋ φ 2 ⌋ {\displaystyle A_{m,2}=\left\lfloor \lfloor m\varphi \rfloor \varphi ^{2}\right\rfloor } , and A m , n = A m , n − 2 + A m , n − 1 {\displaystyle A_{m,n}=A_{m,n-2}+A_{m,n-1}} for n > 2 {\displaystyle n>2} . <p>The <a href="/facts/Zeckendorf%2527s_theorem/hg8s2ycr">Zeckendorf representation</a> of any positive integer is a representation as a sum of distinct Fibonacci numbers, no two of which are consecutive in the Fibonacci sequence. As Kimberling (1995) describes, the numbers within each row of the array have Zeckendorf representation that differ by a shift operation from each other, and the numbers within each column have Zeckendorf representations that all use the same smallest Fibonacci number. In particular the entry A m , n {\displaystyle A_{m,n}} of the array is the m {\displaystyle m} th smallest number whose Zeckendorf representation begins with the ( n + 1 ) {\displaystyle (n+1)} th Fibonacci number. </p> <h2 id="properties">Properties</h2> <p>Each Wythoff pair occurs exactly once in the Wythoff array, as a consecutive pair of numbers in the same row, with an odd index for the first number and an even index for the second. Because each positive integer occurs in exactly one Wythoff pair, each positive integer occurs exactly once in the array (Morrison 1980). </p><p>Every sequence of positive integers satisfying the Fibonacci recurrence occurs, shifted by at most finitely many positions, in the Wythoff array. In particular, the Fibonacci sequence itself is the first row, and the sequence of <a href="/facts/Lucas_number/tVbP4yQr">Lucas numbers</a> appears in shifted form in the second row (Morrison 1980). </p> <ul><li><a href="/facts/Clark_Kimberling/WMRRw662">Kimberling, Clark</a> (1995), <a href="http://www.fq.math.ca/Scanned/33-1/kimberling.pdf">"The Zeckendorf array equals the Wythoff array"</a> (PDF), <i><a href="/facts/Fibonacci_Quarterly/c4LDaB5F">Fibonacci Quarterly</a></i>, 33 (1): 3–8, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1080%2F00150517.1995.12429166">10.1080/00150517.1995.12429166</a>.</li> <li><a href="/facts/David_R._Morrison_(mathematician)/qnxgqRrs">Morrison, D. R.</a> (1980), "A Stolarsky array of Wythoff pairs", <a href="http://web.math.ucsb.edu/~drm/papers/stolarsky.pdf"><i>A Collection of Manuscripts Related to the Fibonacci Sequence</i></a> (PDF), Santa Clara, Calif: The Fibonacci Association, pp. 134–136.</li> <li>Stolarsky, K. B. (1977), <a href="http://www.fq.math.ca/Scanned/15-3/stolarsky.pdf">"A set of generalized Fibonacci sequences such that each natural number belongs to exactly one"</a> (PDF), <i><a href="/facts/Fibonacci_Quarterly/c4LDaB5F">Fibonacci Quarterly</a></i>, 15 (3): 224, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1080%2F00150517.1977.12430440">10.1080/00150517.1977.12430440</a>.</li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/WythoffArray.html">"Wythoff Array"</a>. <i><a href="/facts/MathWorld/yc1jodbq">MathWorld</a></i>.</li></ul>