Project Euler 113: How many numbers below a googol (10^100) are not “bouncy”?

In Problem 112 of Project Euler we got an introduction to bouncy numbers. In Problem 113 we will revisit this concept and solve the problem

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?

Many have written that this problem can be solved using lattice paths. However, if you have no real clue what a lattice is, this doesn’t really help you to fully understand the problem . I had an idea that was the right path and fiddled with the problem until I got the right answer. Later on I have found a much better explanation for why the combinatorics solution is correct.

Increasing numbers

We can represent any increasing number via binary strings, in that case 001101001 will represent 2235. Something which is not really clear without an explanation. However, we have a counter k, which starts at 0. For every 0 we meet in the string we increase k by one, and for every 1 we meet in the string we print the value of k.  Thus we get this number.

Using this method we can represent all 3 digit increasing numbers  made up of the digits 0,1, and 2 with strings of length 5:

11100 = 000
11010 = 001
11001 = 002
10110 = 011
10101 = 012
10011 = 022
01110 = 111
01101 = 112
01011 = 122
00111 = 222

Which means that there are

of these numbers. The reason for substracting 1 is that we don’t want to count the number “000” as a number.

In the same way all 3-digit increasing numbers with the digits 0-9 requires a string containing 3 ones and 9 zeroes and so on.

We want to find all the increasing numbers below which gives us

which is a rather large number

Decreasing numbers

This is rather similar to the increasing numbers. The only difference is that we can have a zero in the front of the string and in the end of the string.

However, there is a small catch as you can see from the number. Before the first 1 we have zeros and after the third one we will have zeros again, that gives us the following patterns

111000 = 000
110100 = 002
110010 = 001
110001 = 000 *
101100 = 022
101010 = 021
101001 = 020
100110 = 011
100101 = 010
100011 = 000 *
011100 = 222
011010 = 221
011001 = 220
010110 = 211
010101 = 210
010011 = 200
001110 = 111
001101 = 110
001011 = 100
000111 = 000 *

The * marks a pattern which is repeated. You can see for 3 digit numbers that 000 will be repeated 3 times + the one time we want to discount it already. For an n-digit number the pattern repeats n times.

Which gives us

different decreasing numbers. The

Removing the doubles

So far we have counted all the increasing number and all the decreasing numbers. However, numbers like 222 and 11 have both properties, which means that we have counted them twice and thus need to remove them from the counting. So let us figure out how many there are in total

if we look at 1-digit numbers there are 1-9, and then 11, 22 and so on. Meaning there are 9*100 of these numbers which are counted twice.

Summing it up

We now have the parts and all we need to do is to sum them up. This gives us a total of

for n-digit numbers. This fits with the numbers given in the problem description and also produces the correct result for the problem given.

Given that we have a method for doing binomial on BigInteger numbers the implementation is trivially reduced to

BigInteger result = Choose(100 + 10, 10) + Choose(100 +9, 9) - 10 * 100 - 2;

You can of course see the complete source code here. It runs in less than 1ms and produces the result

There are 51161058134250 non-bouncy numbers below 10^100

The blog image today is take by Joe Dunckley and kindly shared under the creative commons license.

Posted by Kristian

5 comments

Here is another implementation I will NOT tell anythink about my algo, cuz I cannot remember what it does and I am too lazy to think about it 🙂

#include <iostream>
#include <ctime>

using namespace std;


const int DIGITS = 100;
const int TEN=10;
typedef unsigned long long Long;
Long sums[10];


int main()
{


    time_t start = clock();
    Long bouncy = 9;
    Long temp_sum;
    Long holder;
    int i;

    for(i = 0; i<TEN; i++)
        sums[i] = i+1;

    for(int j = 1; j<DIGITS; j++) // the loop for digits
    {

        temp_sum = 0;
        for(int i = 0; i<TEN; i++)
            temp_sum += sums[i];

        bouncy += 2*temp_sum - sums[9]-10;

        for(i = TEN - 1; i>=0; i--)
        {
            holder = sums[i];
            sums[i] = temp_sum;
            temp_sum -= holder;
        }
     
    }

     cout<<"Project Euler 113:\t"<<bouncy<<endl;
     cout<<"Program last:\t"<<(clock() - start)<<endl;
     
}

Thank you very much for explaining this, but I think you have an error in your math (or at least your description of it). Fortunately, this error just so happens to produce the same (correct) result. Please allow me to explain what I mean.

Ignoring for now the required subtractions, your first example posits that 5C3 (5-choose-3) combinations are required for a 3-digit value that uses the digits 0 to 2. You then state that using all 10 digits would require 12 bits (3 ‘1’s and 9 ‘0’s).

Now, I know there are 220 3-digit increasing numbers using all ten decimal digits, so this implies that the formula should be (# of bits)C(# of digits), because 220 = 12C3.

Further thought leads us to the conclusion that (# of bits) = (# of prints) + (# of increments), where (# of prints) = (# of digits) and (# of increments) = (max digit value) – (min digit value). Therefore, for a googol, the required number of bits should be 100 + (9 – 0) = 109. This agrees with your statement.

The number of digits in a googol, however, is 100. Therefore, the equation to calculate the number of increasing values (again, ignoring the subtraction) should be 100, not 9 as you indicate.

Your formula gets the correct answer because nCr = nC(n-r), and 109 – 100 = 9.

I was banging my head on the wall for hours trying to figure out where that 9 (and for decreasing, 10) came from and why it worked, when it clearly (to me) should have been 100 (for both).

Once again thank you for providing this explanation and all the others, and please excuse my lack of mathematical formatting in this comment as I don’t know how to do it.

I did not understand the numbers for decreasing series. Looks like they are messed up. for example,
110100 should be 001 because we have two 1’s so we get two 0’s, then we have a zero so k becomes 1, and then we have a 1 so we print 1. so it becomes 001. but you have given 002.
similarly for 101100-> first we have 1, so print 0. then a zero so k=1. then a 1 so print 1. then a 1 so print 1. Then we have two zero. So result is 011 but you have given 022.

Am I going wrong somewhere?

Antonio Sanchez

Shouldn’t there be the same number of non-increasing numbers with “d” digits as non-decreasing? Take a non-increasing number. Reverse all the digits. Now you have a non-decreasing number.

Carl J Appellof

I thought there would be a combinatoric solution to this problem, but I could not figure it out. Instead, I wrote a program to calculate the number of non-bouncy numbers for a given number of digits. I ran it for 1-12 digits and collected results. The calculation got very slow after about 20 digits, so I moved on. Using finite differences, I discovered the numbers could be represented by a 10th order polynomial. This led me to Wikipedia articles on Newton interpolation, and I expanded my program to calculate coefficients for this polynomial, followed by a function to evaluate the polynomial for an input value of 100. Using the C++ “double” datatype proved to have bad roundoff errors for this scale of calculation, so I implemented a fraction class using the “long long” (64-bit) data type. Then had to be careful about the order of evaluation to avoid overflow, since I was trying to avoid using a BigInteger class, which is not native to C++. Finally, everything worked, got the same answer as you, and took 1.7 ms on my computer.

Leave a Reply