На сколько нулей кончается выражение?

[Xenia1996]

Для каждого натурального $m$ найти, на сколько нулей может оканчиваться десятичная запись выражения $1^n+2^n+...+m^n$, где $n$ - натуральное число.

Я смогла решить только для $m$, дающих остатки 1 и 2 при делении на 4, а также для $m=4$.

При $m$, дающих остатки 1 и 2 при делении на 4, сумма содержит нечётное число нечётных чисел, стало быть, ответ будет "только на 0 нулей".

При $m=4$ у меня вышло "только на 0, 1 или 2 нуля". Действительно, при $n=1$ имеем ровно 1 нуль на конце. При $n=3$ имеем ровно 2 нуля на конце. При $n=4$ имеем ровно 0 нулей на конце.
Чтобы получить более двух нулей, сумма должна делиться на 8, но этого не происходит. При $n$ равном 1 и 2 нуль будет ровно один. При $n>2$ замечаем, что $2^n$ и $4^n$ делятся на 8, а $1^n$ всегда единичка, значит $3^n$ должна давать остаток 7 при делении на 8, но, согласно арифметике остатков, $3^n$ может давать лишь остатки 3 и 1 при делении на8.

При остальных $m$ у меня не получается

[Sonic86]

Мдя...
Так, ну найти сумму через числа Бернулли тут видимо не поможет...
Можно через сравнения определять для каждой тройки $m,n,k$ верно ли $10^k|S(m,n)=\sum\limits_{j=1}^{m}j^n$...
Функция $\text{ord}_{10}(S(m,n))$ должна быть, наверное, похожа на $\text{ord}_{10}(x!)$ для зафиксированного $n$.
Это такая формулировка у задачи, или еще какие-то условия есть?

[age]

Xenia1996
При $n=1$ имеем $\sum\limits_{j=1}^m{j}=\dfrac{m(m+1)}{2}$.
Несложно видеть, что возможно любое число нулей (подставьте m = 2000000). То же самое для тройки и выше. Только там будут свои суммы рядов. Формулы сумм здесь:
http://mathworld.wolfram.com/FaulhabersFormula.html

[paha]

age в сообщении #385681 писал(а):

Несложно видеть, что возможно любое число нулей (подставьте m = 2000000). То же самое для тройки и выше. Только там будут свои суммы рядов.

задача не про $n$, а про $m$
:^)))

[age]

Ааааа.. что-то совсем не догнал. Извинтиляюсь.

[Xenia1996]

Sonic86 в сообщении #385619 писал(а):

Мдя...

Это такая формулировка у задачи, или еще какие-то условия есть?

Задачу сама придумала, так что, возможно, переборщила с формулировкой. А натолкнула меня вот эта лёгкая задачка (первая из тех, что там есть): http://www.zaba.ru/cgi-bin/tasks.cgi?to ... bor.9klass

Просто, если решение задачи мне даётся легко, у меня тут же руки чешутся её обобщить (или, как говоривал многоуважаемый Михаил Сергеевич, обобщить)...

[Sonic86]

Эта задача вполне решаемая, но решение громоздкое.
Сначала $\text{ord}_{10}(S(m,n)) = min\{ \text{ord}_2(S(m,n));\text{ord}_5(S(m,n))\}$. Далее считаем каждый показатель отдельно.
Эмпирически я нашел и почти вывел формулу для $\text{ord}_2$:

$$ \left\{ \begin{array}{l} n=1 \Rightarrow \text{ord}_2(S(m,n))=\text{ord}_2(m)+\text{ord}_2(m+1)-1 \\ n>1 \Rightarrow \text{ord}_2(S(m,n))=2^{n \text{mod} 2} \cdot (\text{ord}_2(m)+\text{ord}_2(m+1)-1) \end{array} $$

В общем случае, видимо, для $\text{ord}_p$ следует рассматривать случаи $n \equiv r \pmod{p-1}$ при $0 \leq r < p-1$ с $n>1$ и почему-то отдельно $n=1$ (пока не понял, почему)(в предыдущей формуле я загнал случаи разных вычетов $n$ в одну формулу).

[Sonic86]

Для решения для произвольного простого $p>2$ надо доказать (или опровергнуть!?) следующие соотношения (подобраны эмпирически):

$$(A) \ \text{ord}_p(S(m+p^2,n))=\text{ord}_p(S(m,n))$$

$$(B) \ \text{ord}_p(S(m,n))=\text{ord}_p(S((p^2-1)-(m \text{mod} p^2),n))$$

$$(C) \ \text{ord}_p(S(pm,n))=\text{ord}_p(S(pm-1,n))$$

тут основное соотношение - это (A), остальное чуть облегчает работу. Если (А) верно, то нахождение $\text{ord}_p(S(m,n))$ сводится к нахождению $\text{ord}_p(S(m,n))$ для $1 \leq m \leq \frac{p^2-1}{2}$, взаимно простых с $p$
Помогите доказать! Я не знаю, как ее доказывать!

(длинная и нудная почти вся формула для показателя 5 суммы S(m,n), почти не доказано)

$$\begin{array}{l} 1. \ m \equiv 1;3;8;11;13;16;21;23 \pmod 5^2 \Rightarrow \text{ord}_5(S(m,n))=0 \\ 2. \ m \equiv 2;7;17;22 \pmod 5^2 \Rightarrow \text{ord}_5(S(m,n))=[n \equiv 2 \pmod 4](1+ \text{ord}_5(n)) \\ 3. \ m \equiv 12 \pmod 5^2 \Rightarrow \text{ord}_5(S(m,n))=[n \equiv 0 \pmod 2]+[n \equiv 2 \pmod 4](1+ \text{ord}_5(n)) \\ 4. \ m \equiv 6;18 \pmod 5^2 \Rightarrow \text{ord}_5(S(m,n))=[n \equiv 3 \pmod 4](1+ \text{ord}_5(\text{don't \ know})) \\ 5. \ m \equiv 4;5;9;10;14;15;19;20 \pmod 5^2 \Rightarrow \text{ord}_5(S(m,n))= [n \equiv 1;2 \pmod 4](1+ \text{ord}_5(n)) [n \equiv 3 \pmod 4](2+ \text{ord}_5(n)+\text{ord}_5(n-1)) \end{array}$$

(использована нотация Айверсона из книжки Кнута $P$ истинно $\Rightarrow [P]=1$, $P$ ложно $\Rightarrow [P]=0$)

[TOTAL]

Sonic86 в сообщении #386742 писал(а):

$$(A) \ \text{ord}_p(S(m+p^2,n))=\text{ord}_p(S(m,n))$$

Это означало бы, что $\text{ord}_p(S(m,n))$ ограничено (при фиксированном $n$).
Оцените снизу $\text{ord}_p(S(p^{2k},n))$

[Sonic86]

TOTAL, я затупил , каюсь... (зря эмпирика включил)