3
$\begingroup$

I have the sum ( $M$ is any integer $> 1$ ):

$$ \sum_{h = 1}^{M}\left(\,\left\lfloor\, 2M + 1 \over h\,\right\rfloor -\left\lfloor\, 2M \over h\,\right\rfloor\,\right) $$

and looking for a way to simplify it. In the sense of either finding a simple closed form or a good approximation for M large. This resembles my previous question involving the divisor summatory function. However, now this is different because the sum extends to $M$ (not $2M$) and now we have differences with at the numerators an odd number and the previous even number (which is $2$ times $M$), I was hoping some good simplification could be found in this case. The first terms are integers, so they pose no problems, I was mainly looking for some way to simplify the other differences.

A tight upper bound would also be useful ( as well as references to similar well-known $\mbox{formulas )}$.

$\endgroup$
2
$\begingroup$

I think you might have a typo based on your explanation. As written, this difference is nonzero if and only if $h|2M+1$. In that case the difference is $1$. Thus This is simply the number of divisors of $2M+1$, which is a well studied problem. Specifically, if $f(M)$ is the sum that you are requesting, then $f(M)=\sigma_0(2M+1)-1$.

$\endgroup$
3
  • $\begingroup$ Thank you Joshua. It seems I have copied it correctly: what typo do you mean ? Based on my computations it can take various values different from 0 and 1, like 1,2,3,4,5 (hmm, unless I am missing something). $\endgroup$ – Pam Aug 20 '14 at 23:32
  • 1
    $\begingroup$ @pam you're missing something, I think - the two quantities you're taking the floor of are only $\frac1h\leq 1$ apart, whatever the value of $h$, so the difference between their floors will never be more than 1. $\endgroup$ – Steven Stadnicki Aug 20 '14 at 23:45
  • 1
    $\begingroup$ Pam, my presumption of a typo is because you imply that you know about the divisor function and expect this sum to be related to the divisor function nontrivially. Since this is just one less than the divisor function, I assumed that you made a typo. It most definitely cannot take values other than $0$ and $1$ because the difference, without the floors, is always $\frac{1}{h}\leq 1$ $\endgroup$ – Stella Biderman Aug 20 '14 at 23:48
2
$\begingroup$

Hint:

$$\left\lfloor \frac{2M+1}{h}\right\rfloor = \left\lfloor \frac{2M}{h}\right\rfloor$$

Unless... ?

$\endgroup$
4
  • $\begingroup$ hmmm, unless 2M+1 is a multiple of h. $\endgroup$ – Pam Aug 20 '14 at 23:59
  • 1
    $\begingroup$ @Pam preciselly! $\endgroup$ – Darth Geek Aug 21 '14 at 0:00
  • $\begingroup$ The sum becomes $$\sum_{h|2M+1} 1$$ i.e. it's the amount of divisors of $2M+1$ lower than $M$ $\endgroup$ – Darth Geek Aug 21 '14 at 0:02
  • 1
    $\begingroup$ @Pam Note that the only divisor of $2M+1$ higher than $M$ is preciselly $2M+1$ so the sum becomes the amount of the divisors of $2M+1$ minus one. $\endgroup$ – Darth Geek Aug 21 '14 at 0:27

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.