Problem 156: Counting Digits

Project Euler Problem 156 Solution

EulerSolve provides an optimized solution for Project Euler Problem 156, Counting Digits, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary For a fixed digit $d\in\{1,\dots,9\}$, let $f_d(n)$ denote the total number of times $d$ appears in the decimal expansions of all integers from $0$ through $n$. The task is to find every integer $x$ satisfying $$f_d(x)=x,$$ then sum all such $x$ over $d=1,\dots,9$. The point $x=0$ is trivially a fixed point for every nonzero digit, because the decimal expansion of $0$ contains none of $1,\dots,9$, but it contributes nothing to the final total. The real difficulty is to locate all positive fixed points without scanning an enormous search range one value at a time. Mathematical Approach The solution rests on two ideas. First, $f_d(n)$ can be evaluated exactly in $O(\log_{10} n)$ time by summing independent contributions from each decimal position. Second, once $f_d$ is known to be monotone, large intervals can be discarded using only endpoint values, so the search can proceed recursively on decimal blocks rather than on individual integers. The cumulative counting function Let $\nu_d(m)$ be the number of occurrences of digit $d$ in the ordinary decimal expansion of the single integer $m$....

Detailed mathematical approach

Problem Summary

We write the natural numbers $0,1,2,3,\dots$ one after another in base $10$. For a digit $d$ from $1$ to $9$, $f(n,d)$ is the number of times the digit $d$ has been written once the number $n$ has been written, that is, the total number of digits $d$ in the decimal forms of $0,1,\dots,n$. For $d=1$ the statement lists $f(0,1),f(1,1),\dots,f(12,1)$ as $0,1,1,1,1,1,1,1,1,1,2,4,5$, so $f(n,1)$ never takes the value $3$. The solutions of $f(n,1)=n$ begin with $0$, $1$ and $199981$, and $n=0$ is a solution for every nonzero digit. With $s(d)$ the sum of all solutions of $f(n,d)=n$, we are given $s(1)=22786974071$ and must find $s(1)+s(2)+\dots+s(9)$; a number that is a solution for several digits is counted once for each of them. ^[1]

The whole solution in one sentence: $f(n,d)$ can be computed from the digits of $n$ in about a dozen steps, it never decreases, and it exceeds $n$ for every $n\ge10^{11}$, so we cut the range from $0$ to $10^{11}$ into tenths, the tenths into tenths, and so on, throwing away every piece on which the values of $f$ cannot meet the numbers of the piece; for all nine digits together fewer than $90\,000$ pieces are looked at.

Mathematical Approach

Fix a digit $d\in\{1,\dots,9\}$ and write $f(n)$ for $f(n,d)$.

1. The gap between $f(n)$ and $n$

Let $\nu(m)$ be the number of digits $d$ in the single number $m$; for $d=1$, for example, $\nu(11)=2$. Then $f(n)=\nu(0)+\nu(1)+\dots+\nu(n)$, so $f(n+1)-f(n)=\nu(n+1)\ge0$ and $f$ never decreases. The solutions are the zeros of the gap $g(n)=f(n)-n$, and

$$g(n+1)-g(n)=\nu(n+1)-1.$$

So the gap falls by exactly $1$ when $n+1$ contains no digit $d$, stays the same when it contains one, and rises when it contains more. Unlike $f$, the gap goes down and up, so its zeros cannot be found by a binary search.

For $d=1$ the gap starts with $g(0)=g(1)=0$, the solutions $0$ and $1$, and then falls, to $g(9)=-8$. The number $11$ contains two ones, so $f$ jumps from $f(10,1)=2$ to $f(11,1)=4$; this is why $f(n,1)$ never equals $3$. The gap stays negative from $n=2$ to $n=199980$. Around $199981$ we can follow it step by step:

$g(199980)=-1$, and $199981$ contains two ones, so $g(199981)=0$;
each of $199982,\dots,199990$ contains exactly one $1$, so the gap stays $0$: ten solutions in a row;
$199991$ contains two ones, so the gap becomes $1$, and it stays $1$ up to $199999$;
$200000$ contains no $1$, so $g(200000)=0$; $200001$ contains one, so $g(200001)=0$; $200002$ contains none, and the gap drops to $-1$.

