Counting Bouncy Numbers: Project Euler #113

Question

Problem statement:

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349.

As n increases, the proportion of bouncy numbers below n increases such that there are only 12951 numbers below one-million that are not bouncy and only 277032 non-bouncy numbers below \$10^{10}\$.

How many numbers below a googol (\$10^{100}\$) are not bouncy?

Code:

import time
from scipy import special


def count_non_bouncy_numbers(n):
    '''n - number of digits'''
    include_zeroes = scipy.special.comb(10,n,exact=True,repetition=True) - 1 
    exclude_zeroes = scipy.special.comb(9,n,exact=True,repetition=True)
    only_zeroes = include_zeroes - exclude_zeroes
    total = only_zeroes + exclude_zeroes*2 - 9 
    return total

if __name__ == '__main__':
    total = 0
    for n in range(1,101) : total+= count_non_bouncy_numbers(n)
    print(total)

---

The reasoning behind the code:

The formula I should note here is the combinations with replacement, which is \$ {\frac{(q+r-1)!}{r!(q-1)!} }\$. I will denote it as \$C(q,r)\$ where \$q\$ represents number of items that can be selected and \$r\$ numbers of items that are selected.

My function takes an argument \$n\$, which represents number of digits, e.g:

If \$n = 2\$, then we consider all the numbers in range [10,99]

If \$n = 3 \$, then we consider all the numbers in range [100,999]

Step 1. We find all the non-bouncy numbers that contain zeroes. Specifically, for all numbers with \$n\$ digits, there will be \$C(10,n) - C(9,n)\$ non-bouncy numbers that contain zeroes in them

Step 2. We find number of strictly increasing non-bouncy numbers with \$n\$ digits, there are \$C(9,n)\$ of them.

Step 3. We find number of strictly decreasing non-bouncy numbers with \$n\$ digits. Since decreasing numbers are just increasing numbers in reverse, we can see that there are \$C(9,n)\$ of them.

Step 4. We note that numbers such as 111, 33, 555 etc can be considered as strictly decreasing/increasing at the same time, hence we need to remove the overcount. To do so, we subtract \$9\$.

Step 5. Add up the results, i.e: \$C(10,n) - C(9,n) + C(9,n) - C(9,n) - 9\$ , which represents total number of non-bouncy numbers with \$n\$ digits.

---

What can be improved?

Answer 1

Project Euler problems generally can be computed with a calculator or manually.
So, take a different approach:

1. For ascending numbers, choose the transitions (digits 0-9; 9 transitions).

2. For descending numbers, choose the transitions (initial zeros, digits 9-0; 10 transitions).

3. Subtract those where initial zeros are followed only by a non-empty string of a single repeated digit (0-9) (1 transition, but the last place cannot be chosen).

4. Subtract the case of only the initial zeros.

In the end you have to calculate:

$$\binom{100+9}{9} + \binom{100 + 10}{10} - 10 * \binom{100}{1} - 1 = \binom{109}{9} + \binom{110}{10} - 1001$$