CSCI 150: Lab 9

The purpose of this lab is to:

• Review many of the topics from this semester
• Have fun!

Getting Started

This lab has 3 parts. Completing one part successfully leads you the next. You may work with a single partner for all three parts.

There are a few files you'll want for the various parts of this lab. These three files have been included in your repl.it project:

• code.txt
• fruit.bmp
• picture2.py

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

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

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

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 only an integer x and returns an integer indicating the number of elements (i.e., length) in the Syracuse sequence that begins with x (counting the starting number x and the final number 1). So:

• rec(4) should return 3 (the length of the sequence 4 2 1)
• rec(17) should return 13 (the length of the sequenece starting with 17 above)
• rec(14) should return 18 (the length of the sequence starting with 14 above)

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 defined outside of a function). Do NOT use loops within rec. You don't even need to use a list, but it might be helpful to think about how we recursively find the length of a list (from the class slides).

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

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 web address of this page 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 https://cs.oberlin.edu/~aeck/Spring2021/CSCI150/Labs/Lab09/12345.html

Wrap Up

As with every lab, your last job prior to submission is to complete a brief write-up by filling out a Google Form, which is also how you submit your Honor Code statement (so please do not forget to do this).

Handin

Finally, all you need to do is submit your solution to the assignment. To do so, please click on the "Submit" button in the top right of your programming environment. This will save all of your programs for myself and the graders to look at. You are welcome and encouraged to submit partial solutions to your assignment -- you can always resubmit by pushing the "Resubmit" button in the top right, which will save the latest version of your programs. We will only grade the latest version that you submitted. By submitting multiple times, you avoid accidentially forgetting to turn in any completed part of your assignment, especially in case you become busy around the lab due date.

Grading Rubric

syracuse.py (9 points)

Partial Credit