Count the number of times that the number ’13’ appears at least once in an n digit number

combinatorics

Edited question to provide more information and clarity. See original question at the bottom for reference.

My end goal is to count how many times '13' appears in an n-digit number at least once. This means that a number like 21313 would count as only 1. I created a similar question (which is linked to this one I believe) where I received help to obtain the total number of times '13' appears in an n-digit number (where a number like 21313 would count as 2).
I realized that if I take the total number of times 13 appears and I subtract the number of times it's "repeated" (where in a number like 131313 I consider the number of "repetitions" to be 2), I get the total number of times that 13 appears at least once in that n-digit number.
I say "repetition" because I'm not counting all the number of times it's repeated, but the number of additional times that 13 shows up in a number. This is why in a number like 131313, I don't say there's 3 "repetitions." I'm saying that the first '13' shows up once and then the 2nd and 3rd 13's are 2 extra '13's.
I created this question to help me understand how to count those repetitions (see original question below for more information).
I'm not sure if this is the best way to solve this problem, but it's what makes the most sense for now. Please let me know if there's other/better ways to solve it as I've been discovering multiple methods to solve similar problems and would love to know more about the subject).

For reference, here's the values I've obtained using a code I wrote to help solve the problem. Note: I'm including 0 in the first digit of an n-digit number so that I can account for all of the values from 0 up to the highest number in that n-digit number (meaning in a 3 digit number, I'm looking at all the numbers from 0 to 999).

| # Digits | Total # Times 13 Appears | # "Repetitions" | Total # Times 13 Appears at Least Once |
|----------|--------------------------|---------------|----------------------------------------|
| 1        | 0                        | 0             | 0                                      |
| 2        | 1                        | 0             | 1                                      |
| 3        | 20                       | 0             | 20                                     |
| 4        | 300                      | 1             | 299                                    |
| 5        | 4000                     | 30            | 3970                                   |
| 6        | 50000                    | 599           | 49401                                  |
| 7        | 600000                   | 9960          | 590040                                 |
| 8        | 7000000                  | 149001        | 6850999                                |

Original Question:
I'm trying to find the number of times the number '13' is repeated in an n-digit number.

For example:
For a 2 digit number, the answer is 0 because 13 is present only once and it's not repeated.
For a 3 digit number, the answer is also 0 because your only possibilities are _ 13 or 13_. You'd need at least 4 digits to see 13 more than once.
For 4 digits, the only possibility is 1313, and in this example I would count this as 1 repetition. (I am not trying to count the number of times that 13 appears which would be 2 for 1313, I just want how many times it can be repeated).
For 5 digits, you can have 1313_ or 13_13 or _1313. For this, I can fill each _ with 10 possibilities for a total of 10+10+10 = 30. In this case, I am allowing 0 to be the first digit, meaning I would like to count 01313 as part of the 5 digit number.
After 5 digits is where I get stuck. I wrote a program to give me the answers but I don't understand how to mathematically obtain them:

6 digits: 599
7 digits: 9960
8 digits: 149001

I see a trend that for 4 digits, you subtract 1 (where the answer is 600-1). For 8 digits, you add 1 (ans = 149000 +1), and I'm guessing that trend keeps repeating but I don't understand why that is.
Could someone please explain how to work this out? Thank you!

Best Answer

If your ultimate goal is to count the number of length-$n$ strings that contain 13 at least once, counting the number of repeats is not going to help; it is strictly harder.

Instead, let $a_n$ be the number of length-$n$ strings that don't contain 13 at all. There is a recurrence $$a_n = 10 a_{n-1} - a_{n-2}$$ justified as follows: to any of the $a_{n-1}$ strings of length $n-1$ with no 13, we may append any of $10$ digits, except for $a_{n-2}$ cases in which the result is a string ending in 13 (but with no other occurrences of 13 in it).

Together with the base cases $a_1 = 10$ and $a_2 = 99$, this gives a shifted version of the OEIS sequence A004189. From there, or from standard tricks for linear recurrences, we can find $$a_n = \frac{(5 + 2\sqrt 6)^{n+1} - (5-2\sqrt 6)^{n+1}}{4 \sqrt 6}.$$

The number of length-$n$ strings that do contain 13 at least once, then, is given by $10^n - a_n$.

If you still want to count the number of "repeat occurrences of 13" (that is, the number of times over all length-$n$ strings that 13 appears in a string not for the first time), then this can be done in terms of $a_n$; it won't help us find $a_n$.

The total number of 13's that appear in these strings is $(n-1)10^{n-2}$: there are $n-1$ places we could put a 13, and $10^{n-2}$ places to choose all the other digits. This counts a string with $k$ occurrences of 13 $k$ times; we want to count it $k-1$ times. So we may subtract the previously found $10^n - a_n$ to get the formula $$ (n-1)10^{n-2} - 10^n + a_n. $$

Related Question