From the 2017 Putnam:

Q:

Suppose that a positive integer \(N\) can be expressed as the sum of \(k\) consecutive positive integers:

\[ N = a + (a+1) + (a+2) + \cdots + (a+k) \]

for \(k = 2017\) but for no other values of \(k \gt 1\). Considering all positive integers \(N\) with this property, what is the smallest positive integer \(a\) that occurs in any of these expressions?

A:

First, we want to write an arbitrary $N$ more concisely: \[ N = ka + \frac{(k)(k-1)}{2} = k(a + \frac{k-1}{2})\]

Thus, for \(k = 2017\), we should have that any \(N\) is a multiple of \(2017\).

These are just preliminary observations. But the next step took some time – did I want to think about the problem in terms of $k$, $N$, or $a$? At first, $N$ made sense, because I thought it would be possible to write $N$ as $2017x$, but that didn’t really get me anywhere. It did help in thinking about the problem and playing around with how things worked, but it turns out there is actually a quite logical approach, based on considering each $k$ and iterating through all the values of $a$ to reach the possible values of $N$ obtainable from each $k$.

First, observe that, if $k=2$, then we can have values of $3, 5, 7, \dots$ by setting $a = 1, 2, 3, \dots$. This immediately tells us that any value of $N$ must be even, otherwise it could be generated by $k=2$. This provides some insight into how we might go about this problem.

Let us define some terms. If a value of $N$ be generated by some $k \neq 2017$, we call that value of $N$ invalid, and the opposite of that valid. We say a value of $k$ invalidates some $N$ if that value of $k$ may generate $N$ for some $a$.

If we consider even values of $k$ greater than $2$, we see that the values of $N$ that become invalidated by those $k$ are a subset of those made invalid by $k=2$, as any even $k$ will give odd values of $N$, which are all invalid already.

If we consider $k=3$, we get values of $6, 9, 12, \dots$, which are clearly just the multiples of $3$ above $6$ (this can be easily seen, given that each time you increment $a$, you increment $N$ by $ka$). This same idea works for all odd $k$, simply because of how $N$ is defined:

\[ N = k(a + \frac{k-1}{2}) \]

for $a = 1, 2, 3, \dots$

So, for all odd $k$, multiples of $k$ higher than $k(1 +\frac{k-1}{2})$ are all invalid. In fact, for composite numbers, invalid $N$ will have already been invalidated by an earlier odd prime, so we really only need to concern ourselves with odd primes in consideri]ng $k$.

So, how do we choose a valid $N$? We know already that $N$ must be even, and we know that the ones that aren’t invalidated also have to avoid being multiples of $3, 5, 7$, and all the other odd primes under $2017$.

Initially, I thought that we would have to choose some $N$ whose smallest prime factor besides 2017 was $p$. Setting $k=p$ would invaldiate multiples of $p$, but the idea was to choose a prime large enough that it would start invalidating values much larger than $N$. While this would in principle work, there is a way to get much smaller values of $N$ – the powers of 2! Recall that $k=2$ invalidates odd values of $N$, not multiples of $2$. In fact, every power of $2$ invalidates odd values, which means it will never invaldiate a multiple of itself. And so we have a simple solution.

Values that are of the form $2^x \times 2017$ are valid. Thus, we can just set:

\[ 2^x \times 2017 = 2017 (\frac{2017-1}{2} + a) \]

\[ 2^x = 1008 + a \]

This final equation gives us, by the simple fact that $1024$ is a power of $2$, $a = 16$, which is the smallest value of $a$ satisfying our equation.