Tag Archives: number bases

Fibonacci-Based Arithmetic

Games/Experiments, Number Theory, ,

[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!

Further Reading

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. [↩]

A Distinctly Odd Coincidence

Counting/Probability, Proofs, , , , , , ,

This week’s topic comes from partition theory. Consider all the ways to write 7 as the sum of positive integers:
$$\begin{align*}
&7, && 3+2+2,\\
&6+1, && 3+2+1+1,\\
&5+2, && 3+1+1+1+1,\\
&5+1+1, && 2+2+2+1,\\
&4+3, && 2+2+1+1+1,\\
&4+2+1, && 2+1+1+1+1+1,\\
&4+1+1+1, && 1+1+1+1+1+1+1+1.\\
&3+3+1, &&
\end{align*}$$ (We don’t care about order: for example, \(5+2\) and \(2+5\) are the same.) These are called the partitions of 7, and there are 15 of them.

We can also consider imposing constraints on these partitions: For example, how many of these partitions of 7 use only odd integers? These “odd” partitions are
$$\begin{align*}
& 7, && 3+1+1+1+1, \\
& 5+1+1, && 1+1+1+1+1+1+1, \\
& 3+3+1, &&
\end{align*}$$ and there are 5 of them. Here’s a very different question: how many partition of 7 have no repeated parts? These “distinct” partition are
$$\begin{align*}
& 7, && 6+1, && 5+2, && 4+3, && 4+2+1,
\end{align*}$$ and there are 5 of these as well.

This must be coincidence, right? Let’s try a bigger example. How many partitions of 11 use only odd parts? You can (and should!) check that there are 12. And how many partitions of 11 use only distinct parts? Again, there are 12. Surprisingly, these numbers will always match!:

Theorem (Euler): For any positive integer \(n\), the number of “odd” partitions of \(n\) is the same as the number of “distinct” partitions of \(n\).

Transforming Between “Odd” and “Distinct” Partitions

Let’s try to make sense of this. Given a partition of \(n\) into odd parts, there is a simple way to transform it into a partition with distinct parts: whenever two parts are the same, add them together, and repeat until they are all distinct. For example, the partition \(7+3+3+3+3+3+3+1+1+1\) of 28 is transformed into
$$\begin{align*}
& 7+(3+3)+(3+3)+(3+3)+(1+1)+1 \\
& \quad \to 7+(6+6)+6+2+1 \\
& \quad \to 12+7+6+2+1,
\end{align*}$$ which has distinct parts. In the other direction, to transform a “distinct” partition to an “odd” one, we can reverse this process: whenever there is an even part, cut it in half and write it twice. Our example \(12+7+6+2+1\) from above becomes
$$\begin{align*}
& (6+6)+7+(3+3)+(1+1)+1 \\
&\quad \to (3+3)+(3+3)+7+3+3+1+1+1,
\end{align*}$$ which is the “odd” permutation we started with. These transformations can be shown to match “odd” permutations with “distinct” permutations in pairs, proving that these sets have the same size. (A careful argument uses binary representation.) For example, the 5 partitions of 7 above are paired as follows:
$$\begin{align*}
& 7 &&\leftrightarrow && 7 \\
& 6+1 &&\leftrightarrow && 3+3+1 \\
& 5+2 &&\leftrightarrow && 5+1+1 \\
& 4+3 &&\leftrightarrow && 3+1+1+1+1 \\
& 4+2+1 &&\leftrightarrow && 1+1+1+1+1+1+1.
\end{align*}$$ (If you know something about generating functions, then a different proof follows by proving the identity
$$\frac{1}{(1-x)(1-x^3)(1-x^5)(1-x^7)\cdots} = (1+x)(1+x^2)(1+x^3)(1+x^4)\cdots$$ and noting that the coefficients of \(x^n\) in the expansions of the left and right products equals the number of “odd” and “distinct” permutations of \(n\), respectively.)

More Coincidences

These apparent coincidences are characteristic of many results in partition theory. Try your hand at proving the following generalization:

Theorem: The number of partitions of \(n\) into parts that are not divisible by 10 equals the number of partitions of \(n\) where no part is repeated 10 or more times. The same is true for any positive integer in place of 10.

(Hint: both methods used above can be extended to prove this.) If instead we want the parts to be really distinct and make sure no two parts are equal or consecutive, then we want my favorite partition theory result:

Theorem (Rogers-Ramanujan Identity): The number of partitions of \(n\) where any two parts differ by at least 2 is the same as the number of partitions of \(n\) where every part is one more or one less than a multiple of 5.

Despite the simplicity of the statement, this is much harder to prove than the previous theorems.

“Read Backwards” Month

Games/Experiments, Number Theory, , , ,

There are quite a few beautifully symmetric dates that present themselves this month, including 11/1/11, 11/02/2011, 11/05/2011 (use a mirror!), 11/11/11, and 11/22/11. In honor of this phenomenon, I want to say a few words about palindromes, which are simply things that read the same backwards as forwards. A few famous examples include “racecar,” “Never odd or even,” “I prefer pi”, “Dr. Awkward”, “Aibohphobia” (which means fear of palindromes [I didn’t make this up!]), “Go hang a salami; I’m a lasagna hog!”, or if you read by word instead of by letter, “Blessed are they that believe that they are blessed.”

If we consider digits instead of letters or words, then numbers such as 676, 100020001, and 12345678987654321 are palindromes. These are in fact quite special palindromes, as they are all squares of integers: \(26^2 = 676\), \(111111111^2 = 12345678987654321\), and \(10001^2 = 100020001\). Are there infinitely many palindromic squares? Yes: the last example above hints that \(10\ldots01^2 = 10\ldots020\ldots01\) for however many 0s you put in the middle. By contrast, if we ask for \(n^5\) to be palindromic (or any higher power), then no solutions are currently known!

You might ask for other types of palindromic numbers, such as palindromic primes. A few examples include 7 (this is a palindrome!), 101, 19391, and 1000000008000000001. Are there infinitely many? We don’t know. But the largest palindromic prime currently known is \(10^{200000} + 47960506974 \cdot 10^{99995} + 1\), according to Wikipedia.

For one more game, here’s a way to make palindromes out of non-palindromes. Start with a non-palindrome, like 86, and keep adding it to its reversal until you get a palindrome: e.g., 86+68 = 154, 154+451 = 605, and 605+506 = 1111, which is a palindrome. How quickly will this terminate? Well, try starting with 89 and see how long it takes! (Answer: it finally stops at a 13-digit palindrome.) But surely it always terminates eventually, right? Surprisingly, the answer to this question is currently unknown. In fact, it is unknown if the sequence starting at 196 ever finds a palindrome!

Finally, if you still want more to think about, try repeating this entire discussion in another base, e.g. base 2. Good luck!

All Your Base (Jokes)

Computer Science, Number Theory, , , ,

There’s something unsatisfyingly arbitrary about the number 10. When we write numbers, e.g. 1729, our notation means that we have 1 thousand (\(10^3\)), 7 hundreds (\(10^2\)), 2 tens (\(10^1\)), and 9 ones (\(10^0\)), so the number 10 is ingrained in our very writing system. And it’s not just the Arabic numeral system: Roman numerals also organize themselves around powers of 10 (such as I=1, X=10, C=100, etc.). But why 10? (Other than the fact that we usually have 10 fingers and 10 toes [why not 20 instead?].)

Our “decimal” system centers around powers of 10, but there are other equally useful systems based on other numbers. For example, we could use sums of powers of 2, and instead of needing 10 digits (0,1,…,9) we can use just 2, namely 0 and 1. For example, the number 1101 in base 2 means \(1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0\), also known as 13 in base 10. This may seem inefficient, since we need more digits (or, more correctly, “bits” in the binary setting) to express the same value, but it has many benefits. Each bit has only 2 choices, and can therefore be represented by a pair of opposites such as “on/off” (e.g. in circuits) or the two magnetic polarities. The latter is how hard drive disks store information (in binary!), which is one reason this system is beloved by computer scientists. It also allows for jokes like this: “There are 10 types of people in the world: those that understand binary, and those that don’t.”

Another common base is Hexadecimal, using powers of 16 with digits 0,…,9,A,B,C,D,E,F. (A hexadecimal digit is sometimes called a “nibble”.) It is common to prefix a hexadecimal number with “0x”, so 0x3B7 means \(3 \cdot 16^2 + 11 \cdot 16 + 7 = 951\) in decimal. It also makes the phrase “I see 0xDEAD people” perfectly reasonable (how many is that?).

But there are more possibilities still! For example, the octal system uses powers of 8 and (octal) digits 0,…,7. With this we can prove Christmas and Halloween are really the same holiday: indeed, Dec 25 = Oct 31. And don’t miss the octal system’s cameo in Tom Lehrer’s New Math song.

The possibilities are endless! We can use base \(n\) for any positive integer \(n>1\) in similar ways, but we can also use negative \(n\) as well! (My favorite is base -4.) If you want to go ever further, think about what base \((1+\sqrt{5})/2\) (a.k.a. phinary) would look like! Or the related bases Fibonacci and NegaFibonacci!