Consider sum: \begin{equation} S_q(n) = \sum_{x=1}^{n}\Big\{ \frac{x^q}{n} \Big\} \end{equation} where $\{x\}$ is fractional part of $x$. It's easy to see that $S_{1}(n) = \frac{1}{2}(n-1)$, but already $S_{2}(n)$ looks more complicated. I have some observations about the $S_q(n),\; q > 1$. It is likely that they are false, since I have no proof, but it is still interesting to ask about it here.

Observation 1: If an integer $n = p_{1}^{q_1}\ldots p_{m}^{q_m}$, where $p_i$ are prime numbers of the form $4k+1$, then holds: \begin{equation}\label{eq1} S_{2}(n) = \frac{1}{2}\Big(n- p_{1}^{\big\lfloor \frac{q_1}{2} \big\rfloor}\ldots p_{m}^{\big\lfloor \frac{q_m}{2} \big\rfloor}\Big) \end{equation}

Observation 2: If an integer $n = p_{1}^{q_1}\ldots p_{m}^{q_m}$, where $p_i$ are prime numbers, then for odd $q > 1$ holds: \begin{equation}\label{eq2} S_{q}(n) = \frac{1}{2}\Big(n- p_{1}^{\big\lfloor \frac{1}{2}\big\lfloor q_1 - \frac{2q_1}{q} \big\rfloor + \frac{q_1}{2} \big\rfloor}\ldots p_{m}^{\big\lfloor \frac{1}{2}\big\lfloor q_m - \frac{2q_m}{q} \big\rfloor + \frac{q_m}{2} \big\rfloor}\Big) \end{equation}

I couldn't find any pattern for $S_{2q}(n)$ in general, only some special cases:

\begin{equation} S_{2}(2^k) = \frac{1}{2}(2^k - a_{k+1}) = \frac{1}{2}(2^k-b_{k}) \end{equation} where $a_k$ is the sequence A060482, $k>1$ and $b_k$ is the sequence A136252, $k > 0$.

\begin{equation} S_{2}(3^k) = \frac{1}{2}\Big(3^k - \frac{a_{k+2}}{3}\Big) \end{equation} where $a_k$ is the sequence A060647, $k>0$

\begin{equation} S_{2}(4^k) = \frac{1}{2}(4^k - a_{k+1}) \end{equation} where $a_k$ is the sequence A068156, $k>0$

\begin{equation} S_{4}(2^k) = \frac{1}{2}\Big(2^k - a_{\big\lfloor \frac{k-1}{4} \big\rfloor + 1}\Big) \end{equation} where $a_k$ is the sequence A000225, $k > 0$


Are the formulas in observations 1,2 correct? If the formulas are correct, is there any general pattern for $S_{2q}(n)$?

The code for numerical validation of certain small values


I have a solution when $-1$ is a power of $q$ mod $n$ (which generalizes your observations) and when $n$ is prime and $q$ is 2.

We'll show that if there is a $z$ such that $z^q\equiv -1 \mod n$ where $n=\prod_i p_i^{q_i}$ then: $$S_q(n)= \frac{1}{2} ( n - \prod_i p_i^{q_i-\lceil{ q_i/q }\rceil}) $$

In particular, this is a generalization of both your observations 1 and 2 since $-1$ is a quadratic residue for primes $1 \mod 4$ and for odd $q$, $(-1)^q=-1$.

Let $z$ satisfy $z^q\equiv -1 \mod n$. Let $m_k$ be the number of integers $i$ from $0$ to $n-1$ such that $i^q\equiv k \mod n$.

Note that since $gcd(z^k,n)=gcd(-1,n)=1$ that $gcd(z,n)=1$, so multiplying by $z$ permutes the residues $\mod n$. Therefore, $$\sum_{i=0}^{n-1} \frac{i\cdot m_i}{n}=\sum_{x=1}^n \{\frac{x^q}{n} \} =\sum_{x=1}^n \{\frac{(zx)^q}{n} \} =\sum_{x=1}^n \{\frac{n-x^q}{n} \} =\sum_{i=1}^{n} \frac{(n-i)\cdot m_i}{n} $$ Thus, $$2S_q(n)=\sum_{i=0}^{n-1} \frac{i\cdot m_i}{n}+\sum_{i=1}^{n} \frac{(n-i)\cdot m_i}{n} =\sum_{i=1}^{n-1} m_i=n-m_0$$ We can calculate that $x^q\equiv 0 \mod n$ iff for all $i$, $p_i^{q_i}$ divides $x^q$ iff $\prod_i p_i^{\lceil{q_i/q}\rceil}$ divides $x$. Thus, $m_0 = n/\prod_i p_i^{\lceil{q_i/q}\rceil}$. Putting this together gives the desired $S_q(n)$.

For general $q$,$n$ I suspect the answer is expressible using algebraic number theory. For $q=2$, $n=p$ prime, and $p \equiv 3 \mod 4$. For $p>3$, the Class Number formula simplifies to: $$h(-p)=-\frac{1}{p}\sum_{i=0}^{p-1} i (\frac{i}{p} )$$ Thus, you can express $S_2(p)$ for $p\equiv 3 \mod 4$ and $p>3$ in terms of the Class number for imaginary quadractic field of discriminant $-p$: $$S_2(p)=\frac{p-1}{2}-h(-p)$$

  • $\begingroup$ Eric, It's magnificent! That's just what I was looking for. This shows that the difference between S and 1/2n is about the square root of n. Thank you! $\endgroup$ Apr 27 '21 at 11:46

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.