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 Answers 2

Reset to default
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, 2014 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, 2014 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, 2014 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, 2014 at 23:59
  • 1
    $\begingroup$ @Pam preciselly! $\endgroup$
    – Darth Geek
    Aug 21, 2014 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, 2014 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, 2014 at 0:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .