Problem 113: Non-bouncy Numbers

Project Euler Problem 113 Solution

EulerSolve provides an optimized solution for Project Euler Problem 113, Non-bouncy Numbers, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary A positive integer is called increasing if its digits never decrease from left to right, and decreasing if its digits never increase. A number is non-bouncy when it belongs to at least one of those two families. The task is to count all non-bouncy positive integers below $10^{100}$. Direct enumeration is hopeless at this scale, but the implementations show that the problem collapses to pure combinatorics. The answer comes from one count for increasing numbers, one count for decreasing numbers, and one overlap correction. Mathematical Approach Let $N(n)$ denote the number of non-bouncy positive integers below $10^n$. We count the increasing and decreasing families separately, then use inclusion-exclusion to remove the numbers that were counted twice. Two monotone families, but not the same encoding Numbers below $10^n$ have at most $n$ digits. For increasing numbers, padding with leading zeros preserves monotonicity: for example, $134$ becomes $000134$, which is still weakly increasing. For decreasing numbers that trick fails: $66420$ is decreasing, but $066420$ is not. That is why the increasing side is counted in one fixed length $n$, while the decreasing side is counted length by length....

Detailed mathematical approach

Problem Summary

Read the digits of a positive integer from left to right. The number is called increasing if no digit is exceeded by the digit to its left, so that the digits never go down, as in $134468$, and decreasing if no digit is exceeded by the digit to its right, so that the digits never go up, as in $66420$; equal neighbouring digits are allowed in both cases. A positive integer that is neither is called bouncy, for example $155349$, whose digits climb from $1$ to $5$ and then fall to $3$. Bouncy numbers become more and more common: only $12951$ numbers below one million are not bouncy, and only $277032$ below $10^{10}$. We must count the positive integers below a googol, $10^{100}$, that are not bouncy, that is, the increasing or decreasing numbers with at most $100$ digits. ^[1]

The whole solution in one sentence: an increasing or decreasing number is fixed by how often each digit occurs in it, so both families are counted by the "stars and bars" formula for choosing digits with repetition, and the numbers in both, such as $777$, are subtracted once.

Mathematical Approach

We start with small numbers, count by brute force and digit by digit, and then find and prove the formula that the programs evaluate.

1. Small numbers first

A one-digit number has no neighbouring digits to compare, so each of $1,\dots,9$ is both increasing and decreasing. A two-digit number with digits $a$ and $b$ is increasing when $a\le b$ and decreasing when $a\ge b$, and one of the two always holds. A first digit $a$ allows $10-a$ increasing endings and $a+1$ decreasing endings $0,\dots,a$, which gives $9+8+\dots+1=45$ increasing and $2+3+\dots+10=54$ decreasing two-digit numbers. The nine numbers $11,22,\dots,99$ are both, and $45+54-9=90$ is the number of all two-digit numbers. So none of the $99$ numbers below $100$ is bouncy, as the companion Problem 112 also remarks. ^[2]

A bouncy number needs a step up and a step down, hence at least three digits. The smallest is $101$, which goes down from $1$ to $0$ and back up; then come $102,\dots,109$, $120$ and $121$, while $110$ to $119$ are not bouncy. Testing all $900$ three-digit numbers finds $525$ bouncy ones, as Problem 112 says, so $999-525=474$ numbers below $1000$ are not bouncy.

2. The precise question

Write a number with $k$ digits as $d_1d_2\dots d_k$, where $d_1\ne0$. It is increasing exactly when

$$d_1\le d_2\le\dots\le d_k,$$

and decreasing exactly when $d_1\ge d_2\ge\dots\ge d_k$. Mathematicians say non-decreasing and non-increasing; the steps need not be strict. The positive integers below $10^n$ are exactly the numbers with at most $n$ digits; zero is not one of them. Let $N(n)$ be the number of non-bouncy ones among them. The statement gives $N(6)=12951$ and $N(10)=277032$ and asks for $N(100)$; the googol itself has $101$ digits and is not included.

3. First approach: test every number

A program can read the digits of each number $1,2,3,\dots$ with two flags, one for a step up and one for a step down; equal neighbours set neither, and the number is bouncy when both flags are set. Doing this for every number below $10^{10}$ gives $N(1),\dots,N(10)$: $9$, $99$, $474$, $1674$, $4953$, $12951$, $30816$, $67986$, $140906$ and $277032$, where $N(6)$ and $N(10)$ agree with the statement. For a googol this is hopeless: even at a billion tests per second, $10^{100}$ numbers need $10^{91}$ seconds, more than $10^{83}$ years. We have to count the non-bouncy numbers without listing them.

