Digit DP, in depth: prefix counting, the tight and started flags, sums and k-th queries, bottom-up tables and brute-force testing

When digit DP applies

Digit DP applies when three things hold. The question is a count (or sum) of integers in a range with some property. The property can be decided by scanning the digits left to right while remembering a small summary, such as a remainder, the previous digit, a count of some digit, or a bitmask of digits used. And the range is too large to enumerate. If the property needs the whole number at once, such as primality, digit DP does not help; if it needs only a bounded summary, it almost certainly does.

The summary is the heart of the design. For divisibility of the digit sum by k, the summary is the sum modulo k. For divisibility of the number itself by k, it is the number modulo k, updated as (r * 10 + d) % k. For no adjacent equal digits, it is the previous digit. Choosing the smallest sufficient summary is the same skill as choosing a state in any DP.

Ranges as prefix counts

Ranges are handled by prefix counting. Define f(N) as the count of valid integers in [0, N]. Then the count in [L, R] is f(R) - f(L - 1), with f(-1) = 0. This turns every problem into one with a single upper bound, which is what makes the tight flag possible.

Two consequences matter in practice. First, f includes zero, which may or may not satisfy your property; zero has digit sum 0, so it counts for divisibility questions, and the count over [1, N] is one less. Second, when L arrives as a string of hundreds of digits, compute L - 1 with a string decrement or write a variant of f that excludes the bound itself.

The state and the tight flag

Write N's digits as d[0..n-1]. At position pos we choose a digit x. If every earlier digit equalled N's digit, we are tight and may only choose x <= d[pos]; choosing x < d[pos] makes the rest free. If we were already below, we may choose any digit 0 to 9. The full state is (pos, summary, tight), plus a started flag when leading zeros would corrupt the summary.

The number of states is n x |summary| x 2 x 2 and each state tries at most 10 digits. For N up to 10¹⁸ (19 digits) and a remainder modulo 7 that is 19 x 7 x 2 = 266 states and about 2,660 transitions, whatever the size of N.

A reusable template

Here is a template for the digit sum divisible by k. The recursion reads like the definition, and the cache makes it polynomial.

from functools import lru_cache

def count_upto(n: int, k: int) -> int:
    """Integers in [0, n] whose digit sum is divisible by k."""
    if n < 0:
        return 0
    d = list(map(int, str(n)))

    @lru_cache(maxsize=None)
    def go(pos: int, rem: int, tight: bool) -> int:
        if pos == len(d):
            return 1 if rem == 0 else 0
        limit = d[pos] if tight else 9
        total = 0
        for x in range(limit + 1):
            total += go(pos + 1, (rem + x) % k, tight and x == limit)
        return total

    return go(0, 0, True)

def count_range(lo: int, hi: int, k: int) -> int:
    return count_upto(hi, k) - count_upto(lo - 1, k)

The cache is local to one bound, because d is captured. When you answer many queries, memoize only the non-tight states, keyed by remaining length rather than position: a free suffix of length m with a given summary has the same count for every bound, so one table serves all queries. For a modulus that changes per query, include it in the key or rebuild the table.

Worked example: [1000, 2025]

How many integers in [1000, 2025] have a digit sum divisible by 7? Compute f(2025) and f(999).

For f(2025) the walk starts tight at the digit 2. Choosing 0 or 1 frees three positions: we need the count of three-digit strings (with leading zeros, which do not change a digit sum) whose sum, plus 0 or 1, is divisible by 7. Choosing 2 keeps us tight at the next digit, whose limit is 0, so only 0 is allowed; then the third digit's limit is 2, where choosing 0 or 1 frees the last position and choosing 2 keeps us tight on a final digit limited to 5. The program sums these branches: f(2025) = 283, which includes zero, and f(999) = 140. So the answer is 283 minus 140, which is 143, and a brute-force loop over 1000 to 2025 also gives 143.

The same function scales: count_upto(10**18, 7) returns instantly, because only the single tight path depends on the bound and every free branch is one of a few hundred cached states.

Leading zeros and the started flag

Leading zeros are the classic trap. To handle bounds of different lengths uniformly, the template pads every number to N's length: 25 under a bound of 5000 is walked as 0025. For a digit sum that is harmless. For "no two adjacent digits are equal" it is wrong, because the padding zeros look adjacent and equal, so 25 is rejected. The fix is a started flag: until the first non-zero digit, zeros are padding and do not update the summary.

