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.

Given two numbers $M$ and $N$, Let $q_i$ be the integer part of $\frac{iN}{M}$. What is $$ \sum_{i=0}^{M-1} q_i? $$ The Sum is obviously can be calculated in $O(M)$. Can this be done in less time, maybe $O(1)$ if there exists some simpler reduced expression?

share|improve this question
Why is it $O(M)$? If $N=M$, the sum is $M(M-1)/2$, which is $O(M^2)$. –  user1551 Mar 9 '13 at 8:23
Is there any special relationship between M and N? For example, if M and N are coprime, I believe the calculation could be done in O(1) time. –  Mike Mar 9 '13 at 8:36
I edited... It was sum to calculated in O(M) –  Shashwat Kumar Mar 9 '13 at 8:37
I got the solution. It is O(log n*log m). sum = (NM - N - M + gcd(N, M))/2) –  Shashwat Kumar Mar 9 '13 at 8:38
@Shashwat If you have an answer, write it down. wait for comment for a while and then accept it yourself. –  achille hui Mar 9 '13 at 8:51
add comment

1 Answer

Assuming M and N are integers, I believe your formula can be rewritten as

$$\sum\limits_{i=0}^{M-1}\frac{iN}M-\frac1M\sum\limits_{i=0}^{M-1}iN \mod M.$$

The first sum is an arithmetic sum. There is a formula for arithmetic sums that can be done in O(1) time. The second summation is the sum of remainders from the division. If $N$ and $M$ are coprime, no 2 of these remainders are the same, reducing the sum to $\sum\limits_{i=0}^{M-1}i$, which is another arithmetic sum.

I'm sure the formula can be adjusted in the case where $M$ and $N$ are not coprime. Maybe someone else can fill in the blanks while I'm getting some sleep, assuming you're interested. My guess is if you know nothing about M and N, your computation time will stem from performing the Euclidean algorithm to obtain a gcd, which I believe should be less than linear time.

share|improve this answer
add comment

Your Answer


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.