15-112 Fall 2015 Homework 2
Due Sunday, 13-Sep, at 10pm

Read these instructions first!

• This hw is SOLO. See the syllabus for details.
• There is no starter file this week. Instead, you should download hw1.py from hw1, and rename it to hw2.py. Then replace the functions above the #ignore_rest line with your autograded functions (and their helper functions, if any), and replace the test functions below the #ignore_rest line with your new test functions. Remember: all the code above the #ignore_rest line is autograded, and all the code below it is ignored.
• Starting this week, you may use loops, but (as usual) you may not use constructs we have not yet covered (strings, lists, sets, maps, recursion, etc), unless explicitly allowed below.
• Seeing as you do not have a starter file this week, we will still allow more Autolab submissions than usual. Even so, to help avoid an overreliance on the autograder, this week you may only make up to 10 submissions max to Autolab. As usual, only your last one counts.
• Do not use global variables! Do use test functions!
• You can and should use previous functions on the hw to solve later functions.
• You also can and should use your own helper functions, where appropriate.
• And you also can use anything from the course notes, including isPrime, fasterIsPrime (which you can rename to isPrime), and nthPrime. Just cite it if you use it, and be sure you can also generate the code from first principles!
• While optional this week, you are still strongly encouraged to attend small-group CA sessions. These should be a big help for hw2.

---

1. Happy Numbers [25 pts]
   Background: read the first paragraph from the Wikipedia page on happy numbers. After some thought, we see that no matter what number we start with, when we keep replacing the number by the sum of the squares of its digits, we'll always either arrive at 4 (unhappy) or at 1 (happy). With that in mind, we want to write the function nthHappyNumber(n). However, to write that function, we'll first need to write isHappyNumber(n) (right?). And to write that function, we'll first need to write sumOfSquaresOfDigits(n). And that's top-down design! Here we go....
   
   Note: the autograder will grade each of the following functions, so they are required. However, they also are here specifically because they are just the right helper functions to make nthHappyNumber(n) easier to write!
   
   
   1. sumOfSquaresOfDigits(n)
      Write the function sumOfSquaresOfDigits(n) which takes a non-negative integer and returns the sum of the squares of its digits. Here are some test assertions for you:

      assert(sumOfSquaresOfDigits(5) == 25)   # 5**2 = 25
      assert(sumOfSquaresOfDigits(12) == 5)   # 1**2 + 2**2 = 1+4 = 5
      assert(sumOfSquaresOfDigits(234) == 29) # 2**2 + 3**2 + 4**2 = 4 + 9 + 16 = 29
      

   2. isHappyNumber(n)
      Write the function isHappyNumber(n) which takes a possibly-negative integer and returns True if it is happy and False otherwise. Note that all numbers less than 1 are not happy. Here are some test assertions for you:

      assert(isHappyNumber(-7) == False)
      assert(isHappyNumber(1) == True)
      assert(isHappyNumber(2) == False)
      assert(isHappyNumber(97) == True)
      assert(isHappyNumber(98) == False)
      assert(isHappyNumber(404) == True)
      assert(isHappyNumber(405) == False)
      

   3. nthHappyNumber(n)
      Write the function nthHappyNumber(n) which takes a non-negative integer and returns the nth happy number (where the 0th happy number is 1). Here are some test assertions for you:

      assert(nthHappyNumber(0) == 1)
      assert(nthHappyNumber(1) == 7)
      assert(nthHappyNumber(2) == 10)
      assert(nthHappyNumber(3) == 13)
      assert(nthHappyNumber(4) == 19)
      assert(nthHappyNumber(5) == 23)
      assert(nthHappyNumber(6) == 28)
      assert(nthHappyNumber(7) == 31)
      

   4. nthHappyPrime(n)
      A happy prime is a number that is both happy and prime. Write the function nthHappyPrime(n) which takes a non-negative integer and returns the nth happy prime number (where the 0th happy prime number is 7).


