# Fibonacci-Based Arithmetic

[This is the final Wythoff's game post. See the previous ones here: #1, #2, #3, #4, #5, #6. We'll have a few shorter, 1- or 2-post topics starting next week.]

In our standard, base-10 number system, each position represents a specific power of 10: the number 275 in base 10 means that I have five 1s, seven 10s, and two 100s. Similarly, in the base-2 system, each position represents a different power of 2: 10011 in base 2 says I have a 1, a 2, and a 16, but no 4s or 8s.[1] Instead of using powers of 10 or 2, what happens if we use Fibonacci numbers?

We can find the Fibonacci numbers by starting[2] at $$a_1=1$$ and $$a_2=2$$ and then computing each term as the sum of the two previous ones, $$a_n=a_{n-1}+a_{n-2}$$:

1, 2, 3, 5, 8, 13, 21, 34, 55, …

Let’s use these as our position values in our so-called Fibonacci base, using just the digits 0 and 1. For example, 1010011F stands for $$a_7+a_5+a_2+a_1 = 21+8+2+1 = 32$$.

Notice that $$a_2+a_1=a_3$$, so we can write 32 instead as $$a_7+a_5+a_3$$, meaning 32=1010100F. In much the same way, any time we have a Fibonacci representation of a number, we can repeatedly use the identity $$a_n=a_{n-1}+a_{n-2}$$ to ensure that we never use consecutive Fibonacci numbers:

Theorem (Zeckendorf): Every positive integer can be expressed in base Fibonacci with no adjacent 1s. Furthermore, this representation is unique.

The “base-Fibonacci representation” of a number usually refers to its Zeckendorf representation as in this theorem. There’s a simple greedy method to find a number’s Zeckendorf representation: use the largest Fibonacci number less than (or equal to) your number, and repeat on the remainder. For example, to represent 46 in this way, check that the largest Fibonacci number below 46 is $$a_8=34$$, leaving 12 as the remainder. The largest Fibonacci number below (or equal to) 12 is $$a_5=8$$, with a remainder of 4. Now we have to use $$a_3=3$$, and finally we’re left with $$1=a_1$$. So $$46=a_8+a_5+a_3+a_1=10010101_F$$ is the Zeckendorf representation of 46.

But why discuss base Fibonacci now? What does this have to do with Wythoff’s game? Zeckendorf representations provide another simple way to characterize the losing positions in Wythoff’s game! Here’s a beautiful result:

Theorem: If $$a \le b$$ are positive integers, then $$(a,b)$$ and $$(b,a)$$ are losing position in Wythoff’s game precisely when:

• The Zeckendorf representation of a ends in an even number of 0s, and
• The Zeckendorf representation of b is the same as that of a except for one more 0 on the end.

For example, 11=10100F ends in two 0s (two is even), and 18=101000F has the same representation except for an extra 0 at the end, so (11,18) and (18,11) are Wythoff losing positions. Unlike the formula using multiples of $$\phi$$ and $$\phi^2$$ that we proved in the last few posts, this provides a method we could actually compute (without a calculator) on reasonably-sized grids when playing with friends (or enemies)! After all we’ve learned about Wythoff’s game, we finally have a way to win it!

Our Wythoff’s game saga is now ending here on Three-Cornered Things, but here are a few recommended resources if you wish to further explore this rich topic on your own:

### Notes

1. If these concepts are unfamiliar, see this previous post on number bases. []
2. Careful: these indices are shifted from the other common convention that starts the Fibonacci numbers at $$F_1=1$$ and $$F_2=1$$, which is why I’m using as instead of Fs. []

### 1 Comment

1. Brent Yorgey says:

Aww, no proof? I guess I’ll just have to try to prove it myself. =)