# summation of floor function involving prime number

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.

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

• 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$. – John Omielan Jan 16 at 23:18