• This hw is SOLO.  As explained in the course syllabus, you must not discuss these problems or share your code with anyone else except for the course staff and the tutors at Academic Development.  This includes students from former semesters (who may indeed have the answers to these problems!).
• All rules of hw1 apply, except now you may use loops and conditionals (of course!).
   
• Important note #1: your hw2.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 hw2 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 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 5 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 hw2.  In particular:
  • Create this folder for your work:
         mkdir ~/private/15112/hw/hw2/
  • Get your hw2.py starter code from here:
         cp /afs/cs.cmu.edu/academic/class/15112-s12/www/handouts/hw2.py .   [Don't miss the trailing dot!]
  • Get your hw2-public-grader.py public autograder from here:
         cp /afs/cs.cmu.edu/academic/class/15112-s12/www/handouts/hw2-public-grader.py .    [Ditto!]
  • Test your code like so:
         python hw2-public-grader.py
  • Submit your code like so:
         submit-hw2
     
• Remember: You can (and should) test your code on your machine as often as you like, but...  You may only submit 5 times total!

1. Happy Numbers
2. Counting Primes
3. bonus/optional: leastCommonMultiple
4. bonus/optional: latticePointsVisibleFromTheOrigin
5. bonus/optional: swapBits
6. bonus/optional: sortBits

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.
       
3. bonus/optional: leastCommonMultiple  [1 pt]
   Write the function leastCommonMultiple that takes two possibly-negative integers m and n and returns the smallest positive number p such that both m and n evenly divide p.  To do so, you must use Euclid's GCD algorithm (look it up), along with the fact that the product of two numbers equals the product of their gcd and their lcm.
    
4. bonus/optional: latticePointsVisibleFromTheOrigin  [1 pt]
   A lattice point is an ordered pair (x,y) where both x and y are integers.  With this in mind, write the function latticePointsVisibleFromTheOrigin that takes a non-negative integer n, and returns a value between 0 and 1 representing the fraction of the n² lattice points in the square from (0,0) to (n-1,n-1) that are visible from the origin (that is, where a line segment from the origin to that lattice point does not first pass exactly through another lattice point, and, to avoid ambiguity, we will exclude the origin itself from the list of visible lattice points from the origin).  Interestingly, as n tends to infinity, this value converges to 6/pi².  It is amazing how often pi unexpectedly shows up! 
    
5. bonus/optional: swapBits  [1 pt]
   Write the function swapBits that takes a non-negative but possibly-long int value followed by 3 more non-negative int values -- start1, start2, and k -- and returns the value formed by swapping the k bits starting from start1 (where 0 is the rightmost bit, and the bits move leftward as k increases) with the k bits starting from start2.  If these two ranges overlap, just return -1.  Also, assume as many leading 0's as needed.  For example, consider swapBits(329, 3, 7, 2).  First, we see that 329 in binary is:
        0b101001001
   The first segment starts at bit 3 and is of length 2, so is the segment highlighted in green here:
        0b101001001
   The second segment starts at bit 7 and is also of length 2, so is the segment highlighted in yellow here:
        0b101001001
   When we swap these segments, we get this number:
        0b011010001
   This equals 209, which is the result of calling swapBits(329, 3, 7, 2).
    
6. bonus/optional: sortBits  [2 pts]
   Write the function sortBits that takes a non-negative but possibly-long int value followed by a non-negative int value k, and uses selectionsort along with the swapBits function you just wrote to return the value formed by sorting the k-bit segments of the original number (assuming as few leading 0's as are required so that the bit length is a multiple of k).  For example, consider sortBits(13708, 3).  First, we see that 13708 in binary is:
        0b11010110001100
   Now, let's write that again, breaking it up into 3-bit segments:
        0b 011 010 110 001 100
   And then we will sort those segments, from least to greatest:
        0b 001 010 011 100 110
   And let's write that as a single binary number:
        0b001010011100110
   Finally, this equals 5350, which is the result of calling sortBits(13708, 3).

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