4. Second approach: build the numbers digit by digit

Deleting the last digit of an increasing number leaves an increasing number, and one ending in $e$ can be extended by any digit $d\ge e$; a decreasing one by any $d\le e$. So let $a_k(d)$ and $b_k(d)$ count the increasing and the decreasing $k$-digit numbers with last digit $d$. Then $a_1(d)=b_1(d)=1$ for $d=1,\dots,9$, $a_1(0)=b_1(0)=0$, and for $d=0,1,\dots,9$

$$\begin{aligned}a_{k+1}(d)&=a_k(0)+\dots+a_k(d),\\b_{k+1}(d)&=b_k(d)+\dots+b_k(9).\end{aligned}$$

An increasing number never ends in $0$; for $d=1,\dots,9$ the first rows of $a_k(d)$ are

$k=1$: $1,1,1,1,1,1,1,1,1$, in total $9$;
$k=2$: $1,2,3,4,5,6,7,8,9$, in total $45$;
$k=3$: $1,3,6,10,15,21,28,36,45$, in total $165$;
$k=4$: $1,4,10,20,35,56,84,120,165$, in total $495$.

The rows of $b_k(d)$ add up to $9$, $54$, $219$ and $714$. Adding the two totals and removing the nine numbers of each length with all digits equal, which were counted twice, leaves $9$, $90$, $375$ and $1200$ non-bouncy numbers with $1$ to $4$ digits, for example $165+219-9=375$, and $9+90+375+1200=1674$ as in Section 3.

This is dynamic programming: a large count is assembled from smaller counts, each computed once and stored in a table. ^[3] With running totals a row costs about ten additions per family, so with exact big integers this already solves the problem. The rows are diagonals of Pascal's triangle, such as the triangular numbers $1,3,6,10,\dots$, and explaining this leads to a formula.

5. A monotone number is a bag of digits

Suppose an increasing number contains one $1$, one $3$, two $4$s, one $6$ and one $8$. Then it is $134468$, because an increasing number lists its digits in sorted order; conversely, every choice of how often each digit occurs gives exactly one increasing number. A collection in which repetitions count but the order does not is called a multiset, so the increasing $k$-digit numbers correspond one to one to multisets of $k$ digits. So do the decreasing numbers, which list their digits from the largest down: the multiset $\{6,6,4,2,0\}$ gives $66420$.

The two families differ in the digit $0$. An increasing number never contains it, because its first digit is at least $1$ and no later digit is smaller, so its digits come from $1,\dots,9$. A decreasing number may end in zeros, so its digits come from $0,\dots,9$; only the multiset of $k$ zeros must be excluded, since any other has a largest digit of at least $1$, which comes first.

6. Stars and bars

How many multisets of size $k$ can be formed from $m$ kinds of objects? Take the digits $1,2,3$ and $k=2$: the multisets are $11$, $12$, $13$, $22$, $23$ and $33$. Draw each as $k$ stars for the chosen digits, in sorted order, with a bar wherever we move on to the next kind of digit, so that $m$ kinds need $m-1$ bars. The six multisets become

$\star\star||$, $\star|\star|$, $\star||\star$, $|\star\star|$, $|\star|\star$ and $||\star\star$.

The stars before the first bar are the $1$s, those between the bars the $2$s, and those after the last bar the $3$s. So every row of $k$ stars and $m-1$ bars describes exactly one multiset, and every multiset exactly one row. A row has $k+m-1$ places and is fixed by the choice of the $m-1$ places that hold bars, so the number of multisets is ^[4]

$$\binom{k+m-1}{m-1}=\frac{(k+m-1)!}{(m-1)!\,k!}.$$

Here the binomial coefficient $\binom ab$ is the number of ways to choose $b$ of $a$ objects, and $a!=1\cdot2\cdots a$, with $0!=1$. ^[5] In the example, $\binom42=6$.

7. One length at a time

With $m=9$ kinds of digits, Sections 5 and 6 give $\binom{k+8}{8}$ increasing $k$-digit numbers. With $m=10$ kinds and without the all-zero multiset, they give $\binom{k+9}{9}-1$ decreasing ones. For $k=1,2,3,4$ the first formula gives $9$, $45$, $165$ and $495$, and the second $9$, $54$, $219$ and $714$, exactly the totals of Section 4. This also explains the table: an increasing $k$-digit number that ends in $d$ is a multiset of $k-1$ digits from $1,\dots,d$ followed by $d$, so $a_k(d)=\binom{k+d-2}{d-1}$ for $d\ge1$. Textbooks use the same picture: seven-digit phone numbers with non-increasing digits are counted with $7$ stars and $9$ bars as $\binom{16}{9}=11440$; ^[6] removing $0000000$ leaves the $11439$ decreasing seven-digit numbers.

8. Numbers in both families

A number that is both increasing and decreasing satisfies $d_i\le d_{i+1}$ and $d_i\ge d_{i+1}$ for every $i$, so all its digits are equal. Numbers such as $55$ and $999$ are called repdigits, ^[7] and here the one-digit numbers such as $7$ count as repdigits too. A repdigit is fixed by its length and its digit, which can be any of $1,\dots,9$, so there are exactly $9$ repdigits of each length.

9. Inclusion–exclusion

Let $I(n)$, $D(n)$ and $R(n)$ be the numbers of increasing numbers, decreasing numbers and repdigits below $10^n$. When we add $I(n)$ and $D(n)$, every repdigit is counted twice and every other non-bouncy number once; subtracting $R(n)$ repairs this. This is the inclusion–exclusion principle for two sets, $|A\cup B|=|A|+|B|-|A\cap B|$, ^[8] and Section 1 used it for two digits: $45+54-9=90$. Adding the counts of Sections 7 and 8 over all lengths gives

$$\begin{aligned}N(n)=\sum_{k=1}^{n}\biggl(&\binom{k+8}{8}\\&+\binom{k+9}{9}-10\biggr).\end{aligned}$$

10. All lengths at once: the hockey-stick identity

For $n=3$ the decreasing side needs $\binom99+\binom{10}9+\binom{11}9+\binom{12}9$${}=1+10+55+220$, with $k=0$ included for the moment. Such a sum collapses to one binomial coefficient. Choose $10$ of the numbers $1,2,\dots,13$ and look at the largest chosen one. If it is $10+k$, the other $9$ come from the $9+k$ numbers below it, in $\binom{9+k}{9}$ ways, where $k$ is $0$, $1$, $2$ or $3$. Every choice has exactly one largest number, so the four terms together count all $\binom{13}{10}=286$ choices. The same argument with $r+1$ of the numbers $1,\dots,n+r+1$ proves the hockey-stick identity, named after its shape in Pascal's triangle: ^[9]

$$\sum_{k=0}^{n}\binom{k+r}{r}=\binom{n+r+1}{r+1}.$$

We apply it with $r=8$ and $r=9$ and remove the term $k=0$, which is $1$; for the decreasing numbers we also remove the all-zero multiset of each of the $n$ lengths, so that $D(3)=286-1-3=282$. In general

$$\begin{aligned}I(n)&=\binom{n+9}{9}-1,\\D(n)&=\binom{n+10}{10}-1-n,\end{aligned}$$

and $R(n)=9n$.

11. Padding instead of adding

The same two formulas can be seen without adding up lengths. Pad every number below $10^n$ with zeros in front to $n$ digits, so that $134$ becomes $000134$ for $n=6$. Leading zeros keep an increasing number increasing and can be removed again, so the increasing numbers below $10^n$ match the $\binom{n+9}{9}$ strings of $n$ digits that never go down, except $00\dots0$.

Zeros in front would break a decreasing number, since $066420$ goes up from $0$ to $6$, and zeros at the end would turn both $21$ and $210$ into $210$. Instead we pad in front with a symbol $\square$ that counts as larger than $9$: $66420$ becomes $\square66420$. The decreasing numbers below $10^n$ then match the strings of length $n$ over the eleven symbols $\square,9,\dots,0$ that never go up, except the $n+1$ strings with only zeros after the blanks, such as $\square\square0000$; so $D(n)=\binom{n+10}{10}-(n+1)$ once more.

Reversal, turning $000134$ into $431000$, even matches the increasing numbers below $10^n$ one to one with the decreasing $n$-digit numbers, since a padded increasing number ends in its largest digit, which is not $0$; both counts are $219$ for $n=3$.

12. The closed form and a worked example

Putting the three pieces together, $N(n)=I(n)+D(n)-R(n)$ becomes

$$\begin{aligned}N(n)&=\binom{n+9}{9}+\binom{n+10}{10}\\&\qquad-10n-2.\end{aligned}$$

For $n=3$ the pieces are $I(3)=\binom{12}{9}-1=219$, which is $9+45+165$, then $D(3)=\binom{13}{10}-4=282$, which is $9+54+219$, and $R(3)=27$. So $N(3)=219+282-27=474$, the count found in Section 1, and the values of the statement follow too: for $n=6$, $\binom{15}{9}=5005$ and $\binom{16}{10}=8008$ give $5005+8008-62=12951$, and for $n=10$, $\binom{19}{9}=92378$ and $\binom{20}{10}=184756$ give $92378+184756-102=277032$. The programs evaluate it for $n=100$.

13. How quickly bouncy numbers take over

Since $\binom{n+10}{10}=\frac{(n+1)(n+2)\cdots(n+10)}{10!}$, $N(n)$ is a polynomial in $n$ of degree $10$ with the leading term $n^{10}/10!$, where $10!=3628800$, while there are $10^n-1$ positive integers below $10^n$. So the share of non-bouncy numbers tends to zero: it is about $47\%$ below $10^3$, $1.3\%$ below $10^6$, $0.0028\%$ below $10^{10}$ and $4\cdot10^{-11}\%$ below $10^{20}$. Between powers of ten it can rise again: $9$ of the $109$ numbers below $110$ are bouncy, but only $9$ of the $119$ below $120$. The On-Line Encyclopedia of Integer Sequences lists the bouncy numbers below $10^n$, $0$, $0$, $525$, $8325$, $95046$, $\dots$, with a formula equivalent to ours. ^[10]

14. Variations and pitfalls

The argument works in every base $b\ge2$: increasing numbers use the digits $1,\dots,b-1$, decreasing numbers $0,\dots,b-1$, and there are $b-1$ repdigits of each length, so below $b^n$ there are

$$\binom{n+b-1}{b-1}+\binom{n+b}{b}-bn-2$$

non-bouncy numbers, where $bn+2$ removes the all-zero strings and the repdigits. In base $2$ this is $n(n+1)/2$: the non-bouncy binary numbers are a block of ones followed by a block of zeros, such as $1100$. If neighbouring digits had to differ, multisets would become sets, leaving $\binom9k$ strictly increasing $k$-digit numbers, $2^9-1=511$ in all. For a bound that is not a power of ten, as in Problem 112, the count of Section 4 must also track whether the digits so far still equal those of the bound.

Typical mistakes are counting $0$, padding decreasing numbers with zeros, reading "increasing" as strictly increasing, counting the repdigits twice, which adds $9n$, and using $101$ digits because the googol has $101$ digits.

How the Code Works

The C++ program ^[11] keeps its settings in a structure Options, by default $100$ digits with the checkpoint on. parse_arguments accepts --digits=K, read digit by digit by parse_int_after_prefix, and --skip-checkpoints; an unknown argument or a digit count below $1$ gives exit code $1$.

binom_u128(n, k) uses the multiplicative formula. It returns $0$ for $k$ outside $0,\dots,n$ and $1$ for $k=0$ or $k=n$, replaces $k$ by the smaller of $k$ and $n-k$, which does not change the value, because taking $k$ objects is the same as leaving $n-k$, and runs result = result * (n - k + i) / i for $i=1,\dots,k$. As long as nothing overflows, the division is exact: before step $i$ the variable holds $\binom{j-1}{i-1}$, where $j=n-k+i$, and ^[5]

$$\binom{j-1}{i-1}\,j=i\binom{j}{i},$$

so the product is a multiple of $i$ and the new value is again a binomial coefficient. For $\binom{12}{9}$, where $k$ becomes $3$, the steps give $10$, $55$ and $220$; the order matters, since $55$ is not divisible by $3$, but $55\cdot12=660$ is. solve_u128(digits) computes increasing $=\binom{n+9}{9}-1$, decreasing $=\binom{n+10}{10}-(n+1)$ and flat_overlap $=9n$ as in Section 10 and returns increasing + decreasing - flat_overlap. run_checkpoints compares the decimal text of the result for $6$ digits with the $12951$ of the statement, and main stops with exit code $2$ if they differ. to_string_u128 collects the decimal digits by repeated division by $10$ and reverses them, because the standard output stream cannot print unsigned __int128, a 128-bit type that GCC offers as an extension. ^[12]

For $100$ digits every intermediate value stays below $2^{64}$. For $n\ge10$ the largest one is the last product for $\binom{n+10}{10}$, which equals $10\binom{n+10}{10}$ and stays below $2^{128}$ up to $n=25648$; up to there the program agrees with exact integers. From $25649$ digits on, this product exceeds $2^{128}$ and wraps around, because unsigned arithmetic works modulo $2^{128}$. Nothing checks for this, so up to $238609294$ digits the program prints a wrong count and still ends with exit code $0$. From $238609295$ digits on, even 9 * digits overflows the signed int; signed overflow is undefined behaviour in C++, ^[13] so then nothing at all is guaranteed.

The Python version is one function solve(), called at the end of the file. It fixes n = 100, forms increasing, decreasing and flat_overlap as the C++ code does, with comb from the math module, which returns the exact binomial coefficient ^[14] as a Python integer of unlimited size, and prints increasing + decreasing - flat_overlap. The Java main also fixes n = 100. Its comb(n, k) works with BigInteger, Java's arbitrary-precision integers: it starts from BigInteger.ONE and applies the same multiplicative formula without the symmetry shortcut. main then forms inc and dec, turns the long value 9L*n into the overlap flat, and prints inc.add(dec).subtract(flat). Neither version reads a digit count from the command line or runs a checkpoint.

Complexity and Verification

The closed form needs two binomial coefficients: for $100$ digits the C++ and Java loops take $9+10$ multiplications and exact divisions and a few additions, the C++ checkpoint for $6$ digits adds $6+6$ more, and Python leaves the binomial coefficients to math.comb, whose internal steps differ. Since $\binom{n+10}{10}\lt(n+10)^{10}$, the numbers have $O(\log n)$ bits, so the work is constant when an arithmetic operation counts as one step, and $O\bigl((\log n)^2\bigr)$ bit operations with schoolbook multiplication, while the memory holds a few such numbers, $O(\log n)$ bits. The C++ program keeps them in fixed 128-bit words instead, which is why its results are correct only up to $25648$ digits. The brute force of Section 3 needs about $n\cdot10^n$ digit comparisons and the table of Section 4 about $20n$ additions of big integers.

The C++ program checks $N(6)=12951$ on every run unless --skip-checkpoints is given, and --digits=3 and --digits=10 reproduce $474$ and $277032$. Further checks, outside the published solutions, were run for this article. A brute force over every positive integer below $10^{10}$ reproduces $N(n)$ for every $n\le10$, with exactly $\binom{k+8}{8}$ increasing numbers, $\binom{k+9}{9}-1$ decreasing numbers and $9$ repdigits of each length $k\le10$. The count of Section 4 agrees with the closed form for every $n\le1000$; the hockey-stick identity holds for $r\lt15$ and $n\lt300$; the correspondences of Section 11 hold for $n\le6$; and the base-$b$ formula agrees with a brute force for the bases $2$ to $10$ below $b^n\le2\cdot10^5$ and with the digit-by-digit count for bases up to $16$ and $n\le40$. Run for every digit count up to $25700$, the C++ program agrees with exact integers exactly up to $25648$, and a model of its 128-bit arithmetic is wrong for every count from $25649$ to $10^6$; from $32291$ digits on even the true count needs more than 128 bits, and a build with the undefined-behaviour sanitizer reports the first signed overflow at $238609295$ digits. The three programs print the same number, equal to the closed form evaluated with exact Python integers.

Footnotes and References

The references supply background facts; the counts, the closed form and the 128-bit limits are derived in this article.

