Решение. Функция F(n) = F(n – 1) + n возвращает сумму чисел от 1 до n.
Рассмотри начало последовательности:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20...
Заметим, что остаток от деления на 3 будет равен 0 каждое третье число.
Остатки от деления на 3:
1, 2, 0, 1, 2, 0, 1, 2, 0...
Известно, что остаток от деления на 3 суммы остатков от деления чисел на число 3 равен остатку от деления суммы чисел на число 3. Другими словами, остаток суммы остатков равен остатку суммы исходных чисел.
Поэтому последовательность остатков сумм всех чисел от 1 до n при делении на 3 будет:
1, 0, 0, 1, 0, 0, 1, 0, 0...
Таким образом, что F(n) не делится на 3, только если остаток от деления n на 3 равен 1.
Приведём решение Юрия Красильникова на языке Python.
Найдём минимальное число, которое не меньше a и даёт остаток 1 (то есть самое маленькое на отрезке). Это можно сделать, например, по формуле (a + 1)//3 · 3 + 1.
Найдём максимальное число, которое не больше b и даёт остаток 1. Возможная формула (b – 1)//3 · 3 + 1.
Количество таких чисел, очевидно, есть (максимальное-минимальное)//3 + 1.
a,b = 237567892,1134567004
print(((b-1)//3*3-(a+1)//3*3)//3+1)
Поскольку остаток деления числа 237 567 892 на 3 равен единице, то можно привести другое решение.
Приведём другое решение на языке Python.
a,b = 237567892,1134567004
print(len(range((a+1)//3*3, b+1, 3)))
Ответ: 298 999 705.
