CMU 15-112: Fundamentals of Programming and Computer Science
Loops Extra Practice Problems (Optional)

You may not use strings or lists in these problems.

  • 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. You may assume that the helper function isPrime has already been written and is available for you to use. (Do not write isPrime, just pretend it already exists.)

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

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

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

  • nthTwoFactorish(n)
    We will say an integer is two-factorish if it has at least two digits and each consecutive digit is obtained by multiplying or dividing the previous digit by 2 (and the result is still a single digit). For example: 12 (1→2), 21 (2→1), 24 (2→4), 42 (4→2), 36 (3→6), 63 (6→3). Write the function nthTwoFactorish(n) that takes a non-negative integer n and returns the nth two-factorish number (so nthTwoFactorish(0) == 12).

  • ascendingDigits(n)
    Write the function ascendingDigits(n) which, given an integer n, returns an integer that contains only the digits of n that ascend from right to left.
    For example, consider n = 643512. Scanning the number from right to left:
    • The right-most digit is 2.
    • The next digit that is larger than 2 is 5.
    • The next digit that is larger than 5 is 6.
    So the final answer is 652.
    Consider the following additional test cases:
    assert ascendingDigits(64354512) == 652
    assert ascendingDigits(4239758345613) == 98653
    assert ascendingDigits(759) == 9
    assert ascendingDigits(0) == 0
    assert ascendingDigits(-26434512) == -652

  • countNarrowNumbers(a, b)
    A narrow number is an integer whose digit sum is equal to its length (without leading zeros). For example, 1 is a narrow number because its length equals 1 and its digit sum also equals 1. 12 is not a narrow number because its digit sum is 3, not equal to its length of 2. 20 is a narrow number because both its length and digit sum equal 2.
    Write the function countNarrowNumbers(a, b) that takes two positive integers a and b and returns the number of narrow numbers that exist between a and b (inclusive).
    Note: You may not use strings in this problem! A solution that uses strings will receive 0 points.
    Here are some examples:
    countNarrowNumbers(1, 20) == 3 # 1, 11, 20
    countNarrowNumbers(1, 50) == 3 # 1, 11, 20
    countNarrowNumbers(1, 300) == 9 # 1, 11, 20, 102, 111, 120, 201, 210, 300
    countNarrowNumbers(100, 150) == 3 # 102, 111, 120