Computing Floor Sum quickly

Правка en8, от ComboGirl, 2022-02-14 12:50:31

I want to 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$$$ in log time.

I know that when $$$\gcd(m,n) = 1,$$$ this can be viewed as counting lattice points under the line $$$y=\frac{m}{n} x$$$ and by symmetry it's equal to half the number of lattice points contained in the entire rectangle (because there's no lattice points exactly on the line segment between $$$(0,0)$$$ and $$$(m,n)$$$ as $$$\gcd(m,n) = 1$$$), so the sum is equal to $$$\frac{(m-1)(n-1)}{2}.$$$ (When $$$m,n$$$ are prime, the sum is a nice lemma that is used in a proof of Quadratic Reciprocity.)

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? Is there a way to generalize the lattice point counting approach for relatively prime $$$m,n$$$?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский ComboGirl 2022-02-14 12:50:31 36
en7 Английский ComboGirl 2022-02-14 12:43:19 84
en6 Английский ComboGirl 2022-02-14 12:41:27 13 Tiny change: 'ht\rfloor$\n\nI know' -> 'ht\rfloor$ in log time.\n\nI know'
en5 Английский ComboGirl 2022-02-14 12:40:42 0 (published)
en4 Английский ComboGirl 2022-02-14 12:39:43 110
en3 Английский ComboGirl 2022-02-14 12:38:02 350
en2 Английский ComboGirl 2022-02-14 12:34:40 63 Tiny change: 'tion to this?' -> 'tion to that?'
en1 Английский ComboGirl 2022-02-14 12:33:30 314 Initial revision (saved to drafts)