Category Archives: Number Theory

Fibonacci-Based Arithmetic

July 6, 2012Games/Experiments, Number TheoryFibonacci numbers, number bases, Wythoff's gameZachary Abel

[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, 1010011_F 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=1010100_F. 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=10100_F ends in two 0s (two is even), and 18=101000_F 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!

Notes

If these concepts are unfamiliar, see this previous post on number bases. [↩]
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 “Frac”ing Prime Generator

November 14, 2011Computer Science, Number TheoryFRACTRAN, John Conway, primes, sequences/seriesZachary Abel

Last week we saw a few ways to (try to) generate prime numbers with simple formulas. I will now describe a much more puzzling (and recreational) method. The following numbers specify everything you need: $$\left(\frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{14}, \frac{15}{2}, \frac{55}{1} \right).$$ To run this “game,” the rules are as follows: Start with value $v = 2$. At each step, find the first fraction $f$ in the list so that $v \cdot f$ is an integer, and replace the value $v$ by this integer. Repeat indefinitely (or until no such $f$ can be found). The beginning of the computation looks like this:

Start with value $v = 2$.
The first fraction $f$ in the list such that $2\cdot f$ is an integer is $f=15/2$, so the new value $v$ is $2 \cdot 15/2 = 15$.
The first $f$ in the list with $15 \cdot f$ an integer is $f=55/1$, so the new $v$ is $15 \cdot 55/1 = 825$.
The first $f$ with $825 \cdot f$ an integer is $29/33$, so set $v = 825 \cdot 29/33 = 725$.

And so on.

Continuing as above, the list of values looks like 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, 30, 225, 12375, … .

But what does this have to do with primes? The list of fractions was carefully constructed so that many powers of 2 will appear, in exactly the following order: $$2^1, 2^2, 2^3, 2^5, 2^7, 2^{11}, 2^{13}, 2^{17}, \ldots .$$ Indeed, except for $2^1$ (the starting value), any power of two obtained by this process will have a prime exponent, and all primes will appear in this way (in order)! This is a very special property of the chosen list of fractions, and different lists give rise to vastly different output sequences.

In fact, you can think of this procedure as a programming language, where the list of fractions and the starting value constitute your “program.” This language is called FRACTRAN, and both the language and the above prime-enumerating program were designed by John Conway. What else is this language capable of computing? Lots! FRACTRAN can compute anything that modern computers could—but much less efficiently. (In Theoretical Computer Science terminology, FRACTRAN is turing complete.) See the Wikipedia page for more information, as well as an explanation of why the above program works.

Generating Primes with Formulas

November 7, 2011Algebra, Number Theory, ProofsFermat primes, large numbers, Mersenne primes, polynomials, primesZachary Abel

Prime numbers—namely, positive integers with no divisors other than 1 and themselves—have long fascinated mathematicians. As a result, there have been many attempts at formulas to generate prime numbers. For example, the polynomial $x^2-x+41$ spits out a prime number for $x = 0, 1, 2, …, 40$. But for $x = 41$, the value is $41^2$, which is not prime. Can we find some nonconstant polynomial $f(x)$ with integer coefficients that only spits out prime values? (The constant polynomial $f(x) = 2$ always returns a prime, but this is not very interesting.) In a word: No. There is no such polynomial. To prove this, assume $f$ is such a polynomial. Then $f(0) = p$ for some prime $p$, and all of the numbers $\{f(p), f(2p), f(3p), \ldots \}$ are divisible by $p$. This sequence grows toward infinity, so one of them is greater than $p$. Since this number has a factor of $p$, it is not prime.

What if we switch from polynomials to exponents? Maybe the function $2^m + 1$ will give us lots of primes. It can be shown that if $2^m + 1$ is prime then $m$ itself has to be a power of 2. (Indeed, if a prime $p > 2$ divides $m$, check that $2^{m/p} + 1$ divides $2^m + 1$.) So the only possibilities are the numbers $F_n = 2^{2^n} + 1$, which are called Fermat numbers. The first few are $$\begin{align*}
F_0 &= 3,\\
F_1 &= 5,\\
F_2 &= 17,\\
F_3 &= 257,\\
F_4 &= 65537.
\end{align*}$$ It was long believed that all Fermat numbers were prime (Fermat himself conjectured this!), but in fact the very next one, $F_5 = 4294967297 = 641 \cdot 6700417$, is composite. (In Fermat’s defense, this is a large number to factor by hand!) Are there at least infinitely many Fermat primes? We currently don’t know. In fact, the Fermat primes shown above are the only known Fermat primes!

Similarly, numbers of the form $2^n-1$ are called Mersenne numbers. In order for this to be prime, it is necessary for $n$ itself to be prime. (Indeed, if $a$ divides $n$ then $2^a-1$ divides $2^n-1$.) So is $2^p-1$ prime for every prime $p$? Unfortunately, no: $2^{11}-1$ is not prime. But there seem to be many Mersenne primes. Thanks to the “Great Internet Mersenne Prime Search,” a.k.a. GIMPS, there are 47 Mersenne primes known, the largest of which is $2^{43112609}-1$, which has 12978189 digits (in base 10).

OK, so the above “prime-generating” functions don’t work very well. Here’s one that does work. It can be shown that there is some polynomial $Z(a, b, c, d, e, f, g, h, i, j)$ with 10 variables and integer coefficients such that any positive output from $Z$ (when given integer inputs) is prime, and furthermore, every prime is obtained in this way. (Note: $Z$ spits out many non-positive values as well.) Unfortunately, this polynomial $Z$ is not very practical. For one thing, its degree is about $38!$. (Yes, I mean 38 factorial.)

“Read Backwards” Month

November 1, 2011Games/Experiments, Number Theoryinteger powers, large numbers, number bases, palindromes, primesZachary Abel

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)

October 24, 2011Computer Science, Number Theorybinary, Fibonacci numbers, golden ratio, number bases, Tom LehrerZachary Abel

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!

Three-Cornered Things

Zachary Abel's Math Blog