Highest Power of 2 Dividing Numerator of Sum of Odd Reciprocals
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
- 1960: J. Selfridge and D.L. Silverman: E1408: The Highest Power of $2$ in the Numerator of $\sum_{i \mathop = 1}^k 1 / \paren {2 i - 1}$ (Amer. Math. Monthly Vol. 67: pp. 924 – 925) www.jstor.org/stable/2309478
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.7$: Harmonic Numbers: Exercise $18$