4
\$\begingroup\$

Problem statement:

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^{10}\$.

How many numbers below a googol (\$10^{100}\$) are not bouncy?

Code:

import time
from scipy import special


def count_non_bouncy_numbers(n):
    '''n - number of digits'''
    include_zeroes = scipy.special.comb(10,n,exact=True,repetition=True) - 1 
    exclude_zeroes = scipy.special.comb(9,n,exact=True,repetition=True)
    only_zeroes = include_zeroes - exclude_zeroes
    total = only_zeroes + exclude_zeroes*2 - 9 
    return total

if __name__ == '__main__':
    total = 0
    for n in range(1,101) : total+= count_non_bouncy_numbers(n)
    print(total)

The reasoning behind the code:

The formula I should note here is the combinations with replacement, which is \$ {\frac{(q+r-1)!}{r!(q-1)!} }\$. I will denote it as \$C(q,r)\$ where \$q\$ represents number of items that can be selected and \$r\$ numbers of items that are selected.

My function takes an argument \$n\$, which represents number of digits, e.g:

If \$n = 2\$, then we consider all the numbers in range [10,99]

If \$n = 3 \$, then we consider all the numbers in range [100,999]

Step 1. We find all the non-bouncy numbers that contain zeroes. Specifically, for all numbers with \$n\$ digits, there will be \$C(10,n) - C(9,n)\$ non-bouncy numbers that contain zeroes in them

Step 2. We find number of strictly increasing non-bouncy numbers with \$n\$ digits, there are \$C(9,n)\$ of them.

Step 3. We find number of strictly decreasing non-bouncy numbers with \$n\$ digits. Since decreasing numbers are just increasing numbers in reverse, we can see that there are \$C(9,n)\$ of them.

Step 4. We note that numbers such as 111, 33, 555 etc can be considered as strictly decreasing/increasing at the same time, hence we need to remove the overcount. To do so, we subtract \$9\$.

Step 5. Add up the results, i.e: \$C(10,n) - C(9,n) + C(9,n) - C(9,n) - 9\$ , which represents total number of non-bouncy numbers with \$n\$ digits.


What can be improved?

\$\endgroup\$
4
\$\begingroup\$

Project Euler problems generally can be computed with a calculator or manually.
So, take a different approach:

  1. For ascending numbers, choose the transitions (digits 0-9; 9 transitions).

  2. For descending numbers, choose the transitions (initial zeros, digits 9-0; 10 transitions).

  3. Subtract those where initial zeros are followed only by a non-empty string of a single repeated digit (0-9) (1 transition, but the last place cannot be chosen).

  4. Subtract the case of only the initial zeros.

In the end you have to calculate:

$$\binom{100+9}{9} + \binom{100 + 10}{10} - 10 * \binom{100}{1} - 1 = \binom{109}{9} + \binom{110}{10} - 1001$$

\$\endgroup\$
  • \$\begingroup\$ Wow, that's neat! \$\endgroup\$ – Nelver Sep 6 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.