Задание 16. Информатика. Статград 2023-1-1
Алгоритм вычисления значения функции \(F(n)\), где \(n\) — целое неотрицательное число, задан следующими соотношениями:
\(F(0) = 0;\)
\(F(n) = F(n-1) + n.\)
Укажите количество таких чисел \(n\) из интервала \( 237~567~892 \leq n \leq 1~134~567~004\), для которых \(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\) числа \(237~567~892\) равен \(1\).
Python
len(range(237_567_892, 1_134_567_005, 3))
Ответ: \(298999705\)