На какую наибольшую степень числа 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
Надеюсь, ТС некоторое развитие темы не сочтёт за её захват
+++ Досчитал до стапятидесяти тысяч. Ничего больше нескольких пятёрок

[waxtep]

gris в сообщении #1700792 писал(а):

А заодно найти простые числа, на которые делятся бесконечное число сумм. Это 3 и 11, а есть ли ещё такое число — неизвестно

Кажется, должны быть ещё, но очень редко; моя дохлая машинка досчитала до 2944133, нету. Можно пробовать строить смелые гипотезы, например, что следующее такое число близко к несколько раз взятому факториалу предыдущего; впрочем, простые, ближайшие с обеих сторон к 2×11!,3×11! не подходят. Еще предлагаю называть такие числа (даже если их всего два) "шлемоблещущими", κορῠθαίολος. Таким образом, $\kappa_1=3,\kappa_2=11,\kappa_3>2944133$, если существует

-- 10.09.2025, 02:03 --

На всякий случай, я сразу делал все по модулю, это позволяет иметь дело только с маленькими числами и ни черта не хранить. По крайней мере, при поиске шлемоблещущих:

1. fsum(p)={my(an=Mod(2,p),sn=an); 
2. for(k=3,p-2, 
3. an=an*k; 
4. sn=sn+an; 
5. ); 
6. return(sn) 
7. }; 
8.  
9. fssrc(p,q)={ 
10. for(cnt=1,q, 
11. p=nextprime(p+1); 
12. fs=fsum(p); 
13. if(fs==0,return(p)); 
14. \\print([p,fsum(p)]); 
15. ); 
16. return([p,fs]) 
17. }; 

[Dmitriy40]

waxtep
Написал вашу процедуру fsum() на асме (показываю только вычислительную часть):

Используется синтаксис ASM

                mov     EBX,EAX                 ;p
                mov     EDX,2                   ;an
                mov     ESI,EDX                 ;sn
                mov     ECX,3+1                 ;k+1
.cycle:         dec     ECX
                mov     EAX,EDX
                mul     ECX                     ;\
                div     EBX                     ; > умножение по модулю
                add     ESI,EDX                 ;sn
                mov     EAX,ESI                 ;\
                sub     EAX,EBX                 ; > это сумма по модулю
                cmovnc  ESI,EAX                 ;/
                add     ECX,2
                cmp     ECX,EBX
                jc      .cycle

Ссылка на исполняемый файл fsum.exe (2КБ) в облаке: https://cloud.mail.ru/public/BaUi/C4oV1F4Fv
Использование в PARI (разумеется файл должен быть в текущей папке или доступен по path):
fs=extern(strexpand("fsum.exe ",p," 2>nul"));
Вернёт целое число по модулю p.
В stderr пишется время работы (без учёта времени вызова), можно запустить с нужным параметром просто fsum.exe в консоли и посмотреть, пример:
C:\>fsum.exe 1000000007
571737250
Time: 9.283s
C:\>fsum.exe 4294967291
3637729884
Time: 38.081s
Если аргумент не число (причём и запятая и точка завершают число) или меньше $4$ или больше $2^{32}-1$ (это ограничение ради скорости), то выдаёт $-1$ в качестве результата (время при этом не показывается ибо нулевое).

До 3e6 досчиталось за 1ч28м44с. Чем больше простое число, тем больше выигрыш времени по сравнению с PARI.

[gris]

Вот дело пошло. Жаль, что ТС где-то побоку задаёт задачи, а эту тему забросил. А я вот продолжаю считать. Меня же интересует не бесконечное число делимостей, а хотя бы 8. Вот, скажем, последние находки с ровно шестью и семью делимостями:
110603: [2988,6321,10455,56115,79863,90440]
131783: [4484,13736,43733,74821,80070,110191]
141121: [3091,35804,83684,109451,120560,138319]
141161: [3308,9840,39740,52272,75911,76410,76760]
То есть s(3308)%141161=0 и т.п.

+++ wrest, вы как всегда правы! Только 3 и 11 исключаем. Они в разнос пошли.

[mihaild]

А что считаем? Число $n < p$, таких что сумма первых $n$ факториалов делится на $p$? (понятно что начиная с $p!$, либо все делятся, либо все не делятся)

[wrest]

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

А что считаем?

Я так понял что ищут разное.
waxtep ищет такие $p$, что существует бесконечное количество $n$ таких, что $s(n)$ делятся на $p$ и пока нашел двоих: $p=3;p=11$
gris отвлекся от бесконечности и ищет такие $p$, на которые делятся хотя бы $m=8$ различных $s(n)$ Пока таких те же обидва $p=3;p=11$
Но у gris нашлось несколько (больше двух) $p$ на которые делятся хотя бы $m=3,4,5,6,7$ различных $s(n)$ что и даёт ему надежду на отыскание $p$ для которых $m=8$

... где $s(n)=\sum \limits _{k=1}^{n}k!$

[mihaild]

wrest в сообщении #1701276 писал(а):

и ищет такие $p$, на которые делятся хотя бы 8 различных $s(n)$

435037, если не набажил.

[Dmitriy40]

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

435037, если не набажил.

Подтверждаю (выводятся длиной не менее 6, до 1e6):

C:\>gp64 -q fsumn.gp
14081: [2962, 3314, 4566, 5661, 6928, 9324, 9690], len=7
20123: [5528, 6800, 7464, 8225, 10146, 13944], len=6
77419: [16872, 32401, 37553, 38978, 57286, 62380], len=6
110603: [2988, 6321, 10455, 56115, 79863, 90440], len=6
131783: [4484, 13736, 43733, 74821, 80070, 110191], len=6
141121: [3091, 35804, 83684, 109451, 120560, 138319], len=6
141161: [3308, 9840, 39740, 52272, 75911, 76410, 76760], len=7
146681: [6585, 13546, 79620, 82958, 94975, 102009], len=6
218131: [7707, 12992, 25852, 42076, 106939, 116262], len=6
227603: [66224, 111092, 169068, 169134, 183163, 212586], len=6
243671: [45371, 57809, 130096, 137764, 167643, 191639], len=6
306991: [76182, 125338, 188478, 214044, 259610, 284226], len=6
320153: [3816, 13503, 123861, 234726, 242267, 289644], len=6
326983: [3165, 62092, 194380, 254958, 292265, 293717], len=6
327479: [17139, 34623, 128835, 139216, 177771, 206222], len=6
383291: [15156, 40281, 72983, 164798, 215334, 242231, 330412], len=7
435037: [19572, 87011, 145571, 168530, 182255, 277075, 397463, 431120], len=8
435653: [97979, 259744, 261123, 311527, 341147, 345515], len=6
464939: [83039, 233530, 250987, 268310, 318639, 389596], len=6
500369: [40810, 128128, 141244, 211673, 456593, 498548], len=6
578311: [33273, 141936, 205251, 270239, 313630, 406338], len=6
638621: [162725, 286662, 328067, 418515, 557402, 637507], len=6
640411: [33455, 232259, 240682, 529421, 602501, 620509], len=6
674419: [193, 300826, 345708, 346889, 412327, 614771], len=6
686563: [78137, 446175, 536337, 609762, 632499, 654505], len=6
730901: [50610, 408947, 411204, 448085, 676079, 709491], len=6
746167: [50442, 136418, 215358, 444560, 522949, 635864], len=6
781069: [177028, 443520, 558592, 593344, 602200, 634602], len=6
806177: [60955, 215032, 269540, 413677, 427366, 471871, 592106], len=7
817169: [391317, 402146, 447370, 575167, 576307, 647041, 724639], len=7
836471: [19285, 202427, 415352, 584655, 644270, 664636], len=6
853007: [148806, 357344, 467955, 481553, 530210, 657724], len=6
883279: [22776, 226884, 230113, 396885, 445826, 825696], len=6
892973: [407207, 517354, 674226, 692192, 698270, 803108], len=6
904801: [297950, 311508, 549170, 718422, 795671, 828088], len=6
908249: [62085, 563141, 679510, 718408, 840394, 853550], len=6
917869: [7423, 379179, 504563, 604753, 634474, 762521], len=6
954851: [256270, 279553, 316334, 403819, 476956, 889165], len=6
958667: [11462, 76170, 82072, 309268, 412308, 821336], len=6
961451: [14330, 101143, 306468, 382897, 802313, 957833], len=6
969083: [274237, 389154, 502680, 754623, 867632, 968949], len=6
992357: [41150, 68280, 78260, 514000, 734128, 755331], len=6

Считалось 22 минуты.

-- 10.09.2025, 18:27 --

gris
Исполняемый файл fsumn.exe (2.5КБ): https://cloud.mail.ru/public/BedN/BTw4Y4Wib
Пример запуска:
C:\>fsumn.exe 435037
[19572,87011,145571,168530,182255,277075,397463,431120]
Time: 0.017s
Использование в PARI для получения строк выше:
fs=extern(strexpand("fsumn.exe ",p," 2>nul"));
#fs>5 && print(p,": ",fs,", len=",#fs);

[mihaild]

($p$, $|\{n < p | s(n) \equiv 0 \pmod p\}|$, $s(n) \equiv 0 \pmod p$), для первых 125000 простых чисел, если второй компонент кортежа $\geq 7$ или третий истинен. Считалось 45 минут непонятно на чем.

3 1 True
11 3 True
14081 7 False
141161 7 False
383291 7 False
435037 8 False
806177 7 False
817169 7 False
1106201 7 False
1338793 7 False
1493683 7 False

https://colab.research.google.com/drive ... sp=sharing

-- 10.09.2025, 17:41 --

Еще две восьмерки нашлось: 1685221, 1733999.

[Dmitriy40]

gris
Нашёл и девятку:
5171293: [569974,1175400,1281722,1587966,2246209,3850593,3932647,4346646,4792742], len=9

Покажу уж и восьмёрки (все найденные до 1e7, в том числе и mihaild):
435037: [19572,87011,145571,168530,182255,277075,397463,431120], len=8
1685221: [271862,501613,718301,771512,1123715,1169666,1172266,1684429], len=8
1733999: [5268,448113,687843,910436,1337719,1453043,1511082,1686130], len=8
4357567: [712364,1014510,1184773,2336906,2430433,2589773,2944369,3174574], len=8
4357781: [638461,652412,892349,1285551,1698184,2548692,2840935,3159420], len=8
7760647: [950026,1117231,1154924,1448798,4639200,4979593,6015452,6836423], len=8
8191217: [2242273,2724259,3480131,5081027,5143172,7077337,7455847,7540475], len=8
9318581: [245125,631721,2262266,3776506,5993171,6519771,6905732,8200879], len=8

Семёрок найдено 51шт.

[gris]

Спасибо! Теперь можно шестёрки не искать, а только семёрки, восьмёрки, девятки и так далее. Это, конечно, мне не по силам
Dmitriy40, почему в Энциклопедии нет этих замечательных чисел?