2. nearestKaprekarNumber(n) [25 pts]
   Background: a Kaprekar number is a non-negative integer, the representation of whose square can be split into two possibly-different-length parts (where the right part is not zero) that add up to the original number again. For instance, 45 is a Kaprekar number, because 45**2 = 2025 and 20+25 = 45. You can read more about Kaprekar numbers here. The first several Kaprekar numbers are: 1, 9, 45, 55, 99, 297, 703, 999 , 2223, 2728,...
   
   With this in mind, write the function nearestKaprekarNumber(n) that takes an int or float value n and returns the Kaprekar number closest to n, with ties going to smaller value. For example, nearestKaprekarNumber(49) returns 45, and nearestKaprekarNumber(51) returns 55. And since ties go to the smaller number, nearestKaprekarNumber(50) returns 45.
   
   Note: as you probably guessed, this also cannot be solved by counting up from 0, as that will not be efficient enough to get past the autograder. Hint: one way to solve this is to start at n and grow in each direction until you find a Kaprekar number.


3. nthCarolPrime(n) [25 pts]
   Write the function nthCarolPrime(n), which takes a non-negative int and returns the nth Carol Prime, which is a prime number of the form ((2**k - 1)**2 - 2) for some value positive int k. For example, if k equals 3, ((2**3 - 1)**2 -2) equals 47, which is prime, and so 47 is a Carol Prime. The first several Carol primes are:
      7, 47, 223, 3967, 16127, 1046527, 16769023,...
   As such, nthCarolPrime(0) returns 7.
   
   Note: You must use a reasonably efficient approach that quickly works up to n==9, which will return a 12-digit answer! In particular, this means you cannot just edit nthPrime (or fasterIsPrime) to call isCarolPrime instead of isPrime. Hint: you may need to generate only Carol numbers, and then test those as you go for primality (and you may need to think about that hint for a while for it to make sense!).


4. integral(f, a, b, N) [25 pts]
   Background: in calculus, we use the integral of a function f from x=a to x=b to compute the area under the curve between those points (or the negative area if the function is below the x-axis). One way to approximate this area (that is, to find it without doing any actual calculus!) is by replacing the smooth function with a collection of N trapezoids, as shown in this image (from here, with N=5):
   
   
   As in that image, here we will only use uniform widths, so each of the trapezoids has a width of (b - a)/N, so that all N of them together span the width of (b - a).
   
   In any case, the larger N is, the more trapezoids you use, the more accurate your approximation becomes. You can read more here about this so-called trapezoidal rule.
   
   With this in mind, write the function integral(f, a, b, N) that takes a Python function f (that itself takes one value x, a float, and returns a float), and two floats a and b, where a<=b, and a positive int N, and uses the trapezoidal rule with N trapezoids to return the approximate area under the curve of f(x) where a <= x <= b. To be clear, in the case where N=1, this uses just one trapezoid, where the left edge is at (a, f(a)) and the right edge is at (b, f(b)), so the result is (b - a) * (f(a) + f(b))/2 (the width times the average height of the trapezoid).
   
   Hint: you should use almostEqual in your test function. Also, you'll probably want to use some very simple curves for testing, such as f(x)=x, f(x)=2*x+3, and f(x)=2*x**2, and then in ranges (a,b) with values of N such that you can fairly easily compute the expected answer by hand.
   
   Another hint: here is a basic example showing how functions work as parameters to other functions:

   def f1(x): return x+1
   def f2(x): return x+2
   def h(f): return f(10)
   print(h(f1)) # calls f1(10), prints 11
   print(h(f2)) # calls f2(10), prints 12
   



5. Bonus/Optional: carrylessMultiply(x, y) [2 pts]
   Write the function carrylessMultiply(x, y), that works similarly to carrylessAdd(x, y) from the hw2-practice problems, based on this paper on Carryless Arithmetic. This paper shows that carrylessMultiply(643, 59) returns 417. Hint: it may help if you do this differently than usual long multiplication. Instead of working by rows in the output, work by columns. So first compute all the ones digit values, and sum those mod 10. Then compute all the tens digit values, and sum those mod 10. And so on. You may assume x and y are non-negative.


6. Bonus/Optional: play112 (The 112 Game) [3 pts]
   Read the writeup for "The 112 Game" here (skip to Part B). Be sure to follow the spec exactly, so the autograder can properly grade your work! As with all bonus, we recommend that you only do this for the joy of learning (which is great), and not for the points (which are modest).