# Counting Bouncy Numbers: Project Euler #113

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

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?

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$$

• Wow, that's neat! – Ilya Stokolos Sep 6 '19 at 19:15