title: How to count integers between large A and B with a certain property?
body: <p>In programming contests, the following pattern occurs in a lot of tasks:</p>
  
  <blockquote>
    <p>Given numbers A and B that are huge (maybe 20 decimal digits or more), determine the number of integers X with A ≤ X ≤ B that have a certain property P</p>
  </blockquote>
  
  <p><a href="https://www.google.com/?q=%22spoj%22+%22numbers+between%22+A+and+B#q=%22spoj%22+%22numbers+between%22+A+and+B" rel="noreferrer">SPOJ has lots of tasks like these</a> for practice.</p>
  
  <p>Where examples of interesting properties include:</p>
  
  <ul>
  <li>"the digit sum of X is 60"</li>
  <li>"X consists only of the digits 4 and 7"</li>
  <li>"X is palindromic", which means that the decimal representation of X equals its reverse (for example, X = 1234321)</li>
  </ul>
  
  <p>I know that if we define <em>f(Y)</em> to be the number of such integers X ≤ Y, then the answer to our question is <em>f(B) - f(A - 1)</em>. The reduced problem is how to compute the function <em>f</em> efficiently. In some cases we can make use of certain mathematical properties to come up with a formula, but often the properties are more complicated and we don't have enough time for that in a contest.</p>
  
  <p>Is there a more general approach that works in a lot of cases? And can it also be used to enumerate the numbers with the given property or compute some aggregation on them?</p>
  
  <p>A variation of this is to find the k-th number with a given property, which of course can be solved by using binary search together with a counting function.</p>