Project Euler: #112-113, Bouncy numbers

Problem 112:

If no digit in a number is exceeded by the digit to its left it’s called an increasing number – e.g. 134,468. Similarly if no digit is exceeded by the digit to its right it’s called a decreasing number – e.g. 66,420. We’ll call a positive integer that is neither increasing nor decreasing a “bouncy” number – e.g. 155,349.

Clearly there cannot be any bouncy numbers below 100. In fact, the least number for which the proportion of bouncy numbers reaches 50% is 538. By the time we reach 21,780 the proportion of bouncy numbers is 90%.

Find the least number for which the proportion of bouncy numbers is exactly 99%.

Solution to 112:

This seems easy enough to brute-force, so I tried that in Python:

# Parse the number right-to-left to find if it's bouncy.
def is_bouncy(num):
    has_incr_seq, has_decr_seq = False, False
    right_digit = num % 10
    num = num // 10

    while num > 0:
        left_digit = num % 10
        if left_digit < right_digit:
            has_incr_seq = True
        elif left_digit > right_digit:
            has_decr_seq = True
        right_digit = left_digit
        num = num // 10
        if has_incr_seq and has_decr_seq:
            return True
    return False

# Iterate through numbers until the bouncy count is 99%
# of the total count.
count = 0
i = 99
while count < 0.99 * i:
    i = i + 1
    if is_bouncy(i):
        count = count + 1
print(i)

This gives us the answer: 1,587,000. (Python took 2.8 s to run this on a MacBook Air; out of curiosity I tried it in C — 42 ms.)

Next, problem 113:

As n increases, the proportion of bouncy numbers below n increases such that there are only 12,951 numbers below 1,000,000 that are not bouncy and only 277,032 non-bouncy numbers below 10¹⁰.

How many numbers below a googol (10¹⁰⁰) are not bouncy?

Solution to 113:

Let’s start with a simple question and expand from there – how many increasing numbers are there below 1000?

Well, there are 3 digits in any number below 1000 (if we consider e.g. 012 to be 12), and for a number to be increasing each digit must be no lower than the digit to its left. Let’s label the digits in a 3-digit number A, B, and C. The leftmost digit A can be any of the digits 0-9; the middle digit B can be any of the digits from A-9; and the rightmost digit C can be any of the digits from B-9. That means that there are 12 potential digits to choose the 3 digits of our number from – the 10 digits 0-9, plus 2 potential duplicates if A = B or B = C.

The number of increasing numbers below 1000, then, is just (12 choose 3) = 220, minus 1 because we don’t want to count 000. Likewise, the number of increasing numbers below a googol is

$$ {109 \choose 100} - 1 \tag{increasing} $$

Decreasing numbers are similar, except that we can’t just ignore leading zeroes as we’d done with increasing numbers – for example, 072 is in fact a decreasing number, but wouldn’t be caught by the (12 choose 3) we used earlier. So, how many decreasing numbers are there below 1000?

If we label the digits in a 3-digit decreasing number D, E, and F, then the leftmost digit D can be any of the digits 0-9; the middle digit E can be any of the digits 0-D, or, if D = 0, any of the digits 0-9; and the rightmost digit F can be any of the digits 0-E, or, if D = E = 0, any of the digits 0-9. That means that there are 13 potential digits to choose the 3 digits of our number from – the 10 digits 0-9, plus 2 potential duplicates if D = E or E = F, plus 1 for potential leading zero(es).

The number of decreasing numbers below 1000, then, is (13 choose 3) = 286, minus 4 because 000 will occur 4 times (one time as before, plus once for each digit). Analogously, the number of decreasing numbers below a googol is

$$ {110 \choose 100} - 101 \tag{decreasing} $$

Almost there! In order to find all the non-bouncy numbers, we just need to add the increasing numbers to the decreasing numbers. However, some numbers are increasing and decreasing – e.g. 888. How many of these monotonic numbers are there? Well, for each power of 10 there are 9 potential monotonic numbers – e.g. we have 1, 2, ..., 9, 11, 22, ..., 99, 111, 222, ..., 999, etc. Since we have 100 digits, we have:

$$ 9 \times 100 \tag{duplicates} $$

Thus, the total number of non-bouncy numbers below a googol should be:

$$ \left({109 \choose 100} - 1\right) + \left({110 \choose 100} - 101\right) - (9 \times 100) \tag{total} $$

This gives us a final solution of 51,161,058,134,250.