CMU 15-112: Fundamentals of Programming and Computer Science
Week2 Practice (Due never)

• These problems will help you prepare for hw2 and for quiz2.
• Starter files: wk2_practice.py and cs112_f16_wk2.py
• Do not use strings, lists, or recursion this week.
• Do not hardcode the test cases in your solutions.

1. mostFrequentDigit(n)
   Write the function mostFrequentDigit(n), that takes a non-negative integer n and returns the digit from 0 to 9 that occurs most frequently in it, with ties going to the smaller digit.


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

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


4. longestIncreasingRun(n)
   Write the function longestIncreasingRun that takes in a positive int value n and returns the longest increasing run of digits. For example longestIncreasingRun(1232) would return 123 and longestIncreasingRun(27648923679) returns 23679. If there is a tie in run length, the larger of the two runs should be returned. So longestIncreasingRun(123345) would return 345.


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


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


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

8. countingPrimes
   Do the "Counting Primes" problem here.


9. hasOnlyOddDigits(n)
   Write the function hasOnlyOddDigits(n) that takes a possibly-negative integer n and returns True if n only has odd digits, and False otherwise (that is, if it has any even digits).


10. isRotation(x, y)
    Write the function isRotation(x, y) that takes two non-negative integers x and y, both guaranteed to not contain any 0's, and returns True if x is a rotation of the digits of y and False otherwise. For example, 3412 is a rotation of 1234. Any number is a rotation of itself.


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


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


13. nthSquareSumOfTwoSquares(n)
    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.


14. latticePointsVisibleFromTheOrigin(n)
    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 n2 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**2. It is amazing how often pi unexpectedly shows up!