Project Euler 113: Count how many numbers below a googol (10¹⁰⁰) 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¹⁰.

How many numbers below a googol (10¹⁰⁰) 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

Afterthoughts

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