Donald Knuth Concrete Mathematics Page 94 (Topic Integer Functions Floor Ceiling Sums)

181 Views Asked by At

To summarize, this is deriving the arithmetic progression on page 92 third column.

$\frac{0\mod m}{m} + \frac{n \mod m}{m} + \frac{2n \mod m}{m}... \frac{\left(m - 1\right)n \mod m}{m}$

Now Take a look at this equation on page 94

$d\left(\frac{1}{2}\left(0 + \frac{m - d}{m}\right)\frac{m}{d}\right)$ Where $d = gcd(m,n)$

My question is how did $\frac{m}{d}$ get there?

This is the formula of arithmetic progression

$S_n = \frac{1}{2}\left(a_1 + a_n\right)$

Similarly given on page 93 the progression $0,d,2d... m - d$ The Sum should be

$S_n = \frac{1}{2}\left(\frac{0}{m} + \frac{m - d}{m}\right)$

1

There are 1 best solutions below

0
On BEST ANSWER

Your formula for the sum of an arithmetic progression is wrong: it should be

$$S_n=\frac{a_1+a_n}2\cdot n\;,$$

the average term times the number of terms. In the case in question there are $\frac{m}d$ terms. The terms are

$$\frac0m,\frac{d}m,\frac{2d}m,\dots,\frac{m-d}m\;,$$

where $m-d=\left(\frac{m}d-1\right)d$. Thus, the terms are the numbers $\frac{kd}m$ for $k=0,1,\ldots,\frac{m}d-1$, a total of $\frac{m}d$ terms.