Counting without enumerating

How many numbers up to 1,000 have no digit 4 and never contain “13”? You could check all thousand. The answer is 712, and you can get it by visiting 9 states.

First, a range is two prefixes: the count for [A, B] is the count for [0, B] minus the count for [0, A−1]. So you only ever count from zero up to some N.

Inside [0, N], build the number from its most significant digit and carry one flag, tight, which says whether you are still pressed against the limit. If N is 723 and you put a 7 first, the next digit can only go up to 2. Put a 6 first and you are free: anything from 0 to 9 works from there on.

Fig. 1 — Numbers from 0 to N with no digit 4 and no “13”DP with tight

Loading interactive figure…

Static version: up to 1,000 there are 712 numbers with no digit 4 and no “13”, computed with 9 DP states.

Why does memoization pay off? Think of an 18-digit number that ends in 0123456789. Every possible prefix in front of that ending leads to the same question about the same remaining digits, 10⁸ identical calculations if you recompute it each time. Store it once and look it up.

The state stays small: the position, whatever the question needs to remember (here, whether the last digit was a 1), and tight. The count of states depends on how many digits N has, not on how big N is. Before you enumerate anything, ask what the smallest state is that sums up everything that came before.