     (9 votes, average: 5.00 out of 5) Loading...

## Project Euler 113 Solution ## Project Euler 113: Count how many numbers below a googol (10100) 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 1010.

How many numbers below a googol (10100) 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 $\{s_n\}$ of real numbers to be:

(a) monotonically increasing if $s_n \leq s_{n+1}, (n = 1, 2, 3, \cdots)$ [i.e., non-decreasing].

(b) monotonically decreasing if $s_n \geq s_{n+1}, (n = 1, 2, 3, \cdots)$ [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

Project Euler 113 Solution last updated

## Discussion

### 2 Responses to “Project Euler 113 Solution”

1. • 