# 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 `0 - 1 = -1` , which is a negative value |

2 | 3 | had to add, since subtracting `1 - 2 = -1` , which is a negative value |

3 | 6 | had to add, since subtracting `3 - 3 = 0` , which is already in the sequence |

4 | 2 | able to subtract, since `6 - 4 = 2` , which is both positive and a number that has not yet been used in the sequence |

5 | 7 | had to add, since subtracting `2 - 5 = -3` , which is a negative value |

6 | 13 | had to add, since subtracting `7 - 6 = 1` , which is already in the sequence |

7 | 20 | had to add, since subtracting `13 - 7 = 6` , which is already in the sequence |

8 | 12 | able to subtract, since `20 - 8 = 12` , which is both positive and a number that has not yet been used in the sequence |

## 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_STEP`

to 20? Tell one other person what your guess is, then update the`MAX_STEP`

variable to be 20, and re-run the code. Did it do what you expected? - as you increase the size of the
`MAX_STEP`

variable, you might find it useful to decrease the`SCALE`

variable