3
$\begingroup$

In this earlier question, the OP asks for a proof of the statement

Every natural number not of the form $2^k$ for some natural number k can be written as the sum of two or more consecutive positive integers.

The proofs in that answer are all interesting and valid. However, I was curious as to why powers of two cannot be formed this way. It would seem that since powers of two and addition are involved that there would be some proof that powers of two cannot be expressed as the sum of two or more consecutive positive integers that works by exploring properties of addition of binary numbers. That is, we could prove this result by showing that binary addition of multiple consecutive integers, as an algorithm, is incapable of producing a power of two.

Does anyone know of such a proof or how to get started with one? I honestly can't figure out how such a proof would work, but I feel that if one exists it's likely to be extremely interesting.

Thanks!

  • 0
    So, the more general rule is that if the sum of k>1 consecutive integers is divisible by $2^j$, then either $k$ must be divisible by $2^{j+1}$ or the sum of the first and last of the consecutive integers must be divisible by $2^{j+1}$. I bet you can use binary math to prove this by induction on $j$.2011-12-27

3 Answers 3

4

Well, the sum of $k>1$ consecutive positive integers starting at $n$ is $\frac{(n+k)^2+n+k}{2}-\frac{n^2+n}{2}=\frac{2kn+k^2+k}{2} = \frac{k}{2}(2n+k+1)$. If we want to get $2^m$ we must have $2^{m+1}=k(2n+k+1)$ so $k=2^j$ for some $j\in\mathbb{N}$. But then $2^m = 2^jn+2^{2j-1}+2^{j-1}$. If we write this as a binary expansion, the last $j$ digits of $2^j$ must be $0$, the last $2j-1\geq j$ digits of $2^jn$ must be $0$, while $2^{j-1}$ has a $1$ in the last $j-1$ digits, and so the sum has a $1$ in the last $j-1$ digits. Since $2^m$ must be at least $2^{2j-1}\geq2^j$, this cannot be the case, so $2^m$ cannot be written as the sum of $k>1$ consecutive positive integers.

  • 0
    The formula you begin with is not quite correct. That formula is for a sum starting at n+1. It ends up working out, because we just choose n as one less. I only mention it because I hate for such a fine proof to be marred by an inaccuracy. Nice proof!2016-11-16
1

Lemma: The sum of $k\geq 1$ consecutive positive integers is divisible by $2^j$ (ends in $j$ zeros in binary) only if either $k$ is divisible by $2^{j+1}$ or the first and last elements of the consecutive integers ia divisible by $2^{j+1}$.

Proof: Induction on $j$. For $j=0$, this means that given $k$ consecutive integers, either $k$ is even or the sum of the first and last term in the sequence is even. Basically, this means that given an odd number of consecutive binary numbers, the last binary digit of the first and last number in the sequence must be the same. I hope that is obvious.

Assume true for $j$. Now if $k$ consecutive integers add up to a multiple of $2^{j+1}$, then they add up to a multiple of $2^j$, so either $k$ is divisible by $2^{j+1}$ or the first and last element of the sequence add up to a multiple of $2^{j+1}$.

If $k$ is divisible by $2^{j+1}$, then, for any particular set of possible $j+1$ digits, there are $\frac k{2^{j+1}}$ numbers in the sequence that end in those $j+1$ digits. But we can pair off most of these equivalence classes, by pairing off the class ending in $d\pmod {2^{j+1}}$ with the class ending in $2^{j+1}-d \pmod {2^{j+1}}$ and thus, you are left with the numbers that end in $j$ or $j+1$ zeros. The ones that end in $j+1$ zeroes don't affect the last $j+1$ digits, so the sum of the numbers end in $j+1$ zeros if and only if the sum of the $\frac{k}{2^{j+1}}$ numbers that have last $j+1$ digits $10000...0$ add up to a multiple of $2^{j+1}$, which is only possible if there are an even number of them. So $\frac{k}{2^{j+1}}$ must be even, so $k$ is divisible by $2^{j+2}$

On the other hand, if the first and last number add up to a multiple of $2^{j+1}$ then $k$ must be odd, and we can pair all of the elements with it's opposite number in the sequence, except for the middle number in the sequence. But that middle number is always half of the sum of the first and last number, so for the entire sum to end in $j+1$ zeros, the average of the first and last must end in $j+1$ zeros, so the sum of the first and last must end in $j+2$ zeros.

From this lemma, you can easily prove your theorem, because $k>1$ consecutive positive integers cannot add up to $2^j$ because otherwise either the first and last add up to a multiple of $2^{j+1}$ so the largest must be bigger than $2^j$, or $k$ is divisible than $2^{j+1}$ which would make the sum far greater than $2^{j+1}$.

1

Modified from this answer to a supposedly equivalent question.

No power of $2$ can be written as the sum of more than one consecutive, positive integer.

Note that, being the sum of $n-m+1$ integers whose average is $\frac12(n+m)$, $ \sum_{k=m}^nk=\frac12(m+n)(n-m+1)\tag{1} $ Furthermore, since $(n+m)-(n-m+1)=2m-1$, either $n+m$ is odd or $n-m+1$ is.

Suppose $2^j$ can be written as the sum in $(1)$. then we have $ 2^{j+1}=(m+n)(n-m+1)\tag{2} $ Since the only odd factor of a power of $2$ is $1$, $(2)$ implies that either $n-m+1=1$ or $m+n=1$.

If $n-m+1=1$, then there is only one term in $(1)$.

If all the terms in $(2)$ are positive, then $m,n\ge1$. Thus, $n+m\ge2$.

Thus, we can have neither $n-m+1=1$ nor $m+n=1$. Therefore, $2^j$ cannot be written as the sum of more than one consecutive, positive integer..