# (Dis)Prove $u_n(t)=\displaystyle \left(\sum_{i=1}^t i^n \right) \mod (t+1)$

As I was trying to find a generic formula for the sum of the first $$n$$ integers to the power of $$t$$, I found this property that I was able to check from $$t = 1$$ to $$600$$ (for 12 periods). Lets define the sequence:

$$u_n(t)=\displaystyle \left(\sum_{i=1}^t i^n \right) \mod (t+1)$$

It seems that the sequence becomes periodic from $$n = 1$$ or $$n = 2$$, with a period which is defined as $$P(t)=lcm(\{P_i(t)-1\})$$ where $$P_i(t)$$ are the prime factors of $$(t+1)$$ with an exception for $$t = 2^k-1, k>2$$ where the period is $$2$$ and not $$1$$ as given by the formula.

To illustrate and clarify what I try to say, here are some examples:

• $$t=3$$

The first exception, the period is equal to $$2$$:

$$u_0(3)=3,u_1(3)=2,u_2(3)=2,u_3(3)=0,u_4(3)=2,u_5(3)=0,u_6(3)=2,u_7(3)=0$$

• $$t=4$$

The prime factors of $$4+1=5$$ are $$\{5\}$$, then $$scm(\{4\}) = 4$$, hence the period is 4:

$$u_0(4)=4,u_1(4)=0,u_2(4)=0,u_3(4)=0,u_4(4)=4,u_5(4)=0,u_6(4)=0,u_7(4)=0,u_8(4)=4,u_9(4)=0,u_{10}(4)=0,u_{11}(4)=0,u_{12}(4)=4$$

• $$t=9$$

The prime factors of $$9+1=10$$ are $$\{2,5\}$$, then $$scm(\{1,4\}) = 4$$, hence the period is 4:

$$u_0(9)=9,u_1(9)=5,u_2(9)=5,u_3(9)=5,u_4(9)=3,u_5(9)=5,u_6(9)=5,u_7(9)=5,u_8(9)=3,u_9(9)=5,u_{10}(9)=5,u_{11}(9)=5,u_{12}(9)=3$$

• $$t=20$$

The prime factors of $$20+1=21$$ are $$\{3,7\}$$, then $$scm(\{2,6\}) = 6$$, hence the period is 6:

$$u_0(20)=20,u_1(20)=0,u_2(20)=14,u_3(20)=0,u_4(20)=14,u_5(20)=0,u_6(20)=11,u_7(20)=0,u_8(20)=14,u_9(20)=0,u_{10}(20)=14,u_{11}(20)=0,u_{12}(20)=11,u_{12}(20)=0,u_{14}(20)=14,u_{15}(20)=0,u_{16}(20)=14,u_{17}(20)=0,u_{18}(20)=11$$

• $$t=384$$

The prime factors of $$384+1=385$$ are $$\{5,7,11\}$$, then $$scm(\{4,6,10\}) = 60$$, hence the period is 60, I won't display the sequence, but it is true at least up to $$n = 720$$.

Is this property true, and where can I find a proof?

[note] If you are interested, here is the program (written in Erlang) I used to verify this. It is not complete as it does not check if the period could be smaller than the one I test (I did the verification "visually")

-module(powser).

-export([start/1,start/2,start/3]).

start(To) -> start(1,To,2).
start(From,To) -> start(From,To,2).

-spec start(pos_integer(),pos_integer(),pos_integer()) -> done.
%% From: the first power to be tested
%% To: the last power to be tested
%% Cycles: How many periods should be tested
start(From,From,Cycles) when is_integer(From), From > 0,
is_integer(Cycles), Cycles > 1 ->
analyze(From,Cycles),
done;
start(From,To,Cycles) when is_integer(From), is_integer(To), is_integer(Cycles),
To > From, From > 0 , Cycles > 1 ->
analyze(From,Cycles),
start(From+1,To,Cycles).

%%%%%%%%%%%%%%%% private %%%%%%%%%%%%%

intPow(X,I) when is_integer(X), is_integer(I), I >= 0->
intPow(X,I,1).
intPow(_,0,R) -> R;
intPow(X,I,R) when (I band 1) == 1 ->
intPow((X*X), I bsr 1, (R * X));
intPow(X,I,R) ->
intPow((X*X), I bsr 1, R).

decomp(N) when is_integer(N), (N > 0) ->
lists:reverse(decomp(N,[],2)).

decomp(N,R,I) when I*I > N -> [N|R];
decomp(N,R,I) when (N rem I) =:= 0 -> decomp(N div I,[I|R],I);
decomp(N,R,2) -> decomp(N,R,3);
decomp(N,R,I) -> decomp(N,R,I+2).

gcd(A, B) when A < B -> gcd(B, A);
gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, A rem B).

scm(A,B) -> A*B div gcd(A,B).

scm([A]) ->
A;
scm([A,B|T]) ->
scm([scm(A,B)|T]).

sumPow(N,M) -> sumPow(N,M,0).

sumPow(1,_,R) -> R+1;
sumPow(X,M,R) -> sumPow(X-1,M,R+intPow(X,M)).

analyze(N,Cycles) ->
Factors = lists:usort([X-1 || X <- decomp(N+1)]),
D = case {N,Factors} of
{1,_} -> 1; %% exception in exception for t = 1 (k=1)
{_,[1]} -> 2; %% exception for t = 2^k-1 with k > 1
_ -> scm(Factors)
end,
Len = Cycles*D+3, % the period starts for n = 0,1 or 2, so take some margin for the check
R = lists:map(fun(X) -> sumPow(N,X) rem (N+1) end,lists:seq(1,Len)),
{Ok,Offset,ToPrint} = check(R,D,Cycles,3),
io:format("~p (~p, offset ~p, period ~p) : ~w~n",[N,Ok,Offset,D,ToPrint]).

check(List,_,_,0) -> {false,none,List};
check(List,Period,Cycles,N) ->
Offset = 4-N,
case lists:usort([lists:sublist(List, Offset + X * Period, Period) || X <- lists:seq(0,Cycles-1)]) of
[_] -> {true,Offset-1,lists:sublist(List, 1, Period+Offset-1)};
_ -> check(List,Period,Cycles,N-1)
end.

• Have you looked for the sequence in the OEIS? Commented Sep 21, 2021 at 10:40
• No, I did a check now but can't find it. I'll have to dig a little more. Commented Sep 21, 2021 at 11:03

The property can be confirmed with the help of some classical number theory.

It follows from the Chinese remainder theorem that $$u_n$$ is periodic for $$t+1=p_1^{e_1}p_2^{e_2} \cdots p_k^{e_k}$$ if and only if for each of the prime power factors $$p_j^{e_j}$$ the $$u_n$$ sequence is periodic for $$t+1=p_j^{e_j}$$, so it makes sense to explore the behavior of these special sequences.

For $$t+1=2^e$$ it can be shown that with $$n\ge2$$ and $$e\ge2$$ one has $$u_n(t)=2^{e-1}$$ for every even $$n$$ and $$u_n(t)=0$$ for every odd $$n$$. This follows from the fact that for $$t+1=2$$ all terms of the sequence have value $$1$$, combined with the observation that, modulo $$2^e$$, $$\sum_{i=1}^{2^e-1} i^n =\sum_{i=1}^{2^{e-1}-1} i^n+ 2^{(e-1)n}+\sum_{i=1}^{2^e-1} (2^e-i)^n{\rm \ where\ } 2^{(e-1)n}\equiv 0{\rm \ and\ }\sum_{i=1}^{2^e-1} (2^e-i)^n\equiv(-1)^n\sum_{i=1}^{2^{e-1}-1} i^n{\rm,}$$ which implies that $$u_n(2^e-1)=2u_n(2^{e-1}-1)$$ for even $$n$$ and $$u_n(2^e-1)=0$$ for odd $$n$$.

For $$t+1=p^e$$ where $$p$$ is an odd prime, it can be shown that with $$n\ge1$$ and $$e\ge1$$ one has $$u_n(t)=(p-1)p^{e-1}$$ for $$n=k(p-1)$$ and $$u_n(t)=0$$ for all other values of $$n$$:

For $$e=1$$ there is a primitive root $$r$$ with the property that, modulo $$p$$, $$\ r^{p-1}\equiv 1$$ and the lower powers of $$r$$ correspond with the other values between $$1$$ and $$p$$, so $$\sum_{i=1}^{p-1} i^n\equiv \sum_{j=1}^{p-1} r^{jn}$$. If $$n$$ is a multiple of $$p-1$$ then all terms are equivalent with $$1$$ and $$u_n(p-1)=p-1$$. For other $$n$$ one has $$(1-r^n)\sum_{j=1}^{p-1} r^{jn}\equiv r^n-r^{pn}\equiv 0$$ and therefore $$u_n(p-1)=0$$.

The derivation of the values for $$t+1=p^e$$ from those for $$t+1=p^{e-1}$$ starts with noting that the terms of the sum with $$i=kp$$ can be ignored because, modulo $$p^e$$, $$\ \sum_{j=1}^{p^{e-1}-1} (pj)^n=p^n\sum_{j=1}^{p^{e-1}-1} j^n\equiv p^n u_n(p^{e-1}-1)$$, which is trivially equivalent with zero when $$u_n(p^{e-1}-1)=0$$. If $$u_n(p^{e-1}-1)\ne0$$ then $$u_n(p^{e-1}-1)=(p-1)p^{e-2}$$ because $$n=kp$$, so $$n\ge p-1\ge 2$$ and it follows that $$p^n\sum_{j=1}^{p^{e-1}-1} j^n$$ is a multiple of $$p^e$$.

For the remaining sum $$\sum_{1\le i\lt p^e,p\not\mid i}i^n$$, modulo $$p^e$$, define $$r=1+p^{e-1}$$ and note that $$r^k\equiv 1+kp^{e-1}$$, so the first $$p$$ powers of $$r$$ are all different and $$r^p\equiv 1$$. Also $$\sum_{k=1}^p r^{nk}\equiv\sum_{k=1}^p 1+nkp^{e-1}\equiv p + np\frac{p+1}2 p^{e-1}\equiv p$$. Now for $$1\le i\le p^{e-1}$$ with $$i\equiv a\not\equiv 0\pmod p$$ one has, modulo $$p^e$$, $$ir^k\equiv i+akp^{e-1}$$, where each $$k$$ with $$1\le k\le p$$ yields a different value,so together these values form the indices for the remaining sum and it follows that $$u_n(p^e-1)\equiv\sum_{1\le i\lt p^e\atop p\not\mid i}i^n\equiv\sum_{1\le i\lt p^{e-1}\atop p\not\mid i}\sum_{k=1}^p (ir^k)^n\equiv \sum_{1\le i\lt p^{e-1}\atop p\not\mid i}i^n\sum_{k=1}^p r^{kn}\equiv pu_n(p^{e-1}-1)$$ Regarding the periodicity of the sequence it may be noted that, except for $$t=2^e-1$$, the only values of $$n$$ where all the involved $$t+1=p_i^{e_i}$$ sequences are non-zero are $$n=k\ lcm_i (p_i-1)$$, so, by the Chinese remainder theorem, these lead to a unique value of the main sequence at these values of $$n$$.

Proving periodicity for a fixed $$t \ge 2$$ is almost trivial. Indeed once you know that $$n \equiv m \pmod{(\varphi (t+1))} \quad \Longrightarrow \quad i^n \equiv i^m \pmod{(t+1)}$$ , where $$\varphi( \cdot )$$ is Euler totient function, then you have that $$n \equiv m \pmod{(\varphi (t+1))} \quad \Longrightarrow \quad u_n(t)=u_m(t)$$ In particular this shows that $$u_n(t)$$ is $$\varphi(t+1)$$-periodic.

• This proves that the period is a divisor of $\varphi(t+1)$ Commented Sep 21, 2021 at 11:31
• Yes, it is exactly what I see, sometimes the period is φ(t+1), most of the time it is a divisor, consistent with the "imply" definition. Commented Sep 21, 2021 at 12:58