Inclusion/Exclusion: How many natural numbers < 10,000,000 contain 168, in order, consecutively?

Question

For example, 1,683,718, but not 1,568.

I need to use the multiplication principle (which will produce overcounting) and the principle of inclusion/exclusion to find this (or a better way, if possible). Any pointers? The fixed 168 is what throws me off from typical problems.

Answer 1

We're counting the union of five sets: the strings of the form 168XXXX, the strings of the form X168XXX, etc. Each set has $10000$ elements. By inclusion-exclusion, you can sum these counts to $50000$ and subtract the counts of the pairwise intersections of the sets, which contain strings of the form 168168X, 168X168, and X168168, of which there are $30$. The intersections of three or more sets are all empty, so we are done, arriving at $50000-30=49970$.

To double-check, we can get the same answer by brute force:

$ python
>>> sum('168' in str(x) for x in range(10000))
20
>>> sum('168' in str(x) for x in range(100000))
300
>>> sum('168' in str(x) for x in range(1000000))
3999
>>> sum('168' in str(x) for x in range(10000000))
49970