That gives twelve solutions: $199981$ to $199990$, $200000$ and $200001$. For $d=1$ there are $84$ solutions, $0$ included: six runs of ten consecutive numbers, ten pairs and four single numbers, the largest being $1111111110$. They form the OEIS sequence A014778 ^[2], and the values $f(n,1)$ themselves form A094798. ^[3]

2. Counting one decimal place

Put $N=n+1$, so that we count among the $N$ numbers $0,1,\dots,N-1$, and fix a place value $p=10^j$ (units, tens, hundreds, …). ^[4] We write $\lfloor x\rfloor$ for the largest integer that is at most $x$, and $a\bmod b$ for the remainder of $a$ after division by $b$; for example $\lfloor13/10\rfloor=1$ and $13\bmod10=3$. Cut the numbers $0,\dots,N-1$ into consecutive blocks of $10p$ numbers, starting at $0$. Inside a complete block the digit at place $p$ runs through $0,1,\dots,9$, each for $p$ numbers in a row, so it equals $d$ exactly $p$ times, and there are $\lfloor N/(10p)\rfloor$ complete blocks. Let $b_j=\lfloor N/p\rfloor\bmod10$ be the digit of $N$ at place $p$. The last, incomplete block has $N\bmod10p=b_jp+(N\bmod p)$ numbers, and the ones with digit $d$ at place $p$ are its numbers in the positions $dp,\dots,dp+p-1$, counted from $0$. The block therefore contains all $p$ of them if $b_j\gt d$, the first $N\bmod p$ of them if $b_j=d$, and none if $b_j\lt d$. The count at place $p$ is

$$c_j=\Bigl\lfloor\frac{N}{10p}\Bigr\rfloor p+t_j,$$

$$t_j=\begin{cases}p, & b_j\gt d,\\ N\bmod p, & b_j=d,\\ 0, & b_j\lt d,\end{cases}$$

and $f(n,d)$ is the sum of the $c_j$ over the places with $p\lt N$; higher places contribute $0$. No correction for leading zeros is needed: padding a short number with zeros never adds a digit $d\ge1$. Two integer divisions in a row give one division by the product: ^[5]

$$\Bigl\lfloor\frac{\lfloor N/p\rfloor}{10}\Bigr\rfloor=\Bigl\lfloor\frac{N}{10p}\Bigr\rfloor.$$

3. Two checks of the formula

For $f(12,1)$ we have $N=13$. At the units place, $\lfloor13/10\rfloor\cdot1=1$ and $b_0=3\gt1$, so $c_0=1+1=2$: the units digits of $1$ and $11$. At the tens place, $\lfloor13/100\rfloor\cdot10=0$ and $b_1=1=d$, so $c_1=13\bmod10=3$: the tens digits of $10$, $11$ and $12$. The total $5$ matches the statement's table.

For the solution $199981$ we have $N=199982$. Its digits at the five lowest places are $2,8,9,9,9$, all larger than $1$, so each of these places gets the full tail $p$, and the digit at place $10^5$ is $1=d$:

places $1$ to $10^4$: $19998+1$, $19990+10$, $19900+100$, $19000+1000$ and $10000+10000$, that is $19999$ and four times $20000$;
place $10^5$: no complete block, and the tail $199982\bmod10^5=99982$.

The sum is $19999+80000+99982=199981$, so $f(199981,1)=199981$, as the statement says.

4. Complete blocks and the frequency of a digit

If $N=10^k$, then at every place $10^j$ with $j\lt k$ the numbers $0,\dots,N-1$ form $10^{k-j-1}$ complete blocks with $10^j$ hits each, so ^[3]

$$f(10^k-1,d)=k\cdot10^{k-1}.$$

In words: the $10^k$ strings of $k$ digits contain $k\cdot10^k$ digits, and each digit value makes up one tenth of them. Compared with $10^k$, the count $k\cdot10^{k-1}$ is smaller for $k\le9$, equal for $k=10$ and larger for $k\ge11$. In particular $f(10^{10}-1,d)=10^{10}$ for every digit. The number $10^{10}$ contains no digit from $2$ to $9$, so it is a solution for each of the eight digits $d=2,\dots,9$ and is counted eight times in the requested sum, while its leading one gives $f(10^{10},1)=10^{10}+1$.

