Highest Power of 2 Dividing Numerator of Sum of Odd Reciprocals

From ProofWiki
Jump to navigation Jump to search

Theorem

Let:

$S = \dfrac p q = \ds \sum_{k \mathop = 1}^n \dfrac 1 {2 k - 1}$

where $\dfrac p q$ is the canonical form of $S$.

Let $n = 2^k m$ where $m$ is odd.


Then the largest power of $2$ that divides $p$ is $2^{2 k}$.


Proof

We have that:

$\ds \sum_{k \mathop = 1}^n \dfrac 1 {2 k - 1} = \sum_{i \mathop = 0}^{M - 1} \paren {\dfrac 1 {i \times 2^{r + 1} + 1} + \dfrac 1 {i \times 2^{r + 1} + 3} + \cdots + \dfrac 1 {\paren {i + 1} \times 2^{r + 1} - 1} }$

where $k = 2^r M$ where $M$ is odd.

Collect the $r$ terms in the parenthesis on the right hand side of the $i$th term under a single common denominator $P_i$.

Then the resulting numerators will each consist of $2^r$ terms, each of the form $\dfrac {P_i} {R_i}$, where $R_i$ is a distinct odd residue of $2^{r + 1}$.

These $\dfrac {P_i} {R_i}$ must themselves also be the distinct odd residue of $2^{r + 1}$, in some order.


The odd residues of $2^{r + 1}$ are:

$1, 3, 5, \dots, 2^{r + 1} - 1$

Their sum is:

\(\ds \) \(\) \(\ds 1 + 3 + \cdots + \paren {2^{r + 1} - 1}\)
\(\ds \) \(=\) \(\ds \frac {\paren {1 + 2^{r + 1} - 1} 2^r} 2\) Sum of Arithmetic Sequence
\(\ds \) \(=\) \(\ds 2^{2 r}\)


Thus each of the $M$ numerators is of the form $2^{2 r} M_i$, where $M_i$ is odd.

Thus the numerator of $S$ is in the form $2^{2 r} Q$ where $Q$ is the sum of an odd number of odd terms.

Therefore $Q$ is itself odd.

Hence, if $2^r$ is the largest power of $2$ which divides $k$, then $2^{2 r}$ is the largest power of $2$ dividing the numerator of $S$.

$\blacksquare$


Historical Note

This result was posed as an elementary problem by John Lewis Selfridge in March $1960$: Problems for Solution: E1406-E1410 (American Mathematical Monthly Vol. 67: p. 290)  www.jstor.org/stable/2309704.

He notes that H.S. Shapiro and D.L. Slotnick leave the problem unsolved in an article in a $1959$ commercial publication, where they suggest that:

an estimate [of this] power of $2$ ... seems in general to be a difficult number theoretic problem.


In the event, $7$ contributors are reported as having submitted a solution, of which that by D.L. Silverman was the one published.


Among the solvers was Donald E. Knuth, who included the problem as an exercise of difficulty level $M33$ in his The Art of Computer Programming: Volume 1: Fundamental Algorithms.


Sources