(Another) Solution: Writting year as sums of runs of numbers

The solution of just grinding out of the algebra is fine but it's a bit dull and unintuitive. We can use the discussion at the end of the last post to produce a simple proof with almost no algebra.

What we're going to prove is that the number of sequences of consecutive integers that sum to \(Y\) is equal to twice the number of odd divisors of \(Y\).

First off note that if the sum is positive, then there must be more positive numbers in the sequence than negatives. I'm going to assume it's positive, if it's negative then the procedure works, just with the signs changed.

Next, note that the solutions to the problem always come in pairs. Every sequence of even length has a corresponding sequence of odd length. You can construct one from the other as follows.

If 0 appears in the sequence then you cancel every negative number with it's opposite positive number and remove the zero. Every time you cancel a \(-\) with a \(+\) you remove 2 elements from the sequence, so it stays odd or even. Finally removing the 0 flips from odd to even or vice versa. E.g. $$ -3 + -2 + -1 + 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 $$ becomes $$ 4 + 5 + 6 + 7 $$ 2 slightly non-obvious cases of this are sequences beginning with 0 or 1. They have no negative elements, so you just either add or remove 0 at the start.

Conversely if the sequence does not contain 0, prepend all the numbers from 0 up to the start of the sequence and also prepend their negatives. This does not change the sum but it flips the length from even to odd or vice versa. E.g. $$ 4 + 5 + 6 + 7 $$ becomes $$ -3 + -2 + -1 + 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 $$

So now we just consider the solutions of odd length. If we can show that there is exactly one of those for every odd divisor of \(Y\), we're done. That turns out to be fairly easy.

First, lets say you have an odd length sequence that sums to \(Y\). Since it's odd-length, it must have a middle number, let's say \(n\) and then there are \(k\) numbers before and \(k\) numbers after. The befores and afters go together in pairs. \(n-1\) with \(n+1\), \(n-2\) with \(n+2\) etc. Each of these pairs sums to \(2n\) and there are \(k\) pairs plus a lone \(n\) from the middle giving a total of \((2k+1)n\). So we have that \(Y=(2k+1)d\) and so \(2k+1\) (the length of the sequence) must be an odd divisor of \(Y\). So this shows that any sequence that sums to Y leads to a specific odd divisor of Y.

Conversely given an odd divisor of \(Y\), \(2k+1\) and we set \(n = Y/(2k+1)\) then the sequence of length \(2k+1\) centred on on \(n\) sums to \(Y\). So every odd divisor leads to a sequence of odd-length and we're done.

Solution: Writting year as sums of runs of numbers

It turns out the answer is fairly well known and involves what are known as polite numbers but I hadn't heard of them before.

So in order to solve this, we consider sequences of positive consecutive integers. I've added "positive" in there because sequences that are all negative are just positive sequences with the sign flipped and so are not interesting. Sequences that start negative and go positive are also not interesting as you can a bunch of the numbers will cancel out and you'll be left with a sequence that's purely negative or a purely positive.

There's a well-known formula for the sequences starting at \(1\) and that the formula for triangular numbers: \(1 + 2 + ... + n = n(n+1)/2\). We can use this to get a formula for sequences that don't start at \(1\). The sum \((k+1) + (k+2) + ... + (k+n)\) is just the sum from 1 to n minus the sum from 1 to k. More formally that's \begin{equation}\label{2.1} \begin{split} &{} n(n+1)/2 - k(k+1)/2\\ =& 1/2(n^2+n -k^2 -k)\\ =& 1/2(n^2-k^2 + n -k)\\ =& 1/2((n+k)(n-k) +(n -k))\\ =& 1/2((n+k + 1)(n-k))\\ \end{split} \end{equation}

So now if we want to get a specific number \(Y\) out of that then $$ Y = 1/2((n+k + 1)(n-k)) $$ so $$ 2Y = (n+k + 1)(n-k) $$

Notice that the factors on the right hand side differ by \(2k + 1\) this means that one is always even and one odd and the odd one must be a divisor of \(Y\) (any odd divisor of \(2Y\) must divide \(Y\) also). So every odd divisor, \(d\) of \(Y\) gives us 2 possibilities. Either $$ \begin{split} &n+k+1& = d\\ &n-k& = 2Y/d\\ \end{split} $$ or $$ \begin{split} &{}n+k+1& = 2Y/d\\ &{}n-k& = d\\ \end{split} $$

Solving these for n and k we get either $$ \begin{split} n &= (d-1)/2 + Y/d\\ k &= Y/d - (d + 1)/2\\ \end{split} $$ or $$ \begin{split} n &= (d-1)/2 + Y/d\\ k &= (d - 1)/2 - Y/d\\ \end{split} $$

In both cases \(n\) is the same. The \(k\)s are different and in fact they are almost negatives of each other (add them together and you get \(-1\)). This means that for any odd divisor \(d\) you get exactly two solutions but exactly one of them will have a positive \(k\). \(n\) is positive if and only f \(d\) is positive.

So in fact for any \(Y\) there are exactly as many solutions as there are positive odd divisors of \(Y\). In the case of 2016 we have factors \(2016 = 3.3.7.32\) $$ \begin{split} d=1 &: 2016 = 2016\\ d=3 &: 2016 = 671+672+673\\ d=7 &: 2016 = 285+286+...+291\\ d=9 &: 2016 = 220+221+...+228\\ d=21 &: 2016 = 86+87+...+106\\ d=63 &: 2016 = 1+2+3+...+63\\ \end{split} $$ and for \(2015 =5*13*31\) we have $$ \begin{split} d=1 &: 2015 = 2015\\ d=5 &: 2015 = 401 + 402 + ... + 405\\ d=13 &: 2015 = 149 + 150 + ... + 161\\ d=31 &: 2015 = 50 + 51 + 80\\ d=65 &: 2015 = 2 + 3 + ... + 63\\ d=155 &: 2015 = 65 + 66 + ... + 90\\ d=403 &: 2015 = 197 + 198 + ... + 206\\ d=2015 &: 2015 = 1007 + 1008\\ \end{split} $$

In the 2015 example, the divisors 65, 155, 403 and 2015 are big enough that k becomes negative and we need to switch to the second solution. This doesn't happen at all for 2016 - the odd divisors never get very big because a lot of 2016 is kind of locked up inside the 32.

When the sequence comes from the first solution, it has exactly \(d\) elements and is centered around \(Y/d\). This makes sense intuitively, you can sum the sequence by adding the first and last, the second and second last, etc each contributes \(2Y/d\) and finally the middle one gives you one more for a total of \(dY/ = Y\).

When the sequence comes from the second solution, that doesn't work but instead of switching to solution 2, we can stick with solution 1 and accept a negative \(k\). Then we get a \(d\)-element sequence that sums to \(Y\) $$ \begin{split} d=65 &: 2015 = -1 + 0 + 1 + 2 + 3 + ... + 63\\ d=155 &: 2015 = -64 + -63 + ... + 90\\ d=403 &: 2015 = -196 + -195 + ... + 206\\ d=2015 &: 2015 = -1006 + -1005 + ... + 1008\\ \end{split} $$ each of these is actually the same as the solutions above (just cancel all the negatives with their positive counterpart)

Puzzle: Writting year as sums of runs of numbers

This year is 2016 and \[ 2016 = 1 + 2 + 3 + ... + 63 \] I didn't notice this myself, I saw it written somewhere but then I wondered if there were any other ways of writing 2016 as a sum of consecutive numbers and it turn out there are.

So, the puzzle is, how many ways are there of writing 2016 as a sum of consecutive numbers and what's the answer for the general case where you're trying to write any number \(Y\) as such a sum. The answer is quite simple but non-obvious.

I'll post the solution shortly My solution is here, please leave comments or solutions below.