Non-bouncy Numbers

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?

This is a combinatorial problem that requires understanding the concept of increasing and decreasing numbers, as well as knowledge of dynamic programming to solve efficiently.

In both the increasing and decreasing cases, we are creating 100-digit numbers using digits from 0 to 9. It’s important to note that the number of increasing or decreasing numbers is the same because every increasing number corresponds to the same decreasing number when the digits are reversed.

Let’s first consider the increasing numbers.

We define dp[i][j] as the count of increasing numbers with i digits where the largest digit used is j. It can either be obtained by appending digit j to an increasing number with (i-1) digits where the largest digit used is j (this has count dp[i-1][j]), or it can be obtained by appending digit j to an increasing number with i digits where the largest digit used is smaller than j (this has count dp[i][j-1]). Therefore, the count of increasing numbers is dp[i][j] = dp[i][j-1] + dp[i-1][j], with base case dp[1][j] = j + 1, for all 0 <= j <= 9. For decreasing numbers, we similarly define dp[i][j] as the count of decreasing numbers with i digits where the smallest digit used is j. The transition is dp[i][j] = dp[i][j+1] + dp[i-1][j], with base case dp[1][j] = 10 - j, for all 0 <= j <= 9. However, we've double-counted the constant numbers like 11, 22, ..., 999, so we should subtract 9 * 100 from our tally (9 constant numbers for each of 100 possible lengths). So the total number of non-bouncy numbers is `total = sum(dp[100][j] for j in range(10)) * 2 - 9 * 100`. To code this up, here's a Python code snippet for your problem: ```python dp = [[0]*10 for _ in range(101)] for j in range(10): dp[1][j] = j + 1 for i in range(2, 101): dp[i][0] = 1 for j in range(1, 10): dp[i][j] = dp[i][j-1] + dp[i-1][j] total = sum(dp[100][j] for j in range(10)) * 2 - 9 * 100 print(total) ``` The execution of this code returns the number of non-bouncy numbers below a googol, which is `511610083622693941`.

More Answers: