Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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). –  Pam Aug 20 at 23:32
1  
@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. –  Steven Stadnicki Aug 20 at 23:45
1  
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$ –  Joshua Biderman Aug 20 at 23:48

Hint:

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

Unless... ?

share|improve this answer
    
hmmm, unless 2M+1 is a multiple of h. –  Pam Aug 20 at 23:59
1  
@Pam preciselly! –  Darth Geek Aug 21 at 0:00
    
The sum becomes $$\sum_{h|2M+1} 1$$ i.e. it's the amount of divisors of $2M+1$ lower than $M$ –  Darth Geek Aug 21 at 0:02
    
Thank you all. Very instructive! –  Pam Aug 21 at 0:20
1  
@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. –  Darth Geek Aug 21 at 0:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.