CMU 15-112: Fundamentals of Programming and Computer Science
Extra Practice for Week 2 (Due never)

• These problems will help you prepare for hw2 and quiz2. They are optional and you are encouraged to collaborate when working on them.


• You may also wish to see extra-practice2-ct-and-roc.html.


• To start:
  1. Create a folder named 'week2'
  2. Download both extra_practice2.py and cs112_f19_week2_linter.py to that folder
  3. Edit extra_practice2.py
• Do not use string indexing, lists, list indexing, or recursion this week.
• Do not hardcode the test cases in your solutions.
• Hint: Look at the test functions in the starter file to get a better idea of what each question is asking.

---

1. longestDigitRun(n)
   Write the function longestDigitRun(n) that takes a possibly-negative int value n and returns the digit that has the longest consecutive run, or the smallest such digit if there is a tie. So, longestDigitRun(117773732) returns 7 (because there is a run of 3 consecutive 7's), as does longestDigitRun(-677886).


2. nthWithProperty309(n)
   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.


3. nthKaprekarNumber(n)
   Note: please do not start this problem or the next problem prior to Friday's recitation. In Friday's recitation, the TA's will discuss these two problems in detail, and you will have some additional time to solve the problem then. If you start the problem before Friday, it will likely take you much longer, and you'll also likely get much less out of Friday's recitation. So: if you want to get a jump on this hw before Friday, please try problems 4-6.
   
   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 nthKaprekarNumber(n) that takes a non-negative int n and returns the nth Kaprekar number, where as usual we start counting at n==0.


4. nearestKaprekarNumber(n)
   Note: as noted above, please do not start this problem prior to completing nthKaprekarNumber in Friday's recitation. Portions of that solution will prove very helpful here.
   
   Bearing in mind the definition of Kaprekar Number from above, 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.


5. nthLeftTruncatablePrime(n)
   Write the function nthLeftTruncatablePrime(n). See here for details. So nthLeftTruncatablePrime(0) returns 2, and nthLeftTruncatablePrime(10) returns 53.


6. nthCarolPrime(n)
   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 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!).


7. Happy Primes
   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 (note that in the hw2.py starter file, instead of assert, these use assertEqual):

      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).


8. nthPowerfulNumber(n)
   Write the function nthPowerfulNumber(n). See here for details. So nthPowerfulNumber(0) returns 1, and nthPowerfulNumber(10) returns 64.


9. nthCircularPrime(n)
   Write the function nthCircularPrime that takes a non-negative int n and returns the nth Circular prime, which is a prime number that does not contain any 0's and such that all the numbers resulting from rotating its digits are also prime. The first Circular primes are 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197... To see why 197 is a Circular prime, note that 197 is prime, as is 971 (rotated left), as is 719 (rotated left again).