**Homework 4: Loop** **Reed CSCI 121 Fall 2022**   *complete the exercises by 9am on 9/27* In the last two homeworks we practiced using two kinds of Python constructs that allow a programmer to "*control the flow*" of the interpreter's execution of statements in your program. These were (1) the `if` statement that provides conditional execution and (2) the `def` statement that provides a means for defining functions to help compute values. With *conditional statements*, the program might skip past some blocks of statements, or it may execute one block versus another, all depending on some condition that's checked by that `if` statement. With *function definitions*, a program can jump to a named section of code to perform some actions, or to compute some result, all towards serving the work of the main script. These `def` statements act as useful "modules" that serve the main script. The *function call mechanism* which requires the calling code to pass *parameter values* to the function, and then (possibly) get a value upon the function's `return`, imposes a discipline that helps the programmer structuretheir code in a readable way. Each function definitions provides a reusable code component. This week we practice using Python's `while` statement for structuring code. A `while` statement provides *iteration*: the program can execute a *loop*. It can repeatedly perform a series of actions until some condition is met. For example, the code below counts from 1 to 10. It keeps printing then adding one to the variable `count` until that variable gets larger than 10: ~~~ python print("I will now count from 1 to 10...") count = 1 while count <= 10: print("The count is now " + str(count) + ".") count = count + 1 // Increments the count variable by 1. print("There. I am done counting.") ~~~ Here is what that code does: After executing the first two lines, the program will execute the `print` and the increment statements inside the `while` statement's *body*. This is because the `count` variable is only at `1`, and that value is less than or equal to 10. After executing those two lines once, the interpreter "jumps" back to the condition line to see whether `count <= 10`. Since the condition is still true (`count == 2` and `2 <= 10`), it runs those two lines again and re-checks the condition. It keeps looping through those three code lines-- checking the condition, printing, incrementing-- until the assignment statement changes the value of `count` from `10` to `11`. When the loop condition is checked an 11-th time, the condition will then be `False`, and the program skips to the line below the loop body. It prints the message "`There. I am done counting.`" The problems below ask you to write functions that each work in this way. You will use a `while` loop (or loops) to do each function's work. (##) Submission and Scoring Submit each source file containing a Python function definition, possibly with some other "helper" functions, to the Gradescope site. The problems below are labeled the way they will appear as submission items in Gradescope. We'll run tests on your submission to see if your code is correct. Before submitting, you should test your function on several scenarios, making sure it works with a good variety of parameters. Only submit it when you have reasonable confidence that it is correct. Some of the problems allow you to assume that a function's client code won't feed the function certain kinds of parameter values. When we allow you to make assumptions like that, your code need not check for parameters that aren't assumed to happen. Each problem is worth 30 points. 10 of the points are awarded based on the number of tests you pass. An additional prize of up to 10 points will be awarded if *all* the tests pass by the due date. You'll earn fewer of these prize points if you have to submit a problem several times to get all the tests to pass. Another 10 points will be offered after the deadline based on the quality of your code. You should look for straight-forward solutions to solve the puzzle, and your code should be clear and easy to understand. In cases where you feel the need to do something complicated-- some programming puzzles require tricky coding-- you should include comments that (briefly) explain your code's approach. (#) Problems (##) `[HW4 P1]` sum cubes Write a function `sum_cubes` that takes an integer parameter `n` and returns the sum of the first `n` cubes, that is, the sum suggested by $$1^3 + 2^3 + 3^3 + \cdots + n^3$$ So, for example, `sum_cubes(3)` should evaluate to `36` because it is the sum of the first three cubes $1 + 8 + 27$. For values of `n` that are less than `1`, your function should return `0`. Place your function definition in a file named `sum_cubes.py` and test it with different values in the Python interpreter before you submit the code. ~~~ jimfix@C02F48U1ML7H homework4 $ python3 -i sum_cubes.py >>> sum_cubes(3) 36 >>> sum_cubes(-1) 0 ~~~ (##) `[HW4 P2]` perfect square Write a function `def perfect_square(number)` that takes an integer parameter `number` and determines whether it is a square of some other number. It should return `True` when the number is a perfect square. It should return `False` otherwise. For example: ~~~ python >>> perfect_square(81) True ~~~ because $81 = 9^2$. And also ~~~ python >>> perfect_square(21) False ~~~ because $4^2 = 16 < 21 < 25 = 5^2$. Negative numbers are not perfect squares. Zero and one are perfect squares of themselves. Do not use floating point calculations to compute this result. (##) `[HW4 P3]` divisors Write a function `def divisors(number)` that takes a positive integer and returns a report of all the positive integer divisors of that number. That report should be in the form of a string that lists the divisors in order, starting with `1`. If there are more than two divisors, it should use an [Oxford comma](https://en.wikipedia.org/wiki/Serial_comma) before the mention of the last divisor. Here is an example use of the function. ~~~ none >>> divisors(35) 'The divisors of 35 are 1, 5, 7, and 35.' >>> divisors(1) 'The divisor of 1 is 1.' >>> divisors(2) 'The divisors of 2 are 1 and 2.' ~~~ It takes an integer and returns a string. **The `divisors` function does not print anything.** **Hint:** Your function should seek to build a string by looping through all the possible divisors and appending them to that report string using the string concatenation operation `+`. It then will want to append information to the front and back of that report. What it appends will depend on whether there is only one divisor, or two divisors, or more than two divisors. Use integer division to figure out divisibility. (##) `[HW4 P4]` magnitude People often talk about the order of magnitude of an amount. In doing so, they are often thinking in terms of [powers of ten](https://www.youtube.com/watch?v=0fKBhvDjuy0). Let's instead give a very computer science-y definition of the *magnitude* of a number based on powers of two. The first seven powers of two are 1, 2, 4, 8, 16, 32, and 64. We'll say that * 0 is of magnitude 0; * 1 is of magnitude 1; * 2 and 3 are of magnitude 2; * 4, 5, 6, and 7 all are of magnitude 3; * the numbers from 8 to 15 are of magnitude 4; and so on. Note that 30 is of magnitude 5 because it is less than 32, and $32 = 2^5$. But it is also that magnitude because dividing it by 2 yields 15, and 15 is magnitude 4. In other words, the number 30 has one more order of magnitude than 15 because it is twice as big, and because we have chosen to think in base two. Write a function `magnitude` that returns the magnitude of a non-negative integer as we describe above. For example, your function's code should work as follows: ~~~ python >>> magnitude(0) 0 >>> magnitude(1) 1 >>> magnitude(2) 2 >>> magnitude(3) 2 >>> magnitude(15) 4 >>> magnitude(30) 5 >>> magnitude(1023) 10 >>> magnitude(1024) 11 ~~~ You can assume `magnitude` is called only with numbers 0 or larger. **Hint**: The magnitude can be computed by counting the number of times you can divide by two until there is nothing left to divide. You should not use any floating point operations to do this work. It turns out that the magnitude of a positive number is just the number of bits in its binary representation. Even so, you cannot use any Python-provided library functions that perform binary conversion. You should instead compute this magnitude "from scratch" using integer division. (##) `[HW4 P5]` Euclid In the Western world, Euclid is often touted as the inventor of the first recorded algorithm. In Book VII of Euclid's *Elements*, he lays out a description of determining whether two integers have a common divisor, or else are relatively prime. He writes "***When two unequal numbers are set out, and the less is continually subtracted in turn from the greater, if the number which is left never measures the one before it until a unit is left, then the original numbers are relatively prime.***" (See the [Proposition](http://aleph0.clarku.edu/~djoyce/elements/bookVII/propVII1.html)) He is describing an iterative process that starts with two positive integers. If the two numbers are the same, then their common divisor is their whole self. If instead one of the numbers is `1`-- if it is "a unit"-- then the process stops having determined that they have no common divisor. If the numbers differ and are both greater than `1`, then repeat the process using the smaller number of the pair along with the positive difference between the pair-- the subtraction of the lesser from the greater. Write a function `def euclid(a,b)` that performs Euclid's algorithm to determine whether or not two positive numbers have a common divisor by performing this process. For example, if the function is handed `15` and `24`, the process should repeat with `9` and `15` (because `9` equals `24 - 15`), and then `9` and `6`, and then `6` and `3`, and then `3` and `3`. Because these are equal, it stops and returns `True`. As another example, if the numbers it is given are `7` and `5`, then its process repeats with `5` and `2` (because `2` equals `7 - 5`), then with `3` and `2`, then `2` and `1`. Because one of these is `1` it then stops and returns `False`. ~~~ python >>> euclid(15,24) True >>> euclid(7,5) False ~~~ Your function can assume that its two parameters are both greater than 1. You need not worry about handling other kinds of parameters. (##) `[HW4 P6]` reverse number The table below illustrates an iterative process for examining the digits of a number. In particular, it computes the number whose decimal digits are the reverse of that number: number |reverse ------:|------: 53137 | 0 5313 | 7 531 | 73 53 | 731 5 | 7313 0 | 73135 The first row starts with a number and also 0. Each subsequent row of the table advances a calculation on those two numbers that has the effect of changing their digits. The first column gives the result of the number above it when it is divided by 10. The second column is the number above it, multiplied by 10, and with the last digit "lost" from the first column because of the division by 10 added to it. For example, the row with `531` and `73` is followed by a row containing `53` and `731` because `53 == 531 // 10` and because `731 == 73*10 + 1`. In this exercise, generalize your code for **[HW2 P3]** so that it computes the reverse as shown in the table. Write the code as a function `def reverse_number(n)` instead of as a script. (Put the definition in a file named `reverse_number.py`.) It should take a non-negative integer `n` as a parameter and it should return the integer whose digits are the reverse of the decimal representation of `n`. ~~~ none >>> reverse_number(53137) 73135 >>> reverse_number(0) 0 >>> reverse_number(2112) 2112 >>> reverse_number(1234567) 7654321 ~~~ Your code should use only integer operations. It should not use floating point, nor should it convert the integer to a string to obtain the decimal digits. Instead, I recommend writing code that mimics the caclulations shown in the table just above. (##) `[HW4 P7]` count palindromes A number is a *decimal palindrome* whenever it reads the same forwards and backwards. For example `747`, `2112`, `0`, and `1234567654321` are all decimal palindromes. Write a procedure `def count_palindromes(limit)` that gives the numbers from 0 up to `limit` that are decimal palindromes. For example: ~~~ none >>> count_palindromes(999) 109 >>> count_palindromes(1000) 109 >>> count_palindromes(1001) 110 >>> count_palindromes(77) 17 >>> count_palindromes(10) 10 ~~~ The last result is `10` because the single-digit numbers 0 through 9 are all decimal palindromes. The next-to-last result is `17` because 11, 22, 33, 44, 55, 66, and 77 are also decimal palindromes.