Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
    
I can't see an obvious proof using binary representations. The sum of $k$ consecutive integers starting with $n$ is $kn+\frac{k(k-1)}2$ so if $m$ can be written in this form, then $2m = k(2n+k-1)$. If $m$ is a power of $2$, then both $k$ and $2n+k-1$ must be powers of two, but they have different parities, so one of them must be $1$. Presumably, $k>1$, so $2n+k-1=1$ or $2n+k=2$. Since $k\geq 2$, this means that $n\leq 0$. So essentially, the problem is unique factorizataion of powers of $2$. –  Thomas Andrews Dec 27 '11 at 18:25
    
Actually the sum formula given by Arturo Magidin in the original question can be considered as a property of binary addition. It is very essential that the integers are consecutive, so you cannot just use properties of the addition of two arbitrary integers. –  Listing Dec 27 '11 at 18:26
    
@Listing He's asking for a specific type of proof of part of the problem, not just for a proof, so not really a duplicate. –  Thomas Andrews Dec 27 '11 at 18:26
    
@Listing- I did read the answers. Perhaps I am missing something here, but I don't see how the answer that you've referred me to uses properties of arithmetic of binary numbers; it seems to just be using standard arithmetic and divisibility techniques. I guess what I'm looking for is some analysis of how the addition of consecutive values in binary would cause the result not to be a power of two. Does that make any sense? Again, I already understand why the result is true, but I was hoping to gain perspective on why it was true by looking at binary arithmetic. –  templatetypedef Dec 27 '11 at 18:26
show 1 more comment

3 Answers 3

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.

share|improve this answer
    
It's not always divisible by $k$ if $k$ is even. You can only say $2^{m+1}$ is divisible by $k$, but that is enough. –  Thomas Andrews Dec 27 '11 at 18:36
    
@ThomasAndrews Fixed –  Alex Becker Dec 27 '11 at 18:43
    
+1 Well done! Instead of talking about binary expansions you can also argue that in the sum $2^jn+2^{2j-1}+2^{j-1}$ the two first terms are divisible by $2^j$ (because $j\ge1$), but the last one is not. Therefore the sum is of the form $2^{j-1}\ell$ with $\ell>2$ odd. IOW use the non-archimedean triangle inequality of the $2$-adic metric. –  Jyrki Lahtonen Dec 27 '11 at 19:48
add comment

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}$.

share|improve this answer
add comment

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..

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.