This post is inspired by a tweet from @standupmaths who sends out puzzles tagged #mathspuzzle irregularly but fairly frequently. I won’t put out any spoilers on the blog, but once the solution is out on twitter, I may occasionally muse on these here. It’s my first go at both maths blogging and embedding equations into a webpage, so any comments welcome. I’m pretty sure I’ve gone round the houses on this one, so shortened method / notation welcome (as well as pointing out any errors that I’ve made, obviously).
The problem was stated thus: “#MathsPuzzle: What is the only number 10 →20 that is not a sum of consecutive numbers? (eg. Not 12 because 3 + 4 + 5 = 12)”. Tweeters fairly quickly answered 16 and the follow up question (abbreviated) was – how does this generalise? To which the answer is the only positive integers that cannot be represented as the sum of consecutive integers are the set \(x \in \{2^n\}\) where n is an integer.
After finding this result, I tried to express why \(\{2^n\}\) and only \(\{2^n\}\) exhibit this property in 140 characters and failed miserably. So, I decided to blog about it and write the method I followed in my head down – if only to clarify to myself how I came to the result (and whether it was valid).
I began by using the result:
\[\begin{aligned} \sum_{i=1}^{i=j}{i} = \frac {j \cdot (j+1)}{2} \end{aligned} \]
therefore, the sum of integers between j and k is:
\[\begin{aligned} \sum_{i=1}^{i=k}{i} \quad – \quad \sum_{i=1}^{i=j}{i} \qquad & = \qquad \frac {k \cdot (k+1)}{2} – \frac {j \cdot (j+1)}{2} \\ & = \qquad \frac {k^2 – j^2 + k – j}{2} \\ & = \qquad \frac {(k+j) \cdot (k – j) + (k – j)}{2} \\ & = \qquad \frac {(k+j+1) \cdot (k-j)}{2} \end{aligned} \]
therefore, if x is to be expressed as the sum of some set of consecutive integers, the following must hold:
\[\begin{aligned} x \qquad &= \qquad \frac {(k+j+1) \cdot (k-j)}{2} \\ 2x \qquad &= \qquad{(k+j+1) \cdot (k-j)} \qquad (1)\end{aligned} \]
We notice that if both \(k\) and \(j\) are odd, or both \(k\) and \(j\) are even, then both \(k + j\) and \(k – j\) are even, therefore \((k+j+1)\) is odd and \((k-j)\) is even. Conversely, if one of \(k\) or \(j\) is even and the other odd, both \((k + j)\) and \((k – j)\) are odd \((k+j+1)\) is even and \((k-j)\) is odd.
So we may state that if \(x\) is the sum of consecutive integers then we must be able to express \(2x\) as the product of one even and one odd integer
If we next consider any integer as a product of primes, we can say that for any integer
\begin{equation}\label{primefactors} i = 2^a \cdot 3^b \cdot 5^c \cdot 7^d \cdots \qquad (2)\end{equation} and so on for all primes.
If we set \(i = 2x \) then we can combine (1) and (2) to see that for x to be the sum of consecutive integers,
\[\begin{aligned} 2x \qquad &= \qquad {(k+j+1) \cdot (k-j)} \\&= \qquad 2^a \cdot 3^b \cdot 5^c \cdot 7^d \cdots \\ \\ \text{therefore} \\ \\{(k+j+1) \cdot (k-j)}&= \qquad 2^a \cdot 3^b \cdot 5^c \cdot 7^d \cdots \qquad \qquad (3) \end{aligned} \]
As all primes are odd except 2, and \((\text{odd}\times\text{odd})\) is always odd, we can say that the right hand side of (3) will always be \((\text{even}\times\text{odd})\) except in the case where \( b = c = d = \cdots = 0 \) where it will be \( 2^a \). However, for \(x\) to be the sum of consecutive digits, this expression is required to be \((\text{even}\times\text{odd})\), which holds in all cases except where \(2x = 2^a \rightarrow x = 2^{a-1} \rightarrow x \in \{2^n\} \)