Project Euler Problem #113

Problem #113 concerns numbers whose digits are neither increasing nor decreasing. The question reads:

Project Euler Problem 113: Non-bouncy numbers
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?

This problem can be solved very efficiently with some mathematical knowledge. Here’s my solution:

Solution #1: Combinatorial Approach

We proceed by counting the number of increasing numbers below a googol and the number of decreasing numbers below a googol and finding the sum of these results. To form an increasing number below a googol, it suffices to arrange 100 arbitrary digits in increasing order. The distinguishing factor between the increasing numbers is the number of each digit 0, 1, 2, …, 9 within the increasing number. The number of choices for each digit can be found with Stars and Bars: the number of distinct ordered sums with k elements and a total of n is equal to (n+k-1) choose (k-1). Thus, the number of increasing numbers is 109 choose 9. This includes the case where all digits are 0, so 1 must be subtracted. Similarly, to generate a decreasing number below a googol, it suffices to arrange 100 arbitrary digits in decreasing order. However, in this case, some of the digits can be leading zeros, so there are 11 choices for each digit. Thus, the number of decreasing numbers is 110 choose 10. Once again, this includes the case where all digits are 0 so 1 must be subtracted. Thus, the running total is (109 choose 9) + (110 choose 10) – 2. However, this total double counts numbers of the form xxx…xxx with an arbitrary number of equal digits, and it includes numbers which only contain leading zeros and ending zeros. Thus, 100*2 = 200 must be subtracted from the total. Thus, the answer is (109 choose 9) + (110 choose 10) – 202. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Combinatorial Approach to Project Euler Problem #113
 '''
 
 import time
 
 def nChooseR(n,r):
     value = 1
     for x in range(r):
         value*=(n-x)
         value/=(x+1)
     return value
 
 def projectEulerProblemOneHundredThirteen(n):
     increasing = nChooseR(n+9,9)-1
     decreasing = nChooseR(n+10,10)-1
     return increasing+decreasing-10*n
 
 start = time.time()
 print projectEulerProblemOneHundredThirteen(100)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 51161058134250
 --- 1.4066696167e-05 seconds ---
 
 for input of n = 100.
 ''' 

And with that, we’re done. This approach finishes the problem in under a millisecond, so it is more than efficient enough for our purposes. This is a great example of the power of discrete math.

Thanks for reading! See you tomorrow.