After the initial $0$, the digits written here are those of the Champernowne constant $0.123456789101112\ldots$, which is normal in base $10$, so in the long run each digit makes up one tenth of them. ^[6] About $n\log_{10}n$ digits are written up to $n$, so $f(n,d)/n$ grows without bound; this explains why the solutions stop, and Section 5 gives the cutoff.

5. No solution has twelve or more digits

Write the digits of $N=n+1$ as $N=\sum_ib_i10^i$. The complete-block part of the count at place $10^j$ is $\lfloor N/10^{j+1}\rfloor10^j$, and the quotient keeps only the digits of $N$ above place $10^j$:

$$\Bigl\lfloor\frac{N}{10^{j+1}}\Bigr\rfloor=\sum_{i\gt j}b_i10^{i-j-1}.$$

So the digit $b_i$ contributes $b_i10^{i-1}$ at each of the $i$ places $j=0,1,\dots,i-1$ below it, and

$$\sum_{j\ge0}\Bigl\lfloor\frac{N}{10^{j+1}}\Bigr\rfloor10^j=\sum_{i\ge1}i\,b_i\,10^{i-1}.$$

The tails $t_j$ are never negative, so subtracting $n=\sum_ib_i10^i-1$ gives

$$g(n)=f(n,d)-n\ge1+\sum_{i\ge0}b_i\,w_i,$$

with the weights $w_i=(i-10)\,10^{i-1}$; for $i=0$ this is $w_0=-1$. The weight is negative for the ten lowest places $i=0,\dots,9$, zero for $i=10$ and positive for $i\ge11$. As $b_i\le9$, the ten lowest terms together are at least

$$\begin{aligned}9\sum_{i=0}^{9}w_i&=-9\cdot123456790\\&=-1111111110.\end{aligned}$$

If $n\ge10^{11}$, then $N\gt10^{11}$ has a nonzero digit at some place $i\ge11$; that term alone is at least $w_{11}=10^{10}$, and no term with $i\ge10$ is negative. Therefore, for every $n\ge10^{11}$ and every digit $d$,

$$\begin{aligned}g(n)&\ge1+10^{10}-1111111110\\&=8888888891\gt0,\end{aligned}$$

and all solutions are below $10^{11}$. For a small check, $n=12$ and $d=1$ give the bound $1-3-9=-11$, and indeed $f(12,1)-12=-7$. The limit $10^{11}$ cannot be lowered to $10^{10}$: the largest solution for $d=8$ is $79998399997$.

6. Throwing away a whole interval

Suppose a solution $x$ lies in an interval $[L,R]$. Because $f$ never decreases, $f(L)\le f(x)=x\le f(R)$, and of course $L\le x\le R$. So an interval can contain a solution only if both

$$f(L)\le R,\qquad f(R)\ge L.$$

If one of them fails, the interval is thrown away without looking at its numbers. With $R=L+s$, the two conditions say that the gap is at most $s$ at the left end and at least $-s$ at the right end. For example, for $d=1$ the interval $[30,40]$ is thrown away because $f(40,1)=14\lt30$. The test is necessary, not sufficient: for $d=1$ the interval $[100,200]$ passes it, since $f(100,1)=21\le200$ and $f(200,1)=140\ge100$, yet contains no solution. An interval that passes is therefore split further. This is the branch-and-bound principle: a bound rules out a whole branch of candidates at once. ^[7]

7. The decimal search tree

The search starts from the root interval $[0,10^{11}]$. An interval $[L,L+s]$ that passes the test and has $s=10^j\gt1$ is split into the ten intervals

$$\Bigl[L+\frac{ks}{10},\,L+\frac{(k+1)s}{10}\Bigr]$$

for $k=0,1,\dots,9$; neighbours share an endpoint, which is harmless. The numbers $L,\dots,L+s-1$ of an interval of length $s=10^j$ share all their digits from place $10^j$ upward, so each level of the tree fixes one more digit. An interval $[x,x+1]$ of length $1$ stands for the single number $x$, and $x$ is reported exactly when $f(x)=x$.

The search finds every solution: a solution $x\lt10^{11}$ lies in a chain of nested intervals, one for each level, from the root down to its leaf $[x,x+1]$; each of them contains $x$ and so passes the test of Section 6, the leaf is reached, and the equality is checked exactly. By Section 5 there are no solutions from $10^{11}$ on, the right end of the root included.