def no_adjacent_equal_upto(n: int) -> int:
    d = list(map(int, str(n)))

    @lru_cache(maxsize=None)
    def go(pos: int, prev: int, tight: bool, started: bool) -> int:
        if pos == len(d):
            return 1                      # counts 0 as well
        limit = d[pos] if tight else 9
        total = 0
        for x in range(limit + 1):
            if started and x == prev:
                continue
            now = started or x != 0
            total += go(pos + 1, x if now else -1, tight and x == limit, now)
        return total

    return go(0, -1, True, False)

Measured against brute force, the correct version gives 3,645 integers in [100, 5000]. Dropping the flag gives 3,555, about 2.5% low. That is the dangerous kind of bug: plausible, small and invisible without a reference.

Sums and k-th queries

Digit DP can return more than a count. To sum a quantity over all valid numbers, return a pair (count, sum) from each state; when you place digit x at a position with weight w, the contribution is sum_child + x * w * count_child. For the sum of all digits from 0 to 2025 the weight is 1, and the result is 28,179, which brute force confirms.

@lru_cache(maxsize=None)
def go(pos, tight):          # returns (count, digit_sum) for the suffix
    if pos == len(d):
        return 1, 0
    limit = d[pos] if tight else 9
    cnt = s = 0
    for x in range(limit + 1):
        c_, s_ = go(pos + 1, tight and x == limit)
        cnt += c_
        s += s_ + x * c_
    return cnt, s

To find the k-th valid number, binary search on N with f, since f is monotone: the smallest N with f(N) - f(0) >= k is the answer. The 100th positive integer with digit sum divisible by 7 is 700. A faster method descends digit by digit using the free-suffix counts to choose each digit directly, without the outer search. Values that grow quickly need a modulus; apply it to counts and sums consistently. Counting with binomials instead of DP is sometimes possible when the property is symmetric, as in Combinatorics, in depth.

Bottom-up tables and bigger states

Recursion depth equals the number of digits, so stack limits only bite for bounds with thousands of digits. For those, or in languages without convenient memoization, fill a table bottom-up: free[m][s] is the number of length-m digit strings that take summary s to an accepting end. Then walk N's digits once, adding free[m][next_state] for each digit below the bound's digit, and continue along the tight path. This separation, a bound-independent table plus one linear walk, is the fastest form and the easiest to reason about. The fill-order reasoning is the same as in filling DP tables cell by cell.

Larger summaries, such as a bitmask of the digits used (1,024 values) or a pair of remainders, multiply the state count; keep the product under a few million and the approach stays fast. The design question is always the same one met in Tree DP: what is the smallest description of the past that decides the future?

Testing against brute force

Every digit DP should ship with a brute-force oracle, because the bugs are off by small amounts. Compare on every bound from 0 to a few thousand and on random bounds near powers of ten.

import random

def brute(lo, hi, pred):
    return sum(1 for v in range(lo, hi + 1) if pred(v))

pred = lambda v: sum(map(int, str(v))) % 7 == 0
for n in list(range(0, 3000)) + [random.randrange(10**5) for _ in range(200)]:
    assert count_upto(n, 7) == brute(0, n, pred), n
for lo, hi in [(1000, 2025), (1, 1), (0, 0), (99, 101)]:
    assert count_range(lo, hi, 7) == brute(lo, hi, pred)

Include the edges explicitly: zero, single-digit bounds, bounds that are a power of ten, ranges with lo = 0 (which needs f(-1)), and bounds ending in 9 and in 0, where the tight path behaves differently.

Failure modes

• Memoizing tight states across bounds. A cache shared between calls with different N returns counts for the wrong bound. Key it by the bound or cache only free states.
• Forgetting zero. f(N) counts 0 when 0 has the property; subtract it for ranges starting at 1.
• Leading zeros in the summary. Any property that looks at adjacency, first digit or digit counts needs the started flag.
• Wrong update order. For the number modulo k, the update is (r * 10 + x) % k, not (r + x) % k; mixing them passes small tests for k = 3 and 9, where both happen to agree.
• Overflow. Counts up to 10¹⁸ fit in 64 bits, sums do not; use big integers or a modulus.

What to do next

1. Implement count_upto from memory, then add the brute-force test loop before trusting it.
2. Rewrite it with a started flag and solve no-adjacent-equal-digits; reproduce 3,645 for [100, 5000].
3. Change the summary to the number itself modulo k and test with k = 7, where it differs from the digit sum.
4. Return (count, sum) pairs and reproduce 28,179 for the digit sum up to 2025.
5. Convert one solution to the bottom-up free table plus a single tight walk.
6. Solve a problem with a digit bitmask state, such as numbers whose digits are all distinct.