**CS 111 w20 --- Lab 8 (OPTIONAL)**
*Due: Monday, March 16, at 9pm*
This lab consists of a sequence of three challenges. They form a sort of treasure hunt and each one leads to the next. They will help you review recursion, using dictionaries, working with image data, and binary. You will need a these two files for various parts of the homework:
- [`encrypted.txt`](encrypted.txt)
- [`fruit.bmp`](fruit.bmp)
This is an optional individual assignment. Each successfully completed challenge (of the three) will earn 5 points of extra credit. Solutions that do not follow the stated rules of a challenge will not receive full points.
---
# Syracuse
The Syracuse problem (also known variously as the 3x+1 problem, the [Collatz Conjecture](http://www.xkcd.com/710/), or Kakutani's problem) concerns a strange collection of sequences. For every positive integer, there is a Syracuse sequence. For example, Syracuse sequence 17 is
17 52 26 13 40 20 10 5 16 8 4 2 1
Can you see the pattern?
The Syracuse sequence for the number $x$ is created by recursively applying the following function $f$, which returns one of two values depending on whether $x$ is even or odd. In particular, $f(x) = 3x+1$ if $x$ is odd, and $f(x) = x/2$ if $x$ is even. Once $f(x)$ is equal to 1, you stop (you could keep going, but at this point we'd just cycle between 4, 2 and 1, so generally we stop the sequence at 1). As another example, Syracuse sequence 14 looks like
14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
Note that once we reach 17, the pattern is the same as the previous one. No one knows whether all Syracuse sequences eventually reach 1. In other words, it is possible that for some starting numbers, the corresponding Syracuse sequences never get to 1. However, mathematicians have checked a few numbers, and at least the first quintillion (a billion billion) of them do make it to 1 eventually.
Write a program called `syracuse.py`. Create a recursive function `syracuse(x)` that takes in an integer `x` and returns an integer indicating the number of elements in the Syracuse sequence that begins with `x` (counting the starting number `x` and the final number `1`). So `syracuse(4)` should return `3`, `syracuse(17)` should return `13`, and `syracuse(28)` should return `19`. You may find it helpful to temporarily use print statements within your recursive function so you can see whether it is behaving as intended, but be sure to remove these once you get it working.
Important: The function `syracuse` may only take in a single integer and may only return a single integer.
**Do NOT use global variables (variables accessible in any function body).**
**Do NOT use loops within `syracuse`.**
Your program should begin by prompting the user for a sequence length (a positive integer). Using a `while` loop and your `rec` function, find the smallest starting integer `x` such that Syracuse sequence `x` has at least the requested length. For example, the first 10 Syracuse sequences have lengths
| | | | | | | | | | | |
|--------------|-|-|-|-|-|-|-|-|-|--|
|Starting Value|1|2|3|4|5|6|7|8|9|10|
|Sequence Length|1|2|8|3|6|9|17|4|20|7|
So if the user entered 6, your program should print 3: the third Syracuse sequence is the first to have length at least 6. Were the user to enter 15, your program should print 7, since all Syracuse sequences from one to six have lengths less than 15, while Syracuse sequence 7 has a length at least 15.
Find the smallest integer $x$ whose Syracuse sequence contains at least 150 numbers. In the homework web address, add the value of $x$ between `hw7` and `.md.html` to get to the next stage. For example, if the correct answer was 12345 (it isn't), you'd go to http://cs.carleton.edu/faculty/awb/cs111/w20/lab8.12345.md.html.
# What to Turn In
- `syracuse.py`: when run it asks the user for a number and then uses a recursive function to find the smallest integer whose Syracuse sequence contains at least that many numbers.
---
Acknowledgments: This assignment description is modified from [Adam Eck's Scavenger Hunt lab](https://www.cs.oberlin.edu/~aeck/Spring2019/CSCI150/Labs/Lab11/).