8. A small search by hand

To see the tree at work, run it for $d=1$ from the root $[0,1000]$. Of the ten intervals of length $100$, only $[0,100]$ and $[100,200]$ pass; $[200,300]$ fails because $f(300,1)=160\lt200$, and the later ones fail in the same way. Of their twenty children only $[0,10]$ and $[10,20]$ pass: $[20,30]$ fails because $f(30,1)=13\lt20$, and $[110,120]$ because $f(120,1)=53\lt110$. Of the next twenty intervals only $[0,1]$ and $[1,2]$ pass; for instance $[10,11]$ fails because $f(11,1)=4\lt10$. Both surviving leaves are solutions, $0$ and $1$. The search looked at $1+10+20+20=51$ intervals and evaluated $f$ twice for each, instead of testing $1000$ numbers.

How the Code Works

All three programs implement Sections 2, 6 and 7 with the same two functions; we follow the C++ program ^[8] in the order in which it runs. main first lets parse_arguments read the options --limit=N (default $10^{15}$, set in Options) and --skip-checkpoints. Unless --skip-checkpoints was given, run_checkpoints then tests count_digit_upto(12, 1) == 5, the last row of the statement's table, and compares solve(100000) with brute(100000), which follows the definition: for each digit it keeps a running count of the digits of $0,1,\dots,x$ and adds $x$ whenever that count equals $x$. A failed check ends the program with exit code $2$; otherwise it prints solve(limit).

count_digit_upto(n, d) is Section 2. It first increments n, which turns it into $N$, and then runs p10 through $1,10,100,\dots$ while p10 < n. In each round cur is the digit $b_j$, (n / p10 / 10) * p10 counts the complete blocks by the last formula of Section 2, and the tail is added: p10 if cur > d, and $N\bmod p$ if cur == d. The C++ writes this last tail as n % (10 * p10) - d * p10, which is the same number because $N\bmod10p=b_jp+(N\bmod p)$ and $b_j=d$; the Python and Java versions write n % p10 directly.

search_fixed_points(d, start, span, limit, acc) is one node of the tree of Section 7. It returns at once if start is beyond limit, sets right to the smaller of limit and start + span, computes lo and hi, the values of $f$ at start and right, and drops the interval if hi < start or lo > right, the test of Section 6. A node with span == 1 adds start to the accumulator acc when lo == start; any other node calls itself on its ten children with step = span / 10. solve takes as root span the smallest power of ten that is at least the limit and runs the search for $d=1,\dots,9$ into one sum. The right end of the root gets no leaf, so a limit that is itself a power of ten is never tested; at the published limits Section 5 shows that this costs nothing, but --limit=1, for example, returns $0$ and misses the solution $1$ of $d=1$.

The Python and Java programs contain only the two functions and the loop over the digits, with the limit fixed at $10^{11}$, the bound of Section 5, and no checks; Python's search passes the accumulator in and out, and Java's returns the sum of its subtree. The C++ root $[0,10^{15}]$ adds four levels at the top and $2000$ examined intervals: the $36$ new ancestors $[0,10^{12}],\dots,[0,10^{15}]$, four per digit, and $1964$ intervals starting at $10^{11}$ or later, where Section 5 rules out solutions; the result is the same. At these limits no quantity exceeds $10^{16}$, the last value of p10, and the total is a sum of $661$ numbers below $10^{11}$, so the 64-bit long long and long suffice, while Python's integers are unbounded. The C++ program does not check a larger --limit: from $10^{18}$ on, p10 *= 10 overflows. The recursion is $12$ levels deep, or $16$ for the C++ default.

Complexity and Verification

One evaluation of $f$ makes one round for each power of ten $p\lt N$, at most $12$ below $10^{11}$ and $16$ for the C++ default, so it costs $O(\log n)$. With the limit $10^{11}$ the search examines $87\,209$ intervals, keeps $10\,622$ of them and finds $661$ solutions, the nine zeros included; with $10^{15}$ it examines $89\,209$. The two evaluations per interval make $1\,849\,032$ rounds of the digit loop at the limit $10^{11}$ and $1\,900\,359$ at $10^{15}$, and each program, the C++ checks included, runs in well under a second on our test machine. For a limit $U$ and $V$ examined intervals the cost is $O(V\log U)$; we know no a priori bound on $V$ better than the $O(U)$ nodes of the whole tree, so the counts above are measured. A passing interval $[L,L+s]$ below $10^{11}$ has $-12s\le g(L)\le s$, as the gap rises by at most $11$ per step there, so short intervals pass only where the gap is near zero. Only one path of the tree is stored at a time, so the memory is $O(\log U)$.

