Consider the following sequence $1234567891011121314 . . . 9999899999100000$, how many times the block “2016” appears?

Question

Consider the following sequence $1234567891011121314 . . . 9999899999100000$, how many times the block "$2016$" appears?

My try: Easily we can find $...$$2015$ $2016$ $2017$$...$ as our first block, after that we can see this kind of block $\;$ $...1201612017...$ (this repeats 9 times changing the first digit of $12016$ with the numbers $1$ to $9$

Ex: $12016,22016 ...$ = $9$ blocks

And the same thing happens with $20161,20162...$ changing the last digit = $9$ blocks

So $1+9+9=19$ blocks found by me with brute force.

Are there more blocks or just these and i'm missing something?

In the case I missed some blocks (very likely), is there some algebraic or elegant way to find them?

Answer 1

This is more of a rewrite of Brian Tung's answer, since I haven't generated any computer code to find these, but I figure this is ever so slightly more elegant:

The two things to simplify are:

• The numbers in order never appear with a leading "0", and
• The numbers rotate where 2016 can start for each length of digits.

In every case, we just look at two forms for the number of digits adjacent and see where 2016 appears, and rotate the possible wildcard locations. Whatever digit leads in this rotation, it can't be a 0, which eliminates a few edges. 2017 also doesn't appear between digits, like in "9991000", because it doesn't start with a 9.

First off, "2016" contains 4 digits. If we are looking at the sequence before we hit "1000", we would want 2016 to appear in a subsequence like "abcabd". However, every digit in 2016 is distinct, so it could only appear at the end as "cabd". This can't work, since the "a" digit is a first digit, so a = 0 would mean we don't have 3 digits. A similar sort of argument will work with 3, 2, and 1 digit numbers.

For the 6 digit numbers, we can see 2016 isn't a part of 100000. This leaves the case of 4 and 5 digit repetitions.

For 4 digits, we have the form "abcdabc". 2016 appears as "abcd", "bcda", and "cdab". "dabc" is out, because that would make a = 0 which is a leading digit. We have three instances where 2016 appears in the 4 digit numbers then. Note I am not including the last character of the second number, since that just double counts the very first "abcd". That pattern continues throughout.

For 5 digits, we have a free digit, which we could call X, because 2016 is one digit short. We need to fill "abcdeabcd". Let's put the X after 2016, which I believe is doable without loss of generality. Then we compare the letter strings to "2016X"

Then "abcde" = 2016X gives 10 more, "bcdea" gives 9 more since X cannot be 0 here, "cdeab" gives 10 more, and "deabc" another 10. "eabcd" is illegal because a always is 0, so this is the total count of 39 for 5 digits.

Adding up both cases, 39 + 3 = 42 appearances.

This type of argument would also generalize to different numbers, especially ones without zeroes in the decimal expansion. We can see with some algebra that for a k digit number, not starting with 9 and without zeroes in its decimal representation, in the first 10^n numbers we expect about:

$$ \sum_{d = k}^n d * \lfloor{10^{d - k}}\rfloor $$

many appearances, where d is the current number of digits we are considering in the argument here.

So we would expect 50 + 4 = 54 for a number like 1234, but because of the zeroes for numbers like 2016, things get a little complicated. It seems at a glance that you just subtract 11 and 1 from the cases for 2016, so it might be you subtract multiples of these when you add zeroes in. Not sure. I'd also have to think a little bit harder about the cases that involved the edges of digits: numbers like "9100" that appear at "991000" and every higher power.

But hopefully that gives a little insight. Listing the occurrences in order seems to get a result with less understanding than even some half-baked arguments here.

Answer 2

The sequence $2016$ appears $42$ times in all (verified by computer search, I'm afraid):

• $1620, 1621$
• $2016$
• $6201, 6202$
• $16X20, 16X21$ ($X = 0$ to $9$)
• $2016X$ ($X = 0$ to $9$)
• $X2016$ ($X = 1$ to $9$)
• $6X201, 6X202$ ($X = 0$ to $9$)

I can't think of any really elegant way of doing this.

Answer 3

Yes, you are missing some. For example, there are $6201\ 6202$ and $66201\ 66202$

Answer 4

We split cases:

• Case 1: 2016 in one "number".
• Case 2: 201 in one number, 6 in the next.
• Case 3: 20 in one number, 16 in the next

(2 in one number and 016 in the next cannot occur)

Case 1:

We split cases again:

• Sub-case 1: $2016$, there is $1$ possibility.
• Sub-case 2: $?2016$, there are $9$ possibilities.
• Sub-case 3: $2016?$, there are $10$ possibilities.

So in this case there are $20$ possibilities.

Case 2:

The "first" number and the "next" one both start with $6$, and the next one ends with $202$. So we split cases again:

• Sub-case 1: $6201$, there is $1$ possibility.
• Sub-case 2: $6?201$, there are $10$ possibilities.

Therefore, there are $11$ possibilities in this case.

Case 3:

Both numbers start with $16$, the "next" number ends with $21$. We split cases of the "first" number:

• Sub-case 1: $1620$, there is $1$ possibility.
• Sub-case 2: $16?20$, there are $10$ possibilities.

Therefore, there are $11$ possibilities in this case.

The number of blocks of $2016$ is therefore the sum of the numbers of possibilities: $$20+11+11=42\text.$$