Lab: Thue Sequence

In this lab, you will develop a program that prints the Thue sequence.

Instructions

You should complete this lab individually.

Background

The Thue sequence describes a sequence of binary strings. The Thue sequence is defined as $T_0 = 0$ and for any $n \geq 0$, $$T_{n+1} = \text{ the concatenation of } T_n \text{ and the complement of } T_n$$

For example:

Step 1: Manual Calculation

Manually calculate $T_3$ and $T_4$. Ask the instructor if you have any difficulty.

Step 2: Python Program

You should develop a Python program to print the nth element of the Thue sequence. Name your program thue.py. The program should accept one argument, a nonnegative integer. For example:

> python thue.py 0
0
> python thue.py 1
01
> python thue.py 2
0110

Hint: Write a recursive method with a base case and recursive case.

Hint: Write a helper method to calculate the complement of a binary string.

Optional: Binary Operations

Internally, Python represents integers and other data in binary. Instead of working with binary strings, it is possible to work directly with binary data. Operations on binary data are more efficient, and binary data will use less memory than binary strings. If you have time, try reimplementing thue.py using bitwise operators. Consult these resources:

• FAQ: What do the operators «, », &, |, ~, and ^ do?
• Bitwise Operations on Integer Types

Submit

Upload thue.py to Gradescope.

Learning Goals

• Understand the Thue sequence
• Implement a sequence by writing a recursive function