The C++ cross-check with brute is weak: below $100000$ the only nonzero solution is $n=1$ for $d=1$, so both sides equal $1$. For this article we checked more:

the formula of Section 2 against direct counting for all nine digits and all $n\le300\,000$;
direct scans: for $d=1$ exactly $24$ solutions up to $2\cdot10^6$, for the other digits only $0$ up to $10^6$;
Section 5 on $20\,000$ random values below $10^{16}$; the exact smallest gap over all $n$, from a recursion on the leading digit, is $-987654320$, for $d=9$;
an independent scan without the tree: at a gap $c\gt0$ it jumps ahead by $c$, as the gap falls by at most $1$ per step, and at $c\lt0$ by $\lceil -c/11\rceil$, as numbers up to $10^{11}$ have at most $12$ digits; it found the same $661$ solutions below $10^{11}$ with $94\,369$ evaluations of $f$;
the $84$ solutions for $d=1$ agree with A014778 ^[2] and add up to the given $s(1)$;
the three programs print the same total, and so does the C++ program with --limit=100000000000.

Footnotes and References

The references below supply the background facts used above. The bound of Section 5, the correctness of the search and all counts of intervals and solutions are derived or measured in this article.

Project Euler 156 — Counting Digits. The official statement defines f(n, d) by writing 0, 1, 2, … in base 10, gives f(n, 1) for n ≤ 12, the first solutions 0, 1 and 199981 for d = 1 and s(1) = 22786974071, and asks for the sum of s(d) over 1 ≤ d ≤ 9, counting a number once for every digit it solves.
OEIS A014778 — Numbers k equal to the number of 1's in the decimal digits of all numbers ≤ k. The entry lists the 84 solutions for d = 1, from 0 to 1111111110, notes that they form six runs of ten consecutive numbers, ten pairs and four isolated numbers, and records that the list is complete.
OEIS A094798 — Number of times 1 is used in writing out all the numbers 1 through n. Its terms are f(n, 1) for n ≥ 1; the entry notes that the counts for 9, 99, 999, … are 1, 20, 300, 4000, …, the sequence k·10^(k−1) of A053541, and that A014778 gives its fixed points.
Wikipedia — Positional notation. In the decimal system each digit is multiplied by the power of ten that belongs to its place; Sections 2 and 5 use this expansion N = Σ bᵢ·10ⁱ.
Wikipedia — Floor and ceiling functions. The article gives the nested-division rule ⌊⌊x/m⌋/n⌋ = ⌊x/(mn)⌋ for a positive integer n and defines x mod y = x − y⌊x/y⌋; Section 2 and count_digit_upto rely on both.
Wikipedia — Champernowne constant. The constant 0.12345678910111213… concatenates the decimal forms of the positive integers; D. G. Champernowne proved in 1933 that it is normal in base 10, and in a normal number every digit occurs with limiting frequency 1/10.
Wikipedia — Branch and bound. The candidates form a rooted tree whose branches are subsets of them, and a branch is discarded when a bound shows that it cannot contain a better solution; Sections 6 and 7 use the test f(L) ≤ R, f(R) ≥ L as the bound.
C++ — Euler156.cpp. The linked immutable C++ revision contains count_digit_upto, search_fixed_points, solve, brute and the checks of run_checkpoints. It is the implementation record for this article.

Problem 156 source code

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using i64 = long long;

struct Options {
    i64 limit = 1000000000000000LL;
    bool run_checkpoints = true;
};

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

    i64 parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<i64>(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_i64_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }

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

    return options.limit >= 0;
}

i64 count_digit_upto(i64 n, const int d) {
    ++n;

    i64 result = 0;
    i64 p10 = 1;
    while (p10 < n) {
        const int cur = static_cast<int>((n / p10) % 10);
        result += (n / p10 / 10) * p10;

        if (cur == d) {
            result += n % (10 * p10) - static_cast<i64>(d) * p10;
        } else if (cur > d) {
            result += p10;
        }

        p10 *= 10;
    }

    return result;
}

