Homework 2

Due Sunday 27-Jan, at 8pm



  1. Piazza Post [5 pts]
    To succeed in 15-112, you'll need to understand how to use the course resources. Towards that end, by 12:00pm Sunday 27-Jan, you must ask a question on Piazza about the homework or coding in general. This has to be a real question! We will check for this after Sunday and will add points on Autolab manually at that point. If you have already asked a question on Piazza, we will count that question for credit (though you're still encouraged to ask more questions!).

  2. COLLABORATIVE: numberLength [10 pts]
    NOTE: This problem is collaborative. That means you can work on it with other students! However, you must follow the collaboration rules as specified by the syllabus, and you must list all of your collaborators' andrewIDs in a comment above your solution.

    Write the function numberLength(x) that takes a non-negative integer x and returns the number of digits in x. For example, numberLength(12) would return 2.
    Note: This function may be useful in other problems in this assignment...

  3. COLLABORATIVE: countMatchingDigits [10 pts]
    NOTE: This problem is collaborative. That means you can work on it with other students! However, you must follow the collaboration rules as specified by the syllabus, and you must list all of your collaborators' andrewIDs in a comment above your solution.

    Write the function countMatchingDigits(x, y) that takes two non-negative integers, x and y, and counts the number of digits that match between the two integers. For examples, the pair (1234, 2071) has two matches, 1 with 1 and 2 with 2. The pair (2203, 1527) also has two matches, since each of the 2s from the first number match with the 2 from the second.

    Hint: In this and in future problems, you'll need to get individual digits from numbers. If you want, you can reuse your solutions to getKthDigit from lab1 and numberLength to do this.

  4. COLLABORATIVE: nthCircularPrime [15 pts]
    NOTE: This problem is collaborative. That means you can work on it with other students! However, you must follow the collaboration rules as specified by the syllabus, and you must list all of your collaborators' andrewIDs in a comment above your solution.

    A circular prime is a number with the property that any rotation of that number's digits is prime. In this case, rotation refers to cycling the digits of a number; for example, the rotations of 1234 are 1234, 2341, 3412, and 4123. You can read more about this on the Wikipedia page. Single-digit primes are all circular, of course. To find the nth circular prime, you'll need to write isPrime and three other functions:

    1. rotateNumber [5 pts]
      This function takes a number, x, and rotates that number's digits by one place. This would turn the number 1234 to 4123.

    2. isCircularPrime [5 pts]
      This function takes a number, x, and determines whether that number is a circular prime. To do this, you'll need to check whether every rotation of the number is prime.

    3. nthCircularPrime [5 pts]
      This function takes a number, n, and returns the nth circular prime.


  5. Debugging: countEvenDigits(n) [5 pts]
    The following program has one error (or bug) in it somewhere. Your task is to find and fix that bug without substantially rewriting the program. Specifically, each bug can be fixed by modifying only one of the program lines (which will result in full credit). We define 'modify' to mean either changing one line, adding one line, or deleting one line.

    This program is supposed to count the number of even digits that appear in the parameter n. Remember, 0 is even!
    def countEvenDigits(n): if n < 0: return countEvenDigits(-n) elif n == 0: return 1 count = 0 while n > 0: digit = n % 10 if digit % 2 == 0 count += 1 n = n // 10 return count

  6. Debugging: factorial(n) [5 pts]
    The following program has one error (or bug) in it somewhere. Your task is to find and fix that bug without substantially rewriting the program. Specifically, each bug can be fixed by modifying only one of the program lines (which will result in full credit). We define 'modify' to mean either changing one line, adding one line, or deleting one line.

    This program is supposed to return n!, i.e. n-factorial, which is defined for all non-negative integers. For example, 3!=3*2*1=6, 4!=4*3*2*1=24, and 5!=5*4*3*2*1=120. (Note that 0 is a special case, and 0!=1.)
    #Assume n>=0 def factorial(n): if n==0: return 1 result=n for smallerInteger in range(n): result=result*smallerInteger return result

  7. Debugging: intHasRepeatedDigits(n) [5 pts]
    The following program has one error (or bug) in it somewhere. Your task is to find and fix that bug without substantially rewriting the program. Specifically, each bug can be fixed by modifying only one of the program lines (which will result in full credit). We define 'modify' to mean either changing one line, adding one line, or deleting one line.

    This program is supposed to take any integer, positive or negative, and return True if the number has at least one pair of sequentially repeating digits (e.g. 55, 1223, 844, -993) and False otherwise (e.g. 5, 1234, 841, -903), accompanied by an appropriate print() message.
    def intHasRepeatedDigits(n): if n>0: remainingDigits=n else: n=-n while remainingDigits//10>0: firstDigit=remainingDigits%10 tensDigit=(remainingDigits//10)%10 if firstDigit==tensDigit: print(n,"has repeated digits!") return True remainingDigits=remainingDigits//10 print(n,"has no repeated digits...") return False

  8. containsOddDigits [10 pts]
    Write the function containsOddDigits(x) that takes an integer, x, and returns True if it contains any odd digits, and False otherwise.
    Hint: In this and in future problems, you'll need to get individual digits from numbers. You may want to reuse your solution to getKthDigit and numberLength to do this.

  9. countMultiplesOfSeven [10 pts]
    Write the function countMultiplesOfSeven(a, b) that takes two integers, a and b, and returns the number of multiples of seven that occur between a and b (including a and b). For example, countMultiplesOfSeven(4, 16) would return 2, since two multiples of 7 (7 and 14) occur within that range.

  10. printNumberTriangle [10 pts]
    Time for something a little different! Instead of returning a value, in this function you'll be printing out results. Write the function printNumberTriangle that takes one integer, n, and prints out a number triangle based on n. For example, given the number 4, this function would print out
    1
    21
    321
    4321

    Note: the autograder for this problem is very finicky about whitespace; it expects no spaces, and only one newline after each number line. Make sure your output matches what it expects!

  11. nthHappyPrime [15 pts]
    Write the function nthHappyPrime(n) that, of course, finds the nth happy prime. Prime we know already, but what is a happy number? To find out, read the first paragraph on the Wikipedia page. For our purposes, we can simplify the process of finding a happy number by saying that a cycle which reaches 1 indicates a happy number, while a cycle which reaches 4 indicates a number that is unhappy. To solve this problem, you'll want to use isPrime and write three other functions:

    1. sumOfSquaresOfDigits [5 pts]
      Write the function sumOfSquaresOfDigits(n) which takes a non-negative integer and returns the sum of the squares of its digits. For example, 123 would become 1^2 + 2^2 + 3^2 = 1 + 4 + 9 = 14.

    2. isHappyNumber [5 pts]
      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.

    3. nthHappyPrime [5 pts]
      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).