So after all that...

What would be our ultimate solution for the problem? Given the previous post, we have two cases:

• m' and n' both have d digits: in this case, if m' is greater than the largest d-digit Y, the result is 0; otherwise, we have to actually generate the d-digit Y values and return the number that are in range.
• m' has d digits and n' has d' digits, d < d': the result then is the sum of the number of Ys between m' and 10^d-1, the sum of the number of k-digit Ys for k from d + 1 to d' - 1, and the number of Ys between 10^d'+1 and n'.

We need smarter memoization of the function that maps d to the list of d-digit Ys and the function that maps d to the count of d-digit Ys, that doesn't grind out all the results for all values from 1 to d. (If they were recursive in d, I wouldn't mind.) Time to do some research.

UPDATE: or maybe I have a misconception about lazy evaluation. If the list elements don't depend on one another save for their position, maybe you don't have to evaluate an element just to skip over it with !!.

(Of course, we can easily generate the largest d-digit Y. If d == 1, it's 3; otherwise it's the largest two-2 d-digit Y.)