• This lab is SOLO.  See hw1 and the syllabus for details.
• Except as noted below, follow the steps in hw2, except (of course) replace hw2 with hw3.
• You may now use loops and conditionals, but you still may not use the other constructs we've not yet covered.
• You may only submit 4 times total!

1. nthWithProperty309
2. nthSquareSumOfTwoSquares
3. nthSmithNumber
4. nthKaprekarNumber
5. bonus/optional: findZeroWithBisection

1. nthWithProperty309  [25 pts]
   We will say that a number n has "Property309" if its 5th power contains every digit (from 0 to 9) at least once.  309 is the smallest number with this property.  Write the function nthWithProperty309 that takes a non-negative int n and returns the nth number with Property309.
    
2. nthSquareSumOfTwoSquares  [25 pts]
   Write the function nthSquareSumOfTwoSquares that takes a non-negative int n and returns the nth number that is itself a perfect square and is also the sum of two other positive perfect squares.  For example, the first such number is 25, because 25=5**2, and 25 = 16 + 9 = 4**2 + 3**2.
    
3. nthSmithNumber  [25 pts]
   Write the function nthSmithNumber that takes a non-negative int n and returns the nth Smith number, where a Smith number is a composite (non-prime) the sum of whose digits are the sum of the digits of its prime factors (excluding 1). Note that if a prime number divides the Smith number multiple times, its digit sum is counted that many times. For example, 4 equals 2**2, so the prime factor 2 is counted twice, thus making 4 a Smith Number.
    
4. nthKaprekarNumber  [25 pts]
   Write the function nthKaprekarNumber that takes a non-negative int n and returns the nth Kaprekar number, where a Kaprekar number is a non-negative integer, the representation of whose square can be split into two 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.
    
5. bonus/optional: findZeroWithBisection [2 pts]
   Aside: as we will cover more carefully later in the course, a function may take another function as an argument.  For example, consider this code:
   def h(n):
       return n+5
   def f(g, x):
       return 2*g(x)
   print f(h,3) # prints 16
   Here, we define a function f whose first argument is another function.  On the last line, we call f providing the function h, which is bound in f to the parameter g.  Hence, calls to g in f are really calls to h.  Play around with the sample code to get the hang of this idea.  Then, read the next preliminary topic...
   
   In mathematics, one way to numerically (as opposed to algebraically) find a zero of a function f(x) is to use what amounts to binary search.  To start, we need to know two values, x0 and x1, with x0<x1, where f(x0) and f(x1) have different signs (so one is positive and the other is negative).  Hence, by the Intermediate Value Theorem, we know there is some value x in the range [x0,x1] such that f(x)=0.  It is that value of x that we are seeking.  How?  First, try the value xmid, which is the midpoint between x0 and x1.  If f(xmid) is exactly 0, we are done!  Otherwise, we can divide our range in half as such:  if f(xmid) and f(x0) are the same sign, use the range [xmid, x1].  Otherwise, f(xmid) and f(x1) must share the same sign, so use the range [x0, xmid].  We repeat this in a loop until x0 and x1 are within some suitably small epsilon.
    
   With this in mind, write the function findZeroWithBisection that takes a function f, a float x0, a float x1, and a float epsilon, and returns an approximate value x in [x0,x1] where f(x) is approximately zero.  Your function should stop when x0 and x1 are within epsilon, and at that time should return the midpoint of that range.  Note that if it is not true that exactly one of f(x0) and f(x1) is negative, your function should return the Python value None, signifying that the bisection method cannot be used on the given range.
   
   Let's see this in action!  First, we'll use it to approximate the square root of 2 without the ** operator:
   
   print "use bisection to approximate sqrt(2):"
   def f1(x): return x*x - 2 # root at x=sqrt(2)
   x = findZeroWithBisection(f1, 0, 2, 0.000000001)
   print " x =", x                # prints  x = 1.41421356192
   print " check: x**2 =", (x*x)  # prints  check: x**2 = 1.99999999871 (really close!)
   
   Next, let's use it to approximate phi (the golden ratio), without using the closed-form solution ((1 + sqrt(5))/2), instead using the interesting property of phi that adding one to it is the same as squaring it.  That is, ((phi + 1) == phi**2).  How do use that?  Simple, convert it into an equation equal to 0:  phi**2 - (phi + 1) == 0.  Now we're set!  (Of course, we could just use the Quadratic Formula here, but it's more interesting to use bisection, now that we have it!).
   
   print "use bisection to approximate phi (the golden ratio):"
   def f2(x): return x**2 - (x + 1) # root at x=phi
   x = findZeroWithBisection(f2, 0, 2, 0.000000001)
   print " x =", x                  # prints x = 1.61803398887
   phi = (1 + 5**0.5)/2             # the actual value (to within Python's floating point accuracy)
   print " check: x/phi =", (x/phi) # prints check: check: x/phi = 1.00000000007 (nice!)
   
   The previous two examples are nice, but simpler techniques than bisection would have worked as well.  So let's solve a problem that would be hard to solve without bisection (or some other numeric approximation algorithm).  Specifically, find a number x such that x⁵ == 2^x:
   
   print "use bisection to approximate x where x**5 == 2**x"
   def f3(x): return x**5 - 2**x # f(1)<0, f(2)>0
   x = findZeroWithBisection(f3, 1, 2, 0.000000001)
   print " x =", x                              # prints x = 1.17727855081
   print " check: x**5 - 2**x =", (x**5 - 2**x) # prints check: x**5 - 2**x = 3.63570817896e-09 (great!)
   
   Hopefully this bisection excursion helps you appreciate the awesome computational power that about 10 lines of Python can have!

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