Can you give me some hints on solving following summation. Is there any theory concerning the following summation?

$p$ is a prime number > 2

$$\sum_{s=2}^{p-1}\left(\left\lfloor\frac{p}{s}\right\rfloor s\right)$$

I tried to apply the following formula

$$\left\lfloor \frac{x}{y}\right\rfloor = \frac{x - (x\mod{y})}{y}.$$

But it does not get me anything useful.

Thanks in Advance.


This sum is very similar to a well-known formula for the sum of sum of divisors function OEIS A024916:

$$\sum_{k=1}^n \sigma(k) = \sum_{k=1}^n \left\lfloor \frac n k\right\rfloor k$$

which can be computed in sub-linear time as I show here.

This formula is easily seen by writing out all the divisors in a triangular grid. Example for $n=6$:

\begin{matrix} k=1: & 1 \\ k=2: & 1 & 2 \\ k=3: & 1 & & 3 \\ k=4: & 1 & 2 & & 4 \\ k=5: & 1 & & & & 5 \\ k=6: & 1 & 2 & 3 & & & 6 \end{matrix}

Summing columnwise it is easy to see for every value $k$ from $1$ to $n$, $k$ will appear $\lfloor n / k \rfloor$ times, so we add $\left\lfloor n/k\right\rfloor k$ to the total sum. For your particular case we leave out $k=1$ and $k=n$.

  • $\begingroup$ Your last sentence of "For your particular case we leave out $k = 1$ and $k = n$" is misleading. At least to me, it implies leaving these $2$ terms out of both sides of the equation you provide, but this is true only when $2n = \sigma\left(n\right) + 1$. This happens relatively rarely, such as for all powers of $2$, but, more pertinently for the OP, it never happens for any prime $> 2$. Of course, a specific answer to the OP's question is to use something like $\sum_{k=1}^n \sigma\left(k\right) - 2n$. $\endgroup$ – John Omielan Jan 16 at 23:18

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.