# Closed form of finite sum involving the floor function

The sum $$\sum_{k=1}^{p^x-1} \left\lfloor \frac{kx}{p^x} \right\rfloor$$ has stumped me. I don't even know where I would begin. I suppose that starting with the abstraction $$\sum_{k=1}^{f(x)-1} \left\lfloor \frac{kx}{f(x)} \right\rfloor$$ may help, but I still don't know where to begin. I've looked at similar questions, but I still have had no luck solving this problem.

• You can use \left and \right to resize all kinds of brackets, including /lfloor and \rfloor. I went ahead and did that for you, hope you don't mind :) Oct 29 '19 at 23:29
• Are there any assumptions on $p$ or $x$? Mathematica is not giving a closed-form. Oct 29 '19 at 23:30
• are $x$ and $p$ integers o reals ? Oct 29 '19 at 23:32
• @G Cab @Math1000 yeah, one can assume that x, p are integers. Oct 30 '19 at 13:32

If $$x , p^x$$ are integral, then you can use the interesting identity \eqalign{ & \sum\limits_{0\, \le \,k\, \le \,m - 1} {\left\lfloor {{{nk + x} \over m}} \right\rfloor } = \sum\limits_{0\, \le \,k\, \le \,n - 1} {\left\lfloor {{{mk + x} \over n}} \right\rfloor } \quad \left| \matrix{ \;{\rm integer }m > 0 \hfill \cr \;{\rm integer }n \hfill \cr \;{\rm real }x \hfill \cr} \right. = \cr & = \gcd (m,n)\left\lfloor {{x \over {\gcd (m,n)}}} \right\rfloor + {{\left( {m - 1} \right)\left( {n - 1} \right)} \over 2} + {{\gcd (m,n) - 1} \over 2} \cr}