// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (9 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.

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