1
$\begingroup$

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.
$\endgroup$
2
  • $\begingroup$ Have you looked for the sequence in the OEIS? $\endgroup$
    – jjagmath
    Sep 21 '21 at 10:40
  • $\begingroup$ No, I did a check now but can't find it. I'll have to dig a little more. $\endgroup$
    – Pascal
    Sep 21 '21 at 11:03
0
$\begingroup$

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$.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ This proves that the period is a divisor of $\varphi(t+1)$ $\endgroup$
    – jjagmath
    Sep 21 '21 at 11:31
  • $\begingroup$ 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. $\endgroup$
    – Pascal
    Sep 21 '21 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.