Project Euler 113 — Non-bouncy Numbers. The official statement defines increasing, decreasing and bouncy numbers (examples 134468, 66420, 155349), gives 12951 non-bouncy numbers below one million and 277032 below 10^10, and asks how many numbers below a googol are not bouncy.
Project Euler 112 — Bouncy Numbers. With the same definitions it notes that no number below one hundred is bouncy and that 525 numbers below one thousand are, and asks for the least number for which the proportion of bouncy numbers is exactly 99%.
Wikipedia — Dynamic programming. The method breaks a problem into simpler sub-problems, solves each of them only once and stores the solutions in a table.
Wikipedia — Stars and bars (combinatorics). Theorem two: there are C(n + k − 1, k − 1) multisets of size n taken from a set of size k.
NIST DLMF §26.3 — Binomial Coefficients. C(m, n) counts the ways of choosing n of m distinct objects without regard to order; equation 26.3.6 is C(m, n) = (m/n) C(m − 1, n − 1), and 26.3.7 writes C(m + 1, n + 1) as a sum of C(k, n).
O. Levin — Discrete Mathematics: An Open Introduction, Stars and Bars. Example 1.5.2 counts the 7-digit phone numbers with non-increasing digits with 7 stars and 9 bars as C(16, 9).
Wikipedia — Repdigit. A repdigit is a natural number composed of repeated instances of the same digit, such as 11 or 666.
Wikipedia — Inclusion–exclusion principle. For two finite sets, |A ∪ B| = |A| + |B| − |A ∩ B|, because the elements of the intersection are counted twice.
Wikipedia — Hockey-stick identity. For n ≥ r ≥ 0, C(r, r) + C(r + 1, r) + … + C(n, r) = C(n + 1, r + 1), named after its shape in Pascal's triangle; one of its proofs sorts the subsets by their largest element.
OEIS A204692 — Bouncy numbers below 10^n. The sequence starts 0, 0, 525, 8325, 95046, and its formula 10^n − C(n + 10, 10) − C(n + 9, 9) + 10n + 1 equals 10^n − 1 − N(n).
C++ — Euler113.cpp. The linked immutable revision contains binom_u128, solve_u128, to_string_u128 and the 6-digit checkpoint; it is the implementation record for this article.
GCC manual — 128-bit integers. GCC supports __int128 and unsigned __int128 as an extension on targets with an integer mode wide enough to hold 128 bits.
cppreference — Arithmetic operators. Its section on overflows states that unsigned integer arithmetic is always performed modulo 2^n, where n is the number of bits of the type, and that the behaviour is undefined when a signed integer operation overflows.
Python — math.comb. math.comb(n, k) returns the number of ways to choose k of n items without repetition and without order, which is zero for k > n.

Problem 113 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>

namespace {

using u128 = unsigned __int128;

struct Options {
    int digits = 100;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--digits=", options.digits)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.digits >= 1;
}

u128 binom_u128(int n, int k) {
    if (k < 0 || k > n) {
        return 0;
    }
    if (k == 0 || k == n) {
        return 1;
    }
    k = std::min(k, n - k);

    u128 result = 1;
    for (int i = 1; i <= k; ++i) {
        result = result * static_cast<u128>(n - k + i) / static_cast<u128>(i);
    }
    return result;
}

u128 solve_u128(const int digits) {
    const u128 increasing = binom_u128(digits + 9, 9) - 1;
    const u128 decreasing = binom_u128(digits + 10, 10) - (digits + 1);
    const u128 flat_overlap = static_cast<u128>(9 * digits);
    return increasing + decreasing - flat_overlap;
}

std::string to_string_u128(u128 value) {
    if (value == 0) {
        return "0";
    }
    std::string s;
    while (value > 0) {
        const int digit = static_cast<int>(value % 10);
        s.push_back(static_cast<char>('0' + digit));
        value /= 10;
    }
    std::reverse(s.begin(), s.end());
    return s;
}

bool run_checkpoints() {
    if (to_string_u128(solve_u128(6)) != "12951") {
        std::cerr << "Checkpoint failed for digits=6" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << to_string_u128(solve_u128(options.digits)) << '\n';
    return 0;
}

Python

# Problem 113: Non-bouncy numbers below 10^100
# Count = C(n+9,9) - 1 + C(n+10,10) - (n+1) - 9n

from math import comb

def solve():
    n = 100
    increasing = comb(n + 9, 9) - 1
    decreasing = comb(n + 10, 10) - (n + 1)
    flat_overlap = 9 * n
    print(increasing + decreasing - flat_overlap)

solve()

Java

import java.math.BigInteger;

public class Euler113 {
    static BigInteger comb(int n, int k) {
        BigInteger r = BigInteger.ONE;
        for (int i = 1; i <= k; i++) r = r.multiply(BigInteger.valueOf(n-k+i)).divide(BigInteger.valueOf(i));
        return r;
    }
    public static void main(String[] args) {
        int n = 100;
        BigInteger inc = comb(n+9,9).subtract(BigInteger.ONE);
        BigInteger dec = comb(n+10,10).subtract(BigInteger.valueOf(n+1));
        BigInteger flat = BigInteger.valueOf(9L*n);
        System.out.println(inc.add(dec).subtract(flat));
    }
}