4. The number $a_{n}$ is formed by writing down the first n consecutive natural numbers in sequence, for example, $a_{13}=12345678910111213$. Determine how many numbers divisible by 24 are among the numbers $a_{1}, a_{2}, \ldots, a_{10000}$.
SOLUTION. A natural number is divisible by 24 if and only if it is simultaneously (and relatively prime) divisible by the numbers 3 and 8. For the digit sum of a natural number $k$, let's denote it as $S(k)$. The number $a_{n}$ is divisible by three if and only if its digit sum, i.e., the number $S(1)+S(2)+\ldots+S(n)$, is divisible by three. The remainder of this sum when divided by three depends only on the remainders (when divided by three) of the individual addends $S(k)$. Since the number $S(k)$ gives the same remainder as the number $k$ when divided by three (see introductory problem 1), the numbers $S(1), S(4), S(7), \ldots$ give a remainder of 1, the numbers $S(2), S(5), S(8), \ldots$ give a remainder of 2, and the numbers $S(3), S(6), S(9), \ldots$ give a remainder of 0. Therefore, for example, the number $S\left(a_{14}\right)$, i.e., the sum $S(1)+S(2)+\ldots+S(14)$, gives the same remainder when divided by three as the sum

$$
(1+2+0)+(1+2+0)+(1+2+0)+(1+2+0)+1+2 \text{. }
$$

From the grouped triples, we can easily see that this sum is divisible by three. Since the sum $S(3 k-2)+S(3 k-1)+S(3 k)$ is divisible by three for every natural $k$, we can similarly group each sum

$$
S(1)+S(2)+\ldots+S(n)
$$

and determine that its remainder when divided by three

- is 1 if $n=3 k-2$;
- is 0 if $n=3 k-1$ or $n=3 k$.

The numbers $a_{n}$ are therefore divisible by three if and only if $n$ is of the form $3 k$ or $3 k-1$ $(k=1,2, \ldots)$.

Now let's analyze when the numbers $a_{n}$ will also be divisible by eight. A natural number is divisible by eight if and only if the last three digits of its decimal representation are divisible by eight. Our considerations will depend on the number of digits in the number $n$:

- At least three-digit $n$. For such $n$, $a_{n}$ is divisible by eight if and only if $n$ is divisible by eight.

Since the remainders of the numbers $a_{n}$ when divided by three repeat every three, the remainders when divided by eight repeat every eight numbers $a_{n}$, the remainders when divided by 24 will repeat after the least common multiple of these periods, i.e., every twenty-four. For three-digit $n$, we can easily determine that the numbers of the form $104+24 k$ and $120+24 k$ (where $n$ must be divisible by eight and give a remainder of two or zero when divided by three) satisfy the condition in the problem. Up to 10000, we have 413 numbers of the form $104+24 k\left(413=\left\lfloor\frac{1}{24}(10000-104)\right\rfloor+1\right)$ and 412 numbers of the form $120+24 k$.

- Two-digit $n$. For $a_{n}$ to be divisible by eight, it must be divisible by four. The divisibility by four is determined by the last two digits, so $a_{n}$ will be divisible by four precisely for those $a_{n}$ for which $n$ is divisible by four. The number $n-1$ is then odd, so $a_{n-1}$ is also an odd number, and the number $100 a_{n-1}$ gives a remainder of four when divided by eight. Then the number $a_{n}=100 a_{n-1}+n$ will be divisible by eight if and only if $n$ also gives a remainder of four when divided by eight, i.e., it is of the form $8 k+4$. Together with the condition for divisibility by three, we get that the two-digit numbers $n$ that satisfy the condition have (as above) a period of 24 and are of the form $n=12+24 k$ and $n=20+24 k, k \in\{0,1,2,3\}$. Up to one hundred, we have $4+4=8$ numbers.
- One-digit $n$. We can easily determine that among all even numbers $a_{n}$ for $n \leqq 8$, only $a_{6}=123456$ satisfies the condition.

In total, 834 numbers satisfy the condition.

GUIDING PROBLEMS: