## Project Euler 113: Count how many numbers below a googol (10^{100}) are not "bouncy"

#### Problem Description

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?

#### Analysis

Whenever a problem asks for the number of elements in a set, as does this one, then the solution in typically a counting problem solved with combinometrics, dynamic programming or a generating function.

Our solution uses the general formula that counts the monotonically increasing/decreasing digits ignoring leading zeros.

To remove confusion surrounding the terms *increasing* and *non-decreasing*, Rudin, in his *Principles of Mathematical Analysis* (Def. 3.13), defines a sequence
of real numbers to be:

(a) *monotonically increasing* if
[i.e., non-decreasing].

(b) *monotonically decreasing* if
[i.e., non-increasing].

To avoid ambiguity one can specify that a monotonic sequence is “strictly increasing” or that it is non-decreasing, or non-increasing, or strictly decreasing.

#### Project Euler 113 Solution

Runs < 0.001 seconds in Python 2.7.Use this link to get the Project Euler 113 Solution Python 2.7 source.

#### Afterthoughts

- Function
`binomial`

is listed in Common Functions and Routines for Project Euler - See also, Project Euler 112 Solution:

*Project Euler 113 Solution last updated*

Could you please provide more information about that general formula for counting increasing/decreasing digits? Is there a paper about it?

Thanks.

I’m going to have to revisit this problem. I know it’s an application of the Inclusionâ€“exclusion principle that works for limits of any power of ten. Give me a few days to look at it.