// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (8 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 113 Solution

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.
download arrowUse this link to get the Project Euler 113 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|51161058134250|

Afterthoughts

Project Euler 113 Solution last updated

Discussion

2 Responses to “Project Euler 113 Solution”

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

    Thanks.

    Posted by David | August 15, 2012, 9:10 AM
    • 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.

      Posted by Mike | August 21, 2012, 2:06 PM

Post a comment