Which Numbers Are Runs?

  • Hard
  • Number puzzles
  • Tests: Linking a representation to odd divisors

The puzzle

9 = 4 + 5, and 15 = 1 + 2 + 3 + 4 + 5 = 7 + 8. But try to write 16, or 32, or 64, as a sum of two or more consecutive positive integers and you will fail.

Which numbers can be written this way, in how many ways, and why do the powers of two refuse? Work out the count for 100 as a test case.

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

A run of k numbers starting at a sums to k*a + k(k-1)/2. Rearrange to 2N = k(2a + k - 1).

Hint 2

One of k and 2a+k-1 is odd and the other even, and they multiply to 2N. So N needs an odd divisor bigger than 1.

Show the answer Hide the answer

Every number except the powers of two, and the number of ways is one fewer than its count of odd divisors. 100 has three odd divisors (1, 5, 25), so there are two ways: 18+19+20+21+22 and 9+10+...+16.

How to get there

A run of k terms starting at a has sum k*a + k(k-1)/2, so 2N = k(2a + k - 1). The two factors k and 2a + k - 1 differ by 2a - 1, which is odd, so exactly one of them is odd.

Every factorisation of 2N into an even part and an odd part therefore gives a candidate run, and each odd divisor d of N yields one. Discarding d = 1, which gives the trivial single-term "run", the count is (number of odd divisors) - 1.

A power of two has exactly one odd divisor, namely 1, so it has no valid runs - that is the whole reason 16, 32 and 64 cannot be done. For 100 = 2^2 x 5^2 the odd divisors are 1, 5 and 25, giving 3 - 1 = 2 ways. Checking: five terms from 18 give 18+19+20+21+22 = 100, and eight terms from 9 give 9+10+11+12+13+14+15+16 = 100.

The technique worth keeping

Turn "can it be written as..." into an equation, then read the equation as a factorisation. The existence of a representation becomes the existence of a divisor with the right parity, which is something you can count.