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.

  • $\begingroup$ 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 :) $\endgroup$
    – Math1000
    Oct 29 '19 at 23:29
  • $\begingroup$ Are there any assumptions on $p$ or $x$? Mathematica is not giving a closed-form. $\endgroup$
    – Math1000
    Oct 29 '19 at 23:30
  • $\begingroup$ are $x$ and $p$ integers o reals ? $\endgroup$
    – G Cab
    Oct 29 '19 at 23:32
  • $\begingroup$ @G Cab @Math1000 yeah, one can assume that x, p are integers. $\endgroup$ 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} $$

The demonstration is a bit involved, and you can find it in the renowned "Concrete Mathematics" at pag. 94.


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.