Title: Generate Fibonacci words in Python

[Fibonacci subwords and words generated in Python]

The Fibonacci word is a particular sequence of binary digits formed by repeatedly concatenating subwords similarly to the way you calculate Fibonacci numbers by adding the two previous numbers. The sequence of digits is infinite and non-repeating so, if you use the digits to build a number, the result is transcendental like π and e.

To build part of the Fibonacci word, you first need to know about Fibonacci subwords.

Fibonacci Subwords

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

S0 = 0 S1 = 01

Later Fibonacci subwords are given by:

Sn = Sn-1 + Sn-2

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

0 01 010 01001 01001010 0100101001001 010010100100101001010 0100101001001010010100100101001001 0100101001001010010100100101001001010010100100101001010

You can define the unique Fibonacci word as the infinite expansion of the subwords.

The Fibonacci subwords have many interesting properties including:

Each subword begins with the previous subword. (That's obvious from the way you calculate Sn.)
Every subword appears infinitely many times. (Because of the preceding property, each subword begins all of the subwords that follow it.)
The subwords alternately end with 01 and 10.
If you remove the last two letters from a subword (except for the first one, which doesn't have two letters), you get a palindrome.
Sn-1 + Sn-2 and Sn-2 + Sn-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 subwords and the Fibonacci word, see the Wikipedia article Fibonacci word.

Generating Subwords

The example program uses the following function to generate Fibonacci subwords.

def fibo_subword(n): '''Calculate the nth Fibonacci subword.''' if n == 0: return '0' if n == 1: return '01' S2 = '0' # S - 2 S1 = '01' # S - 1 S0 = '010' # S (Initially S = 2.) for i in range(2, n): S0 = S1 + S2 S2 = S1 S1 = S0 return S0

This function simply follows the rules for building Fibonacci subwords.

The example program uses the following code snippet to loop through the desired number of words and displays them in the upper list box.

# List the subwords. self.subwords_list.delete(0, tk.END) for i in range(num_words): self.subwords_list.insert(tk.END, f'{i:3}: {fibo_subword(i)}')

Note that the Fibonacci subwords become very long quickly. The example's spinbox will only go up to 20 so the program will only create up to 20 Fibonacci subwords with the longest having 6,765 characters. If you try to find much longer words, the program will use up all of your computer's memory and crash.

Generating Fibonacci Words

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.

def fibo_word(n): # Calculate the nth Fibonacci word. if n < 1: return '' return fibo_subword(n-1)

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

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

To find the Nth Fibonacci word, notice that the first two Fibonacci subwords have length 1. After that, each subword's length is the sum of the two previous words' lengths. This is the same as the definition of the Fibonacci numbers except the numbers start at 0 and the lengths start a 1.

That means the length of the Nth Fibonacci subword equals the (N-1)th Fibonacci number.

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

def fibo_word(n): # Calculate the nth Fibonacci word. if n < 1: return '' return fibo_subword(n-1)

This function simply returns the (n-1)th Fibonacci subword.

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

# List the words. self.words_list.delete(0, tk.END) for i in range(num_words): self.words_list.insert(tk.END, f'{fibo_number(i)}: {fibo_word(i)}')

Conclusion

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.