Positions in the Wythoff array

Question

Suppose that $x$ and $y$ are positive integers. How can the position of $x+y$ in the Wythoff array (A035513) be predicted from the positions of $x$ and $y$?

Background. The Wythoff array begins with

   1    2    3    5    8   13   21   34   55   89  144 ...
   4    7   11   18   29   47   76  123  199  322  521 ...
   6   10   16   26   42   68  110  178  288  466  754 ...
   9   15   24   39   63  102  165  267  432  699 1131 ...
  12   20   32   52   84  136  220  356  576  932 1508 ...
  14   23   37   60   97  157  254  411  665 1076 1741 ...
  17   28   45   73  118  191  309  500  809 1309 2118 ...
  19   31   50   81  131  212  343  555  898 1453 2351 ...
  22   36   58   94  152  246  398  644 1042 1686 2728 ...

As an example, take $x=11$ and $y=26$, from positions $(2,3)$ and $(3,4)$. The sum $37$ is in position $(6,3)$.

Answer 1

Because the Wythoff array is an encoding of the Zeckendorf representation (the representation of an integer as a sum of nonconsecutive Fibonacci numbers), one can use algorithms that, given the Zeckendorf representations of two integers $x$ and $y$, find the Zeckendorf representation of their sum $z=x+y$, as presented in Efficient Algorithms for Zeckendorf Arithmetic (2012).

Answer 2

Here is an expansion on Carlo's answer. It is more in the nature of clarifying what is sought as well as a nice parallel.

First another well known permutation of the integers is the the 2-ary array (A054582). For technical reasons is it convenient to index rows and columns starting with $0$

$\left[ \begin {array}{cccccc} 1&2&4&8&16&32\\ 3&6& 12&\mathbf{24}&48&96\\ 5&10&\mathbf{20}&40&80&160\\ 7&14&28&56&112&224\\ 9&18&36&72&144&288 \\ 11&22&\mathbf{44}&88&176&352\end {array} \right]$

The analogous question is

Given pairs $(i,j)$ and $(k,\ell)$ find the pair $(p,q)$ giving the position of the sum of the entries in the two given positions.

for example given $(1,3)$ and $(2,2)$ we wish to get back $(5,2)$ since the corresponding entries are $24$ $20$ and $44$

It is not required to find $24,20$ and $44$ nor is it forbidden.

That is one strategy because we easily find

DECODE: The find the entry at position $(i,j),$ multiply $(2i+1)\cdot 2^j$

ENCODE: To find the position of $n$ factor out the twos to get $n=(2i+1)\cdot 2^j$

So then an easy solution to the given problem is decode $(i,j)$, decode $(k,\ell)$, add the results (however one adds) and then encode the sum.

It is relevant to use binary rather than decimal for the array hence

$\left[ \begin {array}{cccccc} 1&10&100&1000&10000&100000 \\ 11&110&1100&11000&110000&1100000 \\ 101&1010&10100&101000&1010000&10100000 \\ 111&1110&11100&111000&1110000&11100000 \\ 1001&10010&100100&1001000&10010000&100100000 \\ 1011&10110&101100&1011000&10110000&101100000 \end{array}\right]$

DECODE: Write $i$ in binary (better yet, use binary) write another $1$ then end with $j$ $0$'s This gives you the entry in binary.

So given $(10,3)$ we write $10$ in binary then a $1$ then $3$ zeros $1010\ 1\ 000$ i.e. $10101000$ Given a second pair we could write a second binary string and then perform binary addition. It is true that $21\cdot 2^3=168=10101000_2$ but in some sense we stayed closer to the given information. Especially if instead of calling it row $10$ we call it row $1010$

ENCODE: Given $n$ convert it to binary (better yet, get it in binary). The number of terminal $0$'s give the column and the head, removing the last $1$ gives the row.

Recall that there are two common ways to get the binary expansion of $i$: go right to left putting a 1 for odd $n$ and replacing it by $\frac{n-1}2$ or $0$ for even $n$ then replacing with $\frac{n}2.$ OR we can go left to right subtracting off the largest possible power of $2$ , say $2^i$ and putting a $1$ then continue considering $2^j$ for $j=i-1,i-2,\cdots$ each time either subtracting and putting a $1$ or just putting a $0$ according as the current value is or is not at least $2^j.$

The second method applied using the Fibonacci numbers $\cdots 13,8,5,3,2,1$ gives the unique Zeckendorf representation of $n$ as a binary vector with no two consecutive $1$'s. (I don't know if there is an easy right to left method.)

Using this representation turns the array of the question

$\left[ \begin {array}{cccccc} 1&2&3&5&8&13\\ 4&7&11 &18&29&47\\ 6&10&16&26&42&68\\ 9& 15&24&39&63&102\\ 12&20&32&52&84&136 \\ 14&23&37&60&97&157\end {array} \right] $

into

$\left[ \begin {array}{cccccc} 1&10&100&1000&10000&100000 \\ 101&1010&10100&101000&1010000&10100000 \\ 1001&10010&100100&1001000&10010000&100100000 \\ 10001&100010&1000100&10001000&100010000& 1000100000\\ 10101&101010&1010100&10101000&101010000 &1010100000\\ 100001&1000010&10000100&100001000& 1000010000&100001000000\end{array} \right]$

If one has the first column then one has the Zeckendorf representation of the entry in position $(i,j)$ and can do the appropriate addition, which is not quite as easy as binary addition but not too bad. And there are formulas such as $\lfloor i \tau^2 \rfloor-1=\lfloor i \tau \rfloor+i-1.$ Here $\tau$ could be replaced by a sufficiently good ratio of Fibonacci numbers. This still leaves some loose ends such as how to figure out the row from the representation.