Almost every integer has a digit 3 in it.

This is an engagingly sounding sentence that begs some clarification. Of course, no one would claim that every number has a digit 3 in it. But what is almost? There are infinitely many integers, and, among them, there are obviously infinitely many integers that have at least one digit equal to 3. For example, we have an infinite sequence 3, 33, 333, 3333, and so on. As easily, we can produce an example of an infinite sequence of integers that do not have a digit 3: 1, 11, 111, 1111, and so on.

Still, the claim is not altogether frivolous. Let's consider in turn integers less than 10, 100, 1000, etc. And, for every such group of integers, let's count how many of them have at least one digit equal to 3. For convenience, let's start with 0.

Among 10 numbers 0, 1, 2, 3, 4, 5, 6, 7, 8 , 9 written with a single digit, only 1 has digit 3 - the number 3 itself. Among 100 numbers 0, 1, ... ,9, 10, 11, ..., 98, 99 written with 1 or 2 digits, the following include digit 3: 3, 13, 23, 30, 31, ..., 38, 39, 43, 53, ..., 93. 19 numbers in all. When we look at the numbers below 1000, it is easy to notice that there are 10 groups of 100 consecutive integers each. The first, as we just found contains 19 integers with a digit 3. And the same is true of 8 other groups of 100 integers: those that start with 1, 2, 4, 5, 6,7 ,8 , or 9. All 100 integers that start with 3 obviously have at least one 3. So, below 1000, there are 9·19 + 100 integers with a digit 3 in them.

The number K_n of positive integers with not more than n digits that are written with at least one 3, satisfies the recurrence relation:

(This is because any number counted in K_n, when be appended any digit, except for 3, will be counted in K_{n +1}. In addition, there are there are 10ⁿ numbers of length n + 1 that end with 3.)

There is another way to obtain number K_n. But first let's regress a little. I do not know whether you noticed this but the opening sentence "Almost every integer has a digit 3 in it" is guilty of an additional ambiguity. Integers do not contain digits, their customary decimal representations - numerals - do. (The same, of course, is true of other positional systems. On the other hand, in Roman numeration, the sentence is completely meaningless.)

What is a decimal numeral? A decimal numeral is an arbitrary string (a word) of letters (digits) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Only one condition is imposed, namely, that the first letter in the string be different from 0. So that 123 is a decimal numeral, while 0123 is not. (The reason is that of convenience but also to avoid unnecessary ambiguity: 0123 would denote the same integer as 00123.)

Now back to the number K_n - the number of positive integers below 10ⁿ whose decimal numeral contains a digit 3. Once we limited the length of the strings of interest to n, we may (now unambiguously) substitute strings of exact length n even for shorter numerals by prepending an appropriate number of 0s. It is simply much more convenient to count the number of strings of the same rather than different length. Thus we are to answer the question: "How many strings of length n contain at least one digit 3?" In all, there are 10ⁿ (decimal) strings of length n. For the first digit could be any of the admissible 10 (0, ..., 9), and the same is true for the second digit, the third one, etc., as well as the last, n^th digit. By the same token, if we try to avoid the digit 3, we have only 9 choices for every digit. Therefore, there are 9ⁿ strings that do not contain the digit 3. Finally, the number of strings of length n that contain at least one 3 is the difference 10ⁿ - 9ⁿ.

You may want to check that K_n = 10ⁿ - 9ⁿ satisfies the recurrence (*) for n > 0. The remarkable thing about this number is that the proportion (10ⁿ - 9ⁿ)/10ⁿ = 1 - (9/10)ⁿ tends to 1 as n grows. As we allow longer and longer numbers, the proportion of numbers that "have a digit 3 in them" becomes closer and closer to 1. Almost every integer has a digit 3 in it.

Well, where do we go from here? There are several questions that can be legitimately asked concerning the problem at hand.

Obviously, what is true for the digit 3 is also also true for other digits. That is, for all non-zero digits. Zero is a different matter. What can be said about 0? What proportion of integers has a 0 in their decimal expansion?

It's also clear that instead of the decimal we could have considered any other positional system. Does the distribution of integers with a zero in their expansion depend on the base of the system?

What if we looked for a pair of subsequent digits? For example, what can be said about integers that include, say, 27 in their decimal expansion? The problem of multiple consecutive digits appears to generalize the original statement, but it does not actually. Do you see why?

So, there "are more" numbers that contain a given digit than those that miss it. This two sets index two series of reciprocals that together form the harmonic series. The series of the reciprocals of the integers that contain a given digit is divergent, whereas the series of the reciprocals of the integers that miss a given digit is convergent.

Finally, it's instructive to compare what we learned now with Benford's Law.

References

1. G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth Edition, Oxford Science Publications, 1996.
2. Clifford A. Pickover, Keys to Infinity, John Wiley & Sons, 1995