tight. Position, tightness, and a small property summary make repeated suffix choices equivalent.

Build numbers left to right beneath a ceiling. Tight means your prefix still touches the ceiling; one smaller digit releases every later position.

What the function promises: Count integers in [0, bound] whose decimal representation contains no digit 7. Zero is included; bound must be nonnegative.

from functools import cache

def count_without_seven(bound):
    if bound < 0: raise ValueError("Negative bound")
    digits = str(bound)
    @cache
    def count(position, tight):
        if position == len(digits): return 1
        limit = int(digits[position]) if tight else 9
        return sum(count(position+1, tight and digit == limit)
                   for digit in range(limit+1) if digit != 7)
    return count(0, True)

assert count_without_seven(9) == 9
assert count_without_seven(77) == 63
assert count_without_seven(0) == 1

Work and storage: O(d·2·10) time and O(d) cached states for d digits in this simple rule.

When to recognize it: Position, tightness, and a small property summary make repeated suffix choices equivalent.

Check before applying it: Leading zeros and inclusion of zero must match the exact counting contract.

Add remaining sum to the state; prune when it becomes negative or impossible to fill.