Задание 16. Информатика. Статград 2023-1-2
Алгоритм вычисления значения функции \(F(n)\), где \(n\) — целое неотрицательное число, задан следующими соотношениями:
\(F(0) = 0;\)
\(F(n) = F(n-1) + n.\)
Укажите количество таких чисел \(n\) из интервала \( 765~432~010 \leq n \leq 1~542~613~234\), для которых \(F(n)\) не делится без остатка на \(3\).
Решение:
Очевидно, что \(F(n)\) — это сумма всех чисел от \(1\) до \(n\). Как известно, остаток суммы равен сумме по модулю остатков остатков. Для последовательности чисел $$ 1, \, 2, \, 3, \, 4, \, 5, \,\ldots $$ последовательность их остатков при делении на \(3\) будет $$ 1, \, 2, \, 0, \, 1, \, 2, \, \ldots . $$ Поэтому, последовательность остатков сумм всех чисел от \(1\) до \(n\) при делении на \(3\) будет $$ 1, \, 0, \, 0, \, 1, \, 0, \, \ldots. $$ Таким образом, сумма чисел от \(1\) до \(n\) не делится на \(3\) только , если остаток от деления на \(3\) числа \(n\) равен \(1\). Заметим также, что остаток от деления на \(3\) числа \(765~432~010\) равен \(1\).
Python
len(range(765_432_010, 1_542_613_235, 3))
Ответ: \(259060409\)