Computing Floor Sum quickly

Revision en2, by ComboGirl, 2022-02-14 12:34:40

Compute the sum $$$\left\lfloor \frac{m}{n} \right\rfloor + \left\lfloor \frac{2m}{n} \right\rfloor + \cdots + \left\lfloor \frac{(n-1)m}{n} \right\rfloor = \sum_{k=1}^{n-1} \left\lfloor \frac{km}{n} \right\rfloor$$$

I'm told that there's a way to think about this that is similar to the Euclidean Algorithm for gcd. Is there a connection to that?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English ComboGirl 2022-02-14 12:50:31 36
en7 English ComboGirl 2022-02-14 12:43:19 84
en6 English ComboGirl 2022-02-14 12:41:27 13 Tiny change: 'ht\rfloor$\n\nI know' -> 'ht\rfloor$ in log time.\n\nI know'
en5 English ComboGirl 2022-02-14 12:40:42 0 (published)
en4 English ComboGirl 2022-02-14 12:39:43 110
en3 English ComboGirl 2022-02-14 12:38:02 350
en2 English ComboGirl 2022-02-14 12:34:40 63 Tiny change: 'tion to this?' -> 'tion to that?'
en1 English ComboGirl 2022-02-14 12:33:30 314 Initial revision (saved to drafts)