CMU 15-112: Fundamentals of Programming and Computer Science
Extra Practice for Unit 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_s21_week2_linter.py to that folder. Note that some of the problems listed below are not included in that starter file.
3. Edit extra_practice2.py
Do not use string indexing, lists, list indexing, or recursion in this unit.
Do not hardcode the test cases in your solutions.

digitCount(n)
Write the function digitCount(n) that takes a possibly-negative int and returns the number of digits in it. So, digitCount(12323) returns 5, digitCount(0) returns 1, and digitCount(-111) returns 3. One way you could do this would be to return len(str(abs(n))), but you cannot do that, since you may not use strings here! This can be solved with logarithms, but seeing as this is the "loops unit", you should instead simply repeatedly remove the ones digit until you cannot.

gcd(m, n)
[Note: to receive any credit, you must solve this problem using Euclid's algorithm, and by no other means. In particular, do not just loop through all integers less than min(m,n) and find the common factors that way -- it is much too slow! Also, do not use math.gcd!]
According to Euclid, the greatest common divisor, or gcd, can be found like so:
   gcd(x,y) == gcd(y, x%y)
We can use that to quickly find gcd's. For example:
    gcd(270,250) == gcd(250, 20) # 270 % 250 == 20
                 == gcd(20, 10) # 250 % 20 == 10
                 == gcd(10, 0) # 20 % 10 == 0
When we get to gcd(x,0), the answer is x. So gcd(270, 250) is 10. With this in mind, write the function gcd(x,y) that takes two positive integers x and y and returns their gcd using Euclid's gcd algorithm.

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

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

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.

integral(f, a, b, N) [10 pts]
Background: in calculus, we use the integral of a function f from x=a to x=b to compute the area under the curve between those points (or the negative area if the function is below the x-axis). One way to approximate this area (that is, to find it without doing any actual calculus!) is by replacing the smooth function with a collection of N trapezoids, as shown in this image:

As in that image, here we will only use uniform widths, so each of the trapezoids has a width of (b - a)/N, so that all N of them together span the width of (b - a).

In any case, the larger N is, the more trapezoids you use, the more accurate your approximation becomes. You can read more here about this so-called trapezoidal rule.

With this in mind, write the function integral(f, a, b, N) that takes a Python function f (that itself takes one value x, a float, and returns a float), and two floats a and b, where a<=b, and a positive int N, and uses the trapezoidal rule with N trapezoids to return the approximate area under the curve of f(x) where a <= x <= b. To be clear, in the case where N=1, this uses just one trapezoid, where the left edge is at (a, f(a)) and the right edge is at (b, f(b)), so the result is (b - a) * (f(a) + f(b))/2 (the width times the average height of the trapezoid).

Hint: you should use almostEqual if you have your own tests or add any to our test function. Also, you'll probably want to use some very simple curves for testing, as we did in the test function, such as f(x)=x, f(x)=2*x+3, and f(x)=2*x**2, and then in ranges (a,b) with values of N such that you can fairly easily compute the expected answer by hand.

Another hint: here is a basic example showing how functions work as parameters to other functions:
```
def f1(x): return x+1
def f2(x): return x+2
def h(f): return f(10)
print(h(f1)) # calls f1(10), prints 11
print(h(f2)) # calls f2(10), prints 12
```

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.

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

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

hasConsecutiveDigits(n)
Write the function hasConsecutiveDigits(n) that takes a possibly- negative int value n and returns True if that number contains two consecutive digits that are the same, and False otherwise.

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

nthAdditivePrime(n)
Write the function nthAdditivePrime(n) that takes a non-negative int n and returns the nth Additive Prime, which is a prime number such that the sum of its digits is also prime. For example, 113 is prime and 1+1+3==5 and 5 is also prime, so 113 is an Additive Prime.

nthPerfectNumber(n)
Write the function nthPerfectNumber(n) that takes a non-negative integer n and returns the nth perfect number, starting at n=0, where a number is perfect if it is the sum of its positive divisors less than itself. For example, 6 is perfect because 6 = 1 + 2 + 3. Also, 28 is perfect because 28 = 1 + 2 + 4 + 7 + 14. The next one is 496, then 8128. For full credit, you need to use a faster version, which uses the same observation that sped up isPrime, so that you only have to search for factors up to the square root of n.

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

isSemiPrime(n)
Write the function isSemiPrime(n) that takes an arbitrary value (perhaps not even an int) and returns True if it is a semi-prime, and False otherwise. You can read about semi-primes here.

Counting Primes
Write the 4 functions describes in the Counting Primes section from here.

And More!
You can find even more loops-and-conditional problems here.

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

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