Числовая последовательность

[Ktina]

Последовательность $(a_n)_{n\in\mathbb N_0}$ задана формулой

$$ \begin{cases} a_0=4 \\ a_{n+1}=3a_n+4 \end{cases} $$

Сколько из первых 2011 членов этой последовательности делится нацело на 2002?

[Руст]

$a_n=2*(3^{n+1}-1)$ всегда делится на 4. На 7 делится, если $n+1$ делится на 6, на 11 делится если $n+1$ делится на 5, на 13 делится если $n+1$ делится на 3. Соответственно $a_n$ делится на 2002 тогда и только тогда, когда $n+1$ делится на 30. Т.е. всего 70 членов.

[Dave]

Ответ: 67.
$2002=2 \cdot 7 \cdot 11 \cdot 13$. Все члены последовательности, очевидно, делятся на 2. Рассматривая остатки от деления на $7, \, 11, \, 13$, получим, что они периодичны с периодами $6, \, 5, \, 3$ соответственно и равны $0$ соответственно для $n=6m+5, \, 5m+4, \, 3m+2$, где $m \in \mathbb N_0$. Значит $a_n$ делится на $2002$ тогда и только тогда, когда $n$ одновременно даёт вышеуказанные остатки $5, \, 4, \, 2$ при делении на $6, \, 5, \, 3$ соответственно. Рассматривая остатки от деления $n$ на $30$, приходим к выводу, что такое возможно только когда $n=30m+29, \, m \in \mathbb N_0$. Среди чисел $\{0,1,2, \ldots, 2010 \}$ таких чисел ровно 67, соответствующих $m$ от $0$ до $66$ (минимальное $m$ равно $29$, максимальное равно $30 \cdot 66 + 29 = 2009$).