0
$\begingroup$

I am trying to prove the above question. As I see it this is the statement that needs to be proved: a number $x$ has no odd factors $\iff$ $x$ cannot be formed by a sum of consecutive natural numbers.

First ($\Rightarrow$):

Assume $x$ has no odd factors (i.e., $x = 2^m$ for some $m$). Seeking a contradiction write $$x = k + (k+1) + \cdots + (k+n) = (n+1)k + {n(n+1) \over 2} = {(2k + n)(n+1) \over 2}$$

Now $2k+n$ and $n+1$ are of opposite parity, therefore one of them is odd. You cannot form an odd number without an odd factor, therefore contradiction.

Second ($\Leftarrow$):

Assume $x$ has at least one odd factor. We seek to prove that $x$ can be written as above...This is where I'm stuck

$\endgroup$
  • $\begingroup$ Your question reads "not divisible by" rather than "not expressible as" so you need only to write the odd factor as a sum of consecutive integers - two should do it. $\endgroup$ – Mark Bennet Aug 24 '15 at 20:02
  • $\begingroup$ Fixed thanks @MarkBennet. Could you elaborate on why writing this odd factor as a sum of consecutive integers helps me? As in the comment below I'm having trouble seeing where this gets me. $\endgroup$ – Moderat Aug 24 '15 at 20:13
  • $\begingroup$ Since any odd number is expressible in the manner suggested in the question, and a particular odd number is a factor of $x$, you have that $x$ is "divisible by$ an odd factor. I have put some comments in an answer to explain indicate why you can't use "expressible as" instead. $\endgroup$ – Mark Bennet Aug 24 '15 at 20:19
  • $\begingroup$ @Mark Bennet: Although I don't see a proof yet I still think it's likely that the conjecture with "expressible as" still holds since your methods is not a counter-proof. E.g. to express 14 with your method we would write $x=7 \cdot 2$ and see that since $7>2$ it won't work. But yet $14=2+3+4+5$ is expressable in another way as such a sum... $\endgroup$ – Tintarn Aug 24 '15 at 20:23
  • $\begingroup$ @Tintarn I didn't do even decompositions it is true - I'll make a note $\endgroup$ – Mark Bennet Aug 24 '15 at 20:24
3
$\begingroup$

Just to complete the analysis of this situation, if there is an odd factor, so that $x=(2m+1)a$ then you can write $$x=(a-m)+(a-m+1)+\dots + (a-1)+a+(a+1)+\dots (a+m)$$ which is the sum of $2m+1$ consecutive integers. This can only be done with natural numbers if $m\lt a$ and there will be one such expression for each odd factor. To see whether it is possible choose the smallest odd factor - if it can be done at all, it can be done for that. So that is decomposition into an odd number of terms.

It is also possible to split $x=2ma-m=m(2a-1)$ into an even number of terms as is clear if we write the sum as:

$$(a-m)+(a-m+1)+\dots +a+ \dots +(a+m-1)=2ma-m$$

Again we clearly need the odd factor, and again this only works as an expression in positive integers if $a\gt m$. So we choose the largest odd factor in this case.

Any odd factor greater than $1$ can be expressed as the sum of two consecutive natural numbers.

$\endgroup$
1
$\begingroup$

An odd factor greater than $1$ is of the form $2m+1=m+(m+1)$

$\endgroup$
  • $\begingroup$ Sorry, I'm not sure I understand why writing $x = (m+(m+1)) \cdot 2^\alpha$ (if $x$ has one odd factor) helps me... $\endgroup$ – Moderat Aug 24 '15 at 20:11
  • $\begingroup$ $m+(m+1)$ is the sum of two consecutive integers. By the way, since $x$ can have more than one odd factor, we only know that $x=(m+(m+1))d$, that is, $d$ needn't be a power of two. $\endgroup$ – ajotatxe Aug 24 '15 at 20:21
1
$\begingroup$

Here's my solution. Although it's basically the same construction as in Mark Bennet's solution, I hope I can present some motivation here.

Assume we want to express $x=(2m-1)a$ where $a>0,m>1$ are positive integers.

First, note that $1+2+\dotsc+(2m-1)=m(2m-1)$ is divisble by $(2m-1)$. Set $a-m=d$. Then we obtain that $(d+1)+(d+2)+\dotsc+(d+2m-1)=(2m-1)d+m(2m-1)=a(2m-1)=x$.

Now if $d \ge 0$ this means that we have found a suitable expression.

Assume $d<0$. Then the sum above is basically made of two parts: One with the negative numbers $d+1,d+2,\dotsc,-1$ and one with the positive numbers $1,2,\dotsc,d+2m-1$. Note that $d+2m-1=a+m-1>1$.

Now, if we just cancel out the numbers which occur both with positive and negative sign we get the desired expression.

Writing formally, we then have a sum going from $-d$ to $d+2m-1$ or equivalently from $m-a$ to $a+m-1$.

So, we have a construction for all cases. First, write $x=(2m-1)a$ where $a>0, m>1$. If $a \ge m$ choose $k=a-m+1$ and $n=2m-2$. If $a<m$ choose $k=m-a$ and $n=2a-1$.

$\endgroup$
0
$\begingroup$

An algorithmic approach to finding such a sequence in any particular instance: For any number $c$ other than a power of $2$, $c$ will have at least one odd prime factor. Choose the smallest odd prime factor of $c$, $p_i$. Let $b=\frac{c}{p_i}$. There are $p_i$ consecutive integers from $b-\frac{p_i-1}{2}$ to $b+\frac{p_i-1}{2}$ that sum to $c$. The average value of those integers is just $b$, so the sum is $p_i\cdot b=c$. Note that if $c$ has more than one odd prime factor, there may be several sequences of consecutive integers that sum to $c$.

As mentioned in another answer, an odd number $(d)$ is also the sum of two consecutive integers $\frac{d-1}{2}+\frac{d+1}{2}$. Also you already show that $2^n$ cannot be the sum of consecutive integers. That covers all cases.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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