4. Recamán Sequence Visualization¶
Quick Overview of Day
Introduce the Recamán sequence. Use turtles to make a visualization of the sequence.
CS20-CP1 Apply various problem-solving strategies to solve programming problems throughout Computer Science 20.
CS20-FP1 Utilize different data types, including integer, floating point, Boolean and string, to solve programming problems.
CS20-FP2 Investigate how control structures affect program flow.
CS20-FP4 Investigate one-dimensional arrays and their applications.
4.1. Sequence Description¶
The first few values of the sequence are as follows:
0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11...
The Recamán sequence is generated by the following rules:
begin at 0
each step (change) in the sequence will be one larger than the last step
to get to the next number in the sequence, you will either add or subtract the step size, based on the following criteria:
if subtracting creates a number that is positive, and that you have not yet seen in the sequence, do it
if you cannot subtract based on the rule above, add instead
For the first few values in the sequence, the thought process for applying the rules would be something like:
Change Amount |
Current Value |
Explanation |
|---|---|---|
0 |
0 |
starting value |
1 |
1 |
had to add, since subtracting |
2 |
3 |
had to add, since subtracting |
3 |
6 |
had to add, since subtracting |
4 |
2 |
able to subtract, since |
5 |
7 |
had to add, since subtracting |
6 |
13 |
had to add, since subtracting |
7 |
20 |
had to add, since subtracting |
8 |
12 |
able to subtract, since |
4.2. Generating the Sequence in Python¶
To generate the sequence in Python, we need to keep track of which numbers have already appeared in the sequence. This can be done easily by using a list. Recall that you can add a number to the end of a list using the append method, so you might call numbers_used.append(current), as shown below.
Say you wanted to generate the sequence for first 10 steps. To do this, initialize a variable to hold the current number we are at in the sequence. You also need to create an empty list to keep track of all the numbers we have seen before. When checking to see if you have used a number in the sequence already, you can ask if the number is not in the list.
4.3. Visualizing the Sequence¶
We can use the turtle module to visualize the sequence. In order to explore the following code, you might want to copy/paste this into Thonny.
To start exploring this, consider the following:
run the code as it is first. What do you think it would look like if we increased the
MAX_STEPto 20? Tell one other person what your guess is, then update theMAX_STEPvariable to be 20, and re-run the code. Did it do what you expected?as you increase the size of the
MAX_STEPvariable, you might find it useful to decrease theSCALEvariable