# Formulas for $\sum_{x=1}^{n}\Big\{\frac{x^q}{n}\Big\}$

Consider sum: $$$$S_q(n) = \sum_{x=1}^{n}\Big\{ \frac{x^q}{n} \Big\}$$$$ 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: $$$$\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)$$$$

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: $$$$\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)$$$$

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

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

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

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

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

Question:

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

• 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! Apr 27 '21 at 11:46