# CSCI 150: Lab 7

Scavenger Hunt!
Due: 10PM on Tuesday, April 4

The purpose of this lab is to:

• Review recursion and other past topics
• Have fun!

## Getting Started

Before you begin, please create a folder called lab07 inside your cs150 folder. This is where you should put all files made for this lab.

This lab has 4 parts. Completing one part successfully leads you the next, so only part 1 is available to you initially. If you don't make it through all the parts, do a handin with the programs you did complete.

There are a few files you'll want for the various parts of this lab. Save these four files [1], [2], [3] and [4] to your working directory before you begin.

As a reminder, our six-step process for creating programs is as follows:

As this course moves forward, the labs will become progressively less and less explicit about these steps. That doesn't mean you're now free to forget about them! Your job is to figure out what makes sense for each of these steps yourself.

## Part 1 - Syracuse

The Syracuse problem (also known variously as the 3x+1 problem, the Collatz Conjecture, 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 a certain function f to x which depends on the parity of x. In particular, f(x) = 3x+1 if x is odd, and f(x) = x/2 if x is even. Once you get 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 rec(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 rec(4) should return 3, rec(17) should return 13, and rec(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 rec 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 rec.

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 Sequence Length 1 2 3 4 5 6 7 8 9 10 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 lab url, replace the "index" in the above url with the value of x to get to the next stage. For example, if the correct answer was 12345 (it isn't), you'd go to http://cs.oberlin.edu/~aeck/Spring2017/CSCI150/Labs/Lab07/12345.html

## Wrap Up

As with every lab, your last job prior to submission is to complete a brief write-up in a README file. If you haven't already done so, please create a new README file in your lab07 folder.

In this file, write a sentence or two about what you learned in this lab. Also give an estimate of the amount of time you spent on the lab. If you have further thoughts about the lab (e.g. parts that were confusing, helpful, annoying, fun, or challenging), please let us know.

## Handin

As usual, you'll want to do a handin after each part of this lab, so refer back here as you finish subsequent parts.

If you followed the Honor Code in this assignment, insert a paragraph attesting to the fact within a README file.

I affirm that I have adhered to the Honor Code in this assignment.

You now just need to electronically handin all your files. As a reminder

```
% cd             # changes to your home directory
% cd cs150       # goes to your cs150 folder
% handin         # starts the handin program
# class is 150
# assignment is 7
# file/directory is lab07
% lshand         # should show that you've handed in something
```

You can also specify the options to handin from the command line

```
% cd ~/cs150     # goes to your cs150 folder
% handin -c 150 -a 7 lab07
```