void search_fixed_points(const int d, const i64 start, const i64 span, const i64 limit, i64& acc) {
    if (start > limit) {
        return;
    }

    const i64 right = std::min(limit, start + span);
    const i64 lo = count_digit_upto(start, d);
    const i64 hi = count_digit_upto(right, d);

    if (hi < start || lo > right) {
        return;
    }

    if (span == 1) {
        if (lo == start) {
            acc += start;
        }
        return;
    }

    const i64 step = span / 10;
    for (int k = 0; k < 10; ++k) {
        search_fixed_points(d, start + static_cast<i64>(k) * step, step, limit, acc);
    }
}

i64 solve(const i64 limit) {
    i64 root_span = 1;
    while (root_span < limit) {
        root_span *= 10;
    }

    i64 sum = 0;
    for (int d = 1; d <= 9; ++d) {
        search_fixed_points(d, 0, root_span, limit, sum);
    }
    return sum;
}

i64 brute(const i64 limit) {
    auto count_in_number = [](i64 x, const int d) {
        if (x == 0) {
            return 0;
        }
        int cnt = 0;
        while (x > 0) {
            cnt += static_cast<int>(x % 10 == d);
            x /= 10;
        }
        return cnt;
    };

    i64 ans = 0;
    for (int d = 1; d <= 9; ++d) {
        i64 running = 0;
        for (i64 x = 0; x <= limit; ++x) {
            running += count_in_number(x, d);
            if (running == x) {
                ans += x;
            }
        }
    }
    return ans;
}

bool run_checkpoints() {
    if (count_digit_upto(12, 1) != 5) {
        std::cerr << "Checkpoint failed for f(12,1)" << '\n';
        return false;
    }
    if (solve(100000) != brute(100000)) {
        std::cerr << "Checkpoint failed for brute cross-check at 100000" << '\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 << solve(options.limit) << '\n';
    return 0;
}

Python

# Problem 156: Counting Digits - find fixed points where f(n,d) = n

def solve():
    def count_digit_upto(n, d):
        """Count occurrences of digit d in 1..n"""
        n += 1
        result = 0
        p10 = 1
        while p10 < n:
            cur = (n // p10) % 10
            result += (n // p10 // 10) * p10
            if cur == d:
                result += n % p10
            elif cur > d:
                result += p10
            p10 *= 10
        return result
    
    def search(d, start, span, limit, acc):
        if start > limit:
            return acc
        right = min(limit, start + span)
        lo = count_digit_upto(start, d)
        hi = count_digit_upto(right, d)
        if hi < start or lo > right:
            return acc
        if span == 1:
            if lo == start:
                acc += start
            return acc
        step = span // 10
        for k in range(10):
            acc = search(d, start + k * step, step, limit, acc)
        return acc
    
    limit = 10**11
    root_span = 1
    while root_span < limit:
        root_span *= 10
    
    total = 0
    for d in range(1, 10):
        total = total + search(d, 0, root_span, limit, 0)
    print(total)

solve()

Java

public class Euler156 {
    static long countDigitUpto(long n, int d) {
        n++;
        long result = 0, p10 = 1;
        while (p10 < n) {
            int cur = (int) ((n / p10) % 10);
            result += (n / p10 / 10) * p10;
            if (cur == d)
                result += n % p10;
            else if (cur > d)
                result += p10;
            p10 *= 10;
        }
        return result;
    }

    static long search(int d, long start, long span, long limit) {
        if (start > limit)
            return 0;
        long right = Math.min(limit, start + span);
        long lo = countDigitUpto(start, d), hi = countDigitUpto(right, d);
        if (hi < start || lo > right)
            return 0;
        if (span == 1)
            return lo == start ? start : 0;
        long step = span / 10, acc = 0;
        for (int k = 0; k < 10; k++)
            acc += search(d, start + k * step, step, limit);
        return acc;
    }

    public static void main(String[] args) {
        long limit = 100000000000L, rootSpan = 1;
        while (rootSpan < limit)
            rootSpan *= 10;
        long total = 0;
        for (int d = 1; d <= 9; d++)
            total += search(d, 0, rootSpan, limit);
        System.out.println(total);
    }
}