# Sums of consecutive odd integers, positive or negative

While supervising a student competition, my colleague and I ran across an interesting problem. Deobfuscated, it boils down to this

Given a limit value $M$, which integers in the range $1,\dotsc,M-1$ can be represented as a sum of consecutive odd numbers or their negatives, starting at $1$?

The requirement is: represent a number in the above range as $$\sum_{i=0}^L(\pm)(2i + 1)$$ for some upper limit value $L$. We also have the restriction that each prefix sum must be in $1,\dotsc,M-1$, namely $$1\le\sum_{i=0}^k(\pm)(2i + 1)< M$$ for all $0\le k \le L$.

For example, if $M = 17$ we can have sums $1, 2, 4, 7, 9, 11, 16$, since, for example $11=1+3+5-7+9$.

We conjecture that for $M\ge 50$ [Edit: was 46, but I missed some cases], any target sum $1\le s< M$ is possible, which brings me to the questions

1. Is this conjecture true?
2. If so, what does the proof look like?
3. Is this a tired old chestnut that we should have known?
• Do the individual odd numbers you're adding or subtracting need to be each no greater than $M$? – John Nov 13 '14 at 22:26
• Yes, because at each step the prefix sum property assures us that the sum so far is in $[1, M-1]$. That being the case, adding a number $M-1$ or greater would push you out of range. – Rick Decker Nov 14 '14 at 0:48
• I've edited the question to explain it in more detail. I hope it clarifies things. – Rick Decker Nov 14 '14 at 0:55
• By "prefix sum" do you mean "partial sum?" – Akiva Weinberger Nov 14 '14 at 1:02
• @columbus8myhw. Sure. – Rick Decker Nov 14 '14 at 1:05

I'm not sure if I got the question since you should be able to make more numbers with $M=17$ for example $3=1-3+5$ but since I don't have enough rep to ask I'll just post an answer and if I'm answering some different problem you'll let me know and I'll fix it :)

I would argue that this is a tired old chestnut since you are effectively just looking at how far away numbers are from squares. Although it has a pleasant twist to it.

So basically since the squares you have access too are $1,4,9, \dots 484$ since the highest number you get to use is $45$. You have to make sure that all numbers from $1$ to $46$ are atleast $r<90$ smaller than one of our squares where $r$ is an even number. This means that we only need to worry about elleven squares since $11^{2}=121<46+90<144=12^{2}$.

OK so lets construct a method that finds the smallest bigger square than some number with an even distance. Right off the bat we notice:

$1$, Square
$-1+3=2$, $r=2$
$1-3+5=3$, $r=6$
$1+3 = 4$, Square
$1-3+5-7+9= -1+3+5+7-9=5$, $r=20$ Should be $r=4$ but that is not possible!

that when our $r$ has a power of two we will need to turn as many plusses into minuses as the power*, this means that we will need more numbers and that our $k$ will grow large. Since the largest number we're allowed to use is $45$ our $k$ can not grow larger than $22$, how big a $k$ do we need for the $r$ that has the largest power of two in our sequence?

(* When you change one plus into minus you change the sum by $2j$ where j is the variable you changed the symbol on. If you need to change the sum by $j=2^{y}*p$ then you need to change $y$ plusses.)

Since $x^{2}$ is a convex fucntion it is evident - if we ignore the power of two rule we discovered for a second - that $r$ is the biggest right after a square since then it has the longest way to go to the next square. This means that we need to look at the odd numbers from $27$ to $45$ and the even numbers from $38$ to $46$ and find the highest power of two on the way to $49$ (whose sum has $7$ terms) and $64$ (whose sum has $8$ terms) respectively. $$49-27 = 22 < 32 \\ 64-38 = 26 < 32$$ The lowest number that produces the highest power of two is therefore $49-16=33$. To create 33 we need to change 4 plus signs that will lower the sum by atleast $2\cdot 4^{2}=32$. So we need a higher square, the next square has $r=81-33=48$ which means we just need to change the signs on $3,\; 5,\; 7$ and $9$ to accomplish our goal.

So that shows that the sums are possible for $46$. What is the lowest possible $M$?

Well since $x^{2}$ is convex we're basically trying to find when this first starts to happen and then it should be true for every $M>M_{0}$. From our earlier example we can see that we will need to atleast try for $M=9$.

$6$, $r=10$
$7$, $r=2$
$8$, $r=8$ doesn't work so we need $r=28$ the sequence is $1+3-5+7-9+11$.

So now we need to go to $M=11$

$9$, Square
$10$, $r=6$
$11$, $r=14$

So I'd guess $M=11$ is the smallest $M$.

• "For example, if M=17 we can have sums 1,2,4,7,9,11,16, since, for example 11=1+3+5−7+9" Since you could ignore the 1+3+5+7+9 = 25 > M sum I assume that you just need to be able to build all the numbers from 1 and to M you don't need all the possible sums to be in that range (then this is quite clearly impossible). – Pawnda Nov 14 '14 at 3:02
• $1-3+5$ violates the condition that all partial (prefix) sums need to lie in the range $1\leqslant \sum_{i=0}^k \pm(2i+1) < M$, the second partial sum $1-3 = -2 < 1$ is out of range. The first time you can possibly use $-(2i+1)$ is at $i = 3$, when $1+3+5-7 = 2 \geqslant 1$. – Daniel Fischer Nov 14 '14 at 11:21
• Ah ok I thought you could pick the plusses and minuses for each k so since k=3 there and the end result is within range its allowed. For k=2 I would pick in a different way to satisfy the rule etc. Ok I'll change this when I get time – Pawnda Nov 14 '14 at 11:42
• For example, if $M\ge 10$ you could have $2=1+3+5-7$ and if $M\ge 36$ you could also have $2=1+3+5+7+9-11+13-15+17-19+21-23+25-27+29-31+33-35$ – Rick Decker Nov 14 '14 at 19:43