CMU 15-112: Fundamentals of Programming and Computer Science
Homework 2 (Due Saturday 7/10 at 5pm ET (Pittsburgh-time))

  1. isPalindromicNumber(n) [10 pts]
    Write the function isPalindromicNumber(n) that takes a non-negative int n and returns True if that number is palindromic and False otherwise, where a palindromic number is the same forwards as backwards. For example, these numbers are palindromic: 0, 1, 99, 12321, 123321, and these numbers are not: 1211, 112, 10010.

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

  3. hasConsecutiveDigits(n) [25 pts]
    Write the function hasConsecutiveDigits(n) that takes a possibly-negative int n and returns True if somewhere in n some digit occurs consecutively (so the same digit occurs twice in a row), and False otherwise. For example, these numbers have consecutive digits: 11, -543661, 1200, -1200, and these numbers do not: 1, 123, 12321, -12321.

  4. carrylessAdd(x, y) [25 pts]
    First, you may wish to read the first page (page 44) from here about Carryless Arithmetic. Or, just understand that carryless addition is what it sounds like -- regular addition, only with the carry from each column ignored. So, for example, if we carryless-ly add 8+7, we get 5 (ignore the carry). And if we add 18+27, we get 35 (still ignore the carry). With this in mind, write the function carrylessAdd(x, y) that takes two non-negative integers x and y and returns their carryless sum. As the paper demonstrates, carrylessAdd(785, 376) returns 51.

  5. longestDigitRun(n) [25 pts]
    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).

Bonus Problems
Bonus problems are entirely optional and worth few points. Do them for the fun and the learning.

  1. bonus: nthSmithNumber(n) [2 pt]
    Please be aware that we usually do not offer extensive help on most bonus problems, but we'll offer some help on this one if you get stuck. It's a good practice problem, so we're hoping you'll try it.
    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.

    To continue, 27 = 3**3, the sum of the digits is 2+7=9, and the sum of the prime factors is 3+3+3=9, so 27 is a Smith Number. However, 144=2**4 + 3**2, the sum of the digits is 1+4+4=9, and the sum of the prime factors is 2+2+2+2+3+3=14, so 144 is not a Smith Number.

  2. bonus: Integer Data Structures [up to 4 pts]
    Note: We will not provide debugging help or hints on this problem! You must rely on your own problem-solving and debugging skills. That being said, we have offered rather detailed guidance here. You should only do this if you find it interesting and fun, because it's really not worth spending many hours on this purely for 4 points. That being said, we hope you enjoy it!

>>( o u o )<<