Title: Calculate Fibonacci words in C#

You can find Fibonacci words by concatenating previous Fibonacci words much as you calculate the Fibonacci sequence by adding previous values in the sequence. The first two Fibonacci words are:

S0 = 0
S1 = 01

The following Fibonacci words are given by:

Sn = Sn-1 + Sn-2

For example, the following list shows the first few Fibonacci words.

0
01
010
01001
01001010
0100101001001
010010100100101001010
0100101001001010010100100101001001
0100101001001010010100100101001001010010100100101001010

To distinguish these "words" from another set that I will describe shortly, I'll call these values Fibonacci sub-words.

If you define a unique "Fibonacci word," it is the infinite expansion of the sub-words.

The Fibonacci sub-words have many interesting properties such as:

• Each sub-word begins with the previous sub-word. (Due to the way you find S_n.)
• Every sub-word appears infinitely many times. (Because of the preceding property, each sub-word begins all of the sub-words that follow it.)
• The sub-words alternately end with 01 and 10.
• If you remove the last two letters from a sub-word (except for the first one, which doesn't have two letters), you get a palindrome.
• S_n-1 + S_n-2 and S_n-2 + S_n-1 differ only in their last two letters.
• The infinite Fibonacci word never ends and is not periodic. That means the decimal value built by using the Fibonacci digits 0.0100101001001... is transcendental (like π and e).

For other properties of Fibonacci words, see the Wikipedia article

When you click the Go button, the example program uses the following method to generate Fibonacci sub-words.

// Calculate the nth Fibonacci sub-word. private string FiboS(int n) { if (n == 0) return "0"; if (n == 1) return "01"; string s2 = "0"; // s - 2 string s1 = "01"; // s - 1 string s0 = "010"; // s (Initially s = 2.) for (int i = 2; i < n; i++) { s0 = s1 + s2; s2 = s1; s1 = s0; } return s0; }

This method simply follows the rules for building Fibonacci sub-words. The example program uses the following code to loop through the desired number of words and displays them in the upper list box.

int num_words = int.Parse(txtN.Text); // List sub-words. lstS.Items.Clear(); for (int i = 0; i < num_words; i++) { lstS.Items.Add(FiboS(i)); }

Note that the Fibonacci sub-words become very long quickly. If you set n too big, the program will use up all of your computer's memory and crash. The list boxes can't display more than about 20 sub-words anyway before the sub-words get too long. For that reason, you may want to limit n to 20 or so.

There's another definition for Fibonacci words that I want to use in my next post. In this version, the Nth Fibonacci word has length equal to the Nth Fibonacci number. The example program uses the following method to calculate Fibonacci numbers.

// Return the nth Fibonacci number. private int Fibo(int n) { if (n <= 1) return n; int n2 = 0; // n - 2 int n1 = 1; // n - 1 int n0 = n1 + n2; // n (Initially n = 2.) for (int i = 2; i < n; i++) { n2 = n1; n1 = n0; n0 = n1 + n2; } return n0; }

This method simply uses the following definition of the Fibonacci sequence.

Fibo(0) = 0
Fibo(1) = 1
Fibo(n) = Fibo(n-1) + Fibo(n-2)

The example uses the following method to calculate Fibonacci words using the new definition with defined lengths.

// Calculate the nth Fibonacci word. private string FiboWord(int n) { // See how long it should be. int length = Fibo(n); string s2 = "0"; // s - 2 string s1 = "01"; // s - 1 string s0 = "010"; // s (Initially s = 2.) while (s0.Length < length) { s0 = s1 + s2; s2 = s1; s1 = s0; } return s0.Substring(0, length); }

This method works much as the previous version did except it doesn't create a specific number of sub-words. Instead it continues its loop until it generates a sub-word that is long enough. It then returns a substring from that sub-word with the desired length.

The program uses the following code to display this kind of Fibonacci word in the lower list box.

// List words. lstWords.Items.Clear(); for (int i = 0; i < num_words; i++) { lstWords.Items.Add(Fibo(i).ToString() + ": " + FiboWord(i)); }

In my next post, I'll show how you can use a slightly modified version of Fibonacci words to create an interesting curve called the Fibonacci word fractal.

Download the example to experiment with it and to see additional details.