• This will be a normal (not pass/fail) autograded lab (so we will not have small-group grading sessions as in lab1).
• All the work for this lab should be done collaboratively, with other students in the course, preferably in groups of about 4-5.  Form study groups and work together.  If you need help, ask for it.  If you are in the position to offer help, please do so!
• Even though this is collaborative, each student must submit separately.
• For all programs:  You must use Linux.  You must use vi and no other editor.  You may, of course, use loops or conditionals this week.
   
• Important note #1: your lab2.py starter code is nearly empty (all it does is invoke the public autograder).  You'll need to add all the function definitions from scratch! 
• Important note #2:  the lab2 public autograder is intentionally very incomplete.  The private autograder will test many more cases.  As such, do not rely on the public autograder to do all your testing.  Of course, you and and should use it to be sure you pass whatever tests it includes.  But you should also add your own test code (after the "ignore_rest" line, so the autograder ignores it).
• Important note #3:  you may only submit 3 times total!  Coupled with the previous note, this places increased responsibility on you to do your own testing in addition to what we provide you.
   
• To obtain starter code and to submit your code for autograding, follow the steps in hw1, except (of course) replace hw1 with lab2.  In particular:
  • Create this folder for your work:
         mkdir ~/private/15112/hw/lab2/
  • Get your lab2.py starter code from here:
         cp /afs/cs.cmu.edu/academic/class/15112-f11/www/handouts/lab2.py .   [Don't miss the trailing dot!]
  • Get your lab2-public-grader.py public autograder from here:
         cp /afs/cs.cmu.edu/academic/class/15112-f11/www/handouts/lab2-public-grader.py .    [Ditto!]
  • Test your code like so:
         python lab2-public-grader.py
  • Submit your code like so:
         submit-lab2
     
• Remember: You can (and should) test your code on your machine as often as you like, but...  You may only submit 3 times total!  (If you submit a 4th time, at least as Autolab is presently set up, you will receive 0/100 on the lab!)

1. Happy Numbers
   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 right that function, we'll first need to write sumOfSquaresOfDigits(n).  And that's top-down design!  Here we go....
    
   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
      print "Passed all tests!"
   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)
      print "Passed all tests!"
   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)
      print "Passed all tests!"
   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. Counting Primes
   In this exercise, we will observe an amazing property of the prime numbers!
    
   1. The Prime Counting Function:  pi(n)
      Write the function pi(n) (which has nothing much to do with the value "pi", but coincidentally shares its name) that takes an integer n and returns the number of prime numbers less than or equal to n.  Here are some test assertions for you:
      assert(pi(1) == 0)
      assert(pi(2) == 1)
      assert(pi(3) == 2)
      assert(pi(4) == 2)
      assert(pi(5) == 3)
      assert(pi(100) == 25)  # there are 25 primes in the range [2,100]
      print "Passed all tests!"
       
   2. The Harmonic Number:  h(n)
      Write the function h(n) that takes an int n and, if n is positive, returns the sum of the first n terms in the harmonic series:  1/1 + 1/2 + 1/3 + 1/4 + ...  If n is non-positive, the function returns 0.  Here are some test assertions for you:
      assert(almostEquals(h(0),0.0))
      assert(almostEquals(h(1),1/1.0                ))  # h(1) = 1/1
      assert(almostEquals(h(2),1/1.0 + 1/2.0        ))  # h(2) = 1/1 + 1/2
      assert(almostEquals(h(3),1/1.0 + 1/2.0 + 1/3.0))  # h(3) = 1/1 + 1/2 + 1/3
      print "Passed all tests!"
      Note:  here we use "almostEquals" rather than "==" because this function returns a floating-point number.  You should also write almostEquals.
       
   3. Using the Harmonic Number to estimate the Prime Counting Function (Wow!)
      Write the function estimatedPi(n) that uses the Harmonic Number function to estimate the Prime Counting Function.  Think about it.  One counts the number of primes.  The other adds the reciprocals of the integers.  They seem totally unrelated, but they are in fact very deeply related!  In any case, this function takes an integer n and if it is greater than 2,  returns the value (n / (h(n) - 1.5) ), rounded to the nearest integer (and then cast to an int).  If n is 2 or less, the function returns 0.  Here are some test assertions for you:
      assert(estimatedPi(100) == 27)
      print "Passed all tests!"
       
   4. Empirical check that this really works:  estimatedPiError
      Write the function estimatedPiError that takes an integer n and returns the absolute value of the difference between the value of our estimation computed by estimatedPi(n) and the actual number of primes less than or equal to n as computed by pi(n).  If n is 2 or less, then function returns 0.  Here is the start of a test function:
      assert(estimatedPiError(100) == 2) # pi(100) = 25, estimatedPi(100) = 27
      assert(estimatedPiError(200) == 0) # pi(200) = 46, estimatedPi(200) = 46
      assert(estimatedPiError(300) == 1) # pi(300) = 62, estimatedPi(300) = 63
      assert(estimatedPiError(400) == 1) # pi(400) = 78, estimatedPi(400) = 79
      assert(estimatedPiError(500) == 1) # pi(500) = 95, estimatedPi(500) = 94
      print "Passed all tests!"
      Aside:  as you can see, the estimatedPi function is an amazingly accurate estimation of the pi function.  For example, the estimatedPi function predicts that there should be 94 prime numbers up to 500, and in fact there are 95 prime numbers in that range.  And so we must conclude that there is some kind of very deep relationship between the sum of the reciprocals of the integers (1/1 + 1/2 + ...) and the number of prime numbers.  This relationship has been explored in great detail by many mathematicians over the past few hundred years, with some of the most important results in modern mathematics relating to it.

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem