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
    Commented Sep 21, 2021 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
    Commented Sep 21, 2021 at 11:03

2 Answers 2

1
$\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
    Commented Sep 21, 2021 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
    Commented Sep 21, 2021 at 12:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .