## Sunday, January 03, 2016

### 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 $$\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}$$

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)