На какую наибольшую степень числа 3 может делиться сумма?

[gipokrat]

В четвёртом туре матрегаты 2005-2006 учебного года девятиклассникам предлагалась следующая задача:

Цитата:

На какую наибольшую степень числа 3 может делиться сумма вида $1!+2!+3!+\dots +n!$?

Мне кажется, что на четвёртую степень. К примеру, сумма факториалов первых семи натуральных чисел равна 5913, следовательно, делится на 81, но не делится на 243.
Однако официальный ответ на задачу звучит чуточку иначе:

Цитата:

Ответ: на третью степень числа 3.

Вот ссылка на этот ответ: https://view.officeapps.live.com/op/vie ... BROWSELINK (задача 4.3).
Если загуглить условие нашей задачи, то легко увидеть, что тот же самый ответ фигурирует ещё в нескольких местах, например, здесь: https://earthz.ru/solves/Zadacha-po-matematike-1435 .
Мой же ответ не фигурирует пока нигде. Что с ним не так? Будьте добры, помогите разобраться. Заранее благодарю!

[mihaild]

Скорее всего изначально кто-то обсчитался, а дальше в других местах переписали с этой ошибкой.

[gris]

Проблема интересная. Но gipokrat по обыкновению закидывает простенькую приманку с желанием увести в сопредельные пространства, где без лоцмана заблудишься.
Речь идёт о последовательности сумм факториалов, которую я по простоте посчитал с помощью
f=1;s=1;for( n=2,N, f*=n;s+=f;... [1,3,9,33...]
Наверняка есть в соответствующей энциклопедии. Интересно посмотреть на делимость членов последовательности на различные числа. ТС привёл некоторые метода остановки поиска. Можно ограничится делимостью на простые числа. На 2 и 5 очевидно ничего не делится. На 3 делятся все члены, начиная со второго. Дальше надо считать. На 11 тоже делятся 4-тый, 8-ой и 10-тый и далее везде. На 7 ничего не делится.
А вот потом 17, 23, 29, 37, 41, 43... некоторые по 2 раза. 163 три раза, 467 четыре раза, 1303 пять раз. В бесконечность никто не сваливается. Есть ли такой делитель? Много интереснейших загадок.

wrest, я всё обдумываю вашу подсказку по действиям с числами в их символьном представлении. Спасибо.

[Shadow]

mihaild в сообщении #1700634 писал(а):

Скорее всего изначально кто-то обсчитался

ТС мог бы процитировать полное решение:

Цитата:

Ответ: на третью степень числа $3$.

Обозначим данную сумму $S_n$. Заметим, что $S_7 = 5913$ и это число делится на $3^3 = 27$. При меньших значениях $n$ или при $n = 8 S_n$ не делится на $27: S_1 = 1; S_2 = 3; S_3 = 9; S_4 = 33; S_5 = 153; S_6 = 873; S_8 = 46233$. Если $k\ge 9$, то $k!$ включает в себя произведение $3\times 6 \times 9$, поэтому делится на $27$.

Таким образом, при $n\ge 9 получим: $S_n = S_7 + 8! + 9! + \ldots$ В этой сумме одно из слагаемых не делится на $27$, а остальные – делятся, поэтому такая сумма не делится на $27.$

Автор не заметил, что $5913$ делится на $3^4$

[gris]

Я всё-таки немножко посчитал и воспарил в ужас восторга. Это же надо — оперировать с суммами факториалов от 1 до 80000. Сотни тысяч цифр! А ведь надо это дело хранить, да ещё на делимость проверять. Как всё это делается?
А с делимостью не очень хороршо:)
Короче, я решил отыскать первое появление простого числа, на которое делится ровно i факториальных сумм. А заодно найти простые числа, на которые делятся бесконечное число сумм. Это 3 и 11, а есть ли ещё такое число — неизвестно. Оно должно делиться на сумму факториалов до своего предыдущего (не обязательно простого).
А вот табличка. Число повторов, первое простое число, на которое делится ровно столько сумм факториалов, эти крайние факториалы.
0 2
1 17: [5]
2 37: [24,29]
3 163: [17,32,87]
4 467: [8,44,159,177]
5 1303: [212,242,337,872,1158]
6 20123 [5528,6800,7464,8225,10146,13944]
7 14081: [2962,3314,4566,5661,6928,9324,9690]
С точным числом повторов от одного до четырёх простачков много, а вот больше пяти повторов встречаются крайне редко. Вот ситуация от 70000 до 80000:
75167 5
75403 5
77419 6
78539 5
Надеюсь, ТС некоторое развитие темы не сочтёт за её захват