Sums of Sequences on the SAT

Monday night, my friend Jesse mentioned an SAT question he felt was actually insightful. It led us to explore a property we did not expect to find.

The Initial Question

The integer $8$ may be written as the sum of $n$ consecutive integers, for some $n$ strictly greater than $1$. There is only one such $n$; what is it?

The following two sections discuss approaches to finding the answer to this initial question efficiently. This work led to both our second question and our methods of solving it.

Reasoning per start value $x$

Neither Jesse nor I wanted to rely on this reasoning because it doesn't generalize well. I figured I'd discuss it because it does illustrate good initial exploration.

For this particular case, reasoning per start-of-sequence seems like an okay idea. For each possible start, you can just keep adding larger values of $y$ until the sum meets or beats $8$, and then move on to the next $x$. There probably aren't that many cases to even check.

Before starting, it would be good to check (whether you'll stop at some point)(per-x-stops).

(start per-x-stops)

For each $x$, (does the search for $y$ stop)(per-x-y-stops)?

(start per-x-y-stops)

It is true that, when we strive for a positive value $8$, for each $x$ we fix, there will be a unique smallest $y$ to stop at with $S(x,y)\ge 8$, and every longer sequence will just surpass $8$ further.

(stop per-x-y-stops)

Do we (run out of $x$-values)(per-x-x-stops) to check?

(start per-x-x-stops)

Checking $x=0$ is the same as checking $x=1$, so we don't even have to worry about that case. Checking positive $x$ will stop after $x=8$, since any larger starting value already has $S>8$. (Perhaps, at this point, you decide to check for solutions with positive $x$.) Checking negative $x$ seems more interesting, since the further negative the start, the further $y$ can be and still possibly have $S=8$. However, as you start adding larger $y$, you'll notice that you keep cancelling out what you started with exactly. For instance, $S(-2,2)=0$, so $S(-2,5) = S(3,5)$:

\[
\begin{aligned}
(-2) + (-1) + 0 + 1 + 2 + 3 + 4 + 5 \\
=3 + 4 + 5
\end{aligned}
\]

Since we won't even get positive sums until we pass that cancellation point when [$\newcommand\abs[1]{\left\vert{#1}\right\vert}y=\abs{x}$,][(when we start with the negative of what we end with, and they all sum to zero)] for every [$x<0$,][(negative start point)] we may as well start by trying [$y>\abs{x}$,][(stopping past the cancellation point)] and in that case, the result is the same as $S(\abs{x}+1,y)$, a sum of a sequence of only positive integers. So we don't even need to check negative $x$; any solution will have a corresponding sequence with positive $x$ and the same $S$.

(stop per-x-x-stops)

(stop per-x-stops)

Let's (check for solutions)(per-x-check).

(start per-x-check)

This kind of result is best presented in a table. For each positive $x\le 8$, a smallest $y$ with $S(x,y)\ge 8$ is found. To understand why we are only working with those $x$, click on "whether you'll stop at some point" above.

\[
\begin{array}{c|c|c}
x & y & S(x,y-1) & S(x,y) \\ \hline
1 & 4 & 6 & 10\\
2 & 4 & 5 & 9 \\
3 & 5 & 7 & 12\\
4 & 5 & 4 & 9 \\
5 & 6 & 5 & 11\\
6 & 7 & 6 & 13\\
7 & 8 & 7 & 15\\
8 & 8 & - & 8
\end{array}
\]

The only positive solution is $S(8,8)$, but that one is technically disallowed. Then the corresponding solution with negative elements in the sequence, $S(-7,8)$, is the desired solution. (The correspondence is discussed in "whether you'll stop at some point" above.) Its length is $n = y - x + 1 = 8 - (-7) + 1 = 16$. (Seven negatives, eight positives, and $0$.)

(stop per-x-check)

Reasoning per length of sequence $n$

This is related to my reasoning. It’s pretty much how I talked through it with Jesse when I objected that there was no solution.

Let’s study the (cases of possible $n$)(n-cases), including the technically disallowed case $n = 1$.

(start n-cases)

(The $n = 1$ case.)(n-et-1)

(start n-et-1)

Then there is exactly one “solution” with the sequence containing only the integer $8$.

(stop n-et-1)

(The $n = 2$ case.)(n-et-2)

(start n-et-2)

Then the consecutive integers have opposite parity, and add to be odd. Since we want them to add to the even number $8$, there cannot be a solution in this case.

(stop n-et-2)

(The $n = 3$ case.)(n-et-3)

(start n-et-3)

Then the consecutive integers add up to $3k$, where $k$ is the middle integer. Since $8$ is not divisible by $3$, there cannot be a solution in this case.

(stop n-et-3)

(The $n \ge 4$ case.)(n-ge-4)

(start n-ge-4)

We split this case up into two subcases:

(When all of the consecutive integers are positive.)(n-ge-4-pos)

(start n-ge-4-pos)

The consecutive integers sum to at least $1+2+3+4=10$. Since $8 < 10$, this subcase cannot produce a solution.

(stop n-ge-4-pos)

(When some of the consecutive integers are not positive.)(n-ge-4-neg)

(start n-ge-4-neg)

Let the smallest and largest numbers in the sequence be $x$ and $y$, and let the resulting sum be $S(x,y)$. Since $S > 0$ exactly when $\abs{x} < \abs{y}$, a solution must satisfy that. Then a solution must have $S(x,y) = S(\abs{x} + 1,y)$, and we know there will be a sequence with all positive values corresponding to whatever solution we find. We’ve already shown that the only positive sequence with sum $8$ has $n = 1$ and is $S(8,8)$, but it does not count as a solution. The actual solution corresponding to it has $n = 16$ and is $S(-7,8)$.

(stop n-ge-4-neg)

(stop n-ge-4)

(stop n-cases)

The Second Question

If you've skipped to this point, here's the notation: when a sequence is being considered, the smallest value is $x$ and the largest is $y$, and the sum $x + (x+1) + \cdots + (y-1) + y$ is represented as $S(x,y)$. Note that the length $n$ is given by $y - x + 1$, since $y-x$ counts how many values come after $x$.

How special is $8$ in this property? More thoroughly, what is the set $K$ of integers $k$ for which there is only one way to write $k$ as a sum of at least two consecutive integers? (Why this was interesting to me...)(second-interesting)

(start second-interesting)

It seems like it should be a pretty restrictive property. There are a lot of sums out there, and as you consider larger numbers, there's even more sums to consider. So, there will probably be fewer elements of $K$ as you look further from $0$. But I don't even know whether $K$ has an infinite number of elements off-hand — the elements could become more rare as we go larger, but still keep appearing, like the prime numbers, or there could be a point where so many sums are being considered that nothing has the property anymore.

(stop second-interesting)

How we approached this problem was to first get a feeling for what $K$ might look like. Then we wanted to test our feelings, and divided up the next bit of work between the two of us to speed things up. Then we discussed our results and decided on how to prove our expectations were true.

Getting a Feeling

Before really digging in, we answered the following questions to get a feel for things.

Do we need to study (negative elements of $K$)(feeling-negative)?

(start feeling-negative)

No, because $S(x,y) = -S(-y,-x)$ for every pair of integers with $x\le y$. That implies that the possible sums to consider for a positive $k$ are exactly the opposites of those to consider for its negative $-k$.

(stop feeling-negative)

What are the (small elements of $K$)(feeling-small)?

(start feeling-small)

We already know $8$ is in $K$, so let's find the nonnegative elements of $K$ less than $8$. $0=S(-y,y)$ for every positive $y$, so $0$ is not in $K$. $1$ is really easy to check that $S(0,1)$ is the only solution with at least two values in the sequence, so $1$ is in $K$. Continuing in this way, $2$ and $4$ are in $K$, while $3=S(1,2)=S(0,2)$, $5=S(2,3)=S(-1,3)$, $6=S(1,3)=S(0,3)$, $7=S(3,4)=S(-2,4)$ show that those are not in $K$.

(stop feeling-small)

What do we expect the (next value in $K$)(feeling-expect) to be?

(start feeling-expect)

It seems so far that $K$ only contains powers of $2$. But that seems almost ridiculous, especially since we only have the elements $1$, $2$, $4$, $8$ to base it on. Regardless, $16$ is a good next guess, not too close, not too far.

(stop feeling-expect)

Since checking values that end up in $K$ tends to require more work than checking values that are not in $K$, Jesse and I decide to split up our work like so: He'll tackle testing whether our guess for the next value in $K$ is actually in $K$, and I'll tackle showing that everything up to our guess isn't in $K$.

Testing values we expect are in $K$

Jesse likes to make algorithms, so he decided to streamline the process of testing values in a way that meshed with our general observations.

Can we make any (observations that generalize)(obs-general)?

(start obs-general)

As mentioned above, the reasoning per start value doesn't generalize well. One thing from both reasonings that generalizes well here is that we need only check the positive sequences. The second reasoning has other results that help here. For instance, we expect powers of two to be in $K$, and there are certain values of $n$ to exclude in that case. We showed $n=2$ implies $S$ is odd. We also showed when $n=3$, $S$ is divisible by $3$. Since the most useful observations here are for fixed $n$, it seems like that's what our algorithm will want to assume at each step. With that assumption, (another observation)(obs-fixed-n) makes the algorithm clear.

(start obs-fixed-n)

When $n$ is fixed, notice that removing the smallest value and adding the next is the same as shifting all the values up by $1$, so:

\[
S(x+1,y+1) = S(x,y) + n \\
\text{and more generally...} \\
S(x+z,y+z) = S(x,y) + nz
\]

This is incredibly helpful, since that means you can just find one example sequence, such as $S(1,n)$, and then the sums of the other $n$-length sequences are exactly the numbers that differ from $S(1,n)$ by a multiple of $n$.

(stop obs-fixed-n)

(stop obs-general)

What do those observations tell us (the general algorithm)(general-form-of-algorithm) should be?

(start general-form-of-algorithm)

We will check each possible $n$ for sequences of $n$ consecutive positive integers that sum to a $k$ that is a power of $2$. We assume $n\ge 4$. (Why?!Why assume $n\ge4$.)(why-n-ge-4) For each $n$ afterwards, compute $k-S(1,n)$, and check if it is a multiple of $n$. If so, and it is the $z$th multiple of $n$, then we have $S(1+z,n+z)=k$. In this case, $k$ is not in $K$. (Why?!Why $k$ is not in $K$.)(why-k-not-in-K) In the other case, $k$ may still be in $K$, and we move on to test the next $n$. We eventually reach an $n$ such that $S(1,n)>k$, at which point all $n$ greater than it cannot have any positive solutions.

(start why-n-ge-4)

$n=1$ has only the trivial solution $S(k,k)=k$, $n=2$ has only odd sums, and $n=3$ has only sums divisible by $3$.

(stop why-n-ge-4)

(start why-k-not-in-K)

We always also have the solution $S(-k+1,k)=k$ corresponding to $S(k,k)=k$, so there are now two ways to express $k$ as a sum of at least two consecutive integers.

(stop why-k-not-in-K)

(stop general-form-of-algorithm)

How does this algorithm (apply to the $k$ we want to test)(apply-algorithm)?

(start apply-algorithm)

We want to test whether $k=16$ is in $K$. As before, this is best presented in a table.

\[
\begin{array}{c|c|c}
n & S(1,n) & k-S(1,n) & \text{divisible by $n$?} \\ \hline
4 & 10 & 6 & \text{no} \\
5 & 15 & 1 & \text{no}
\end{array}
\]

and viola, we're done, because $S(1,6)>k$. Thus $16$ is in $K$, as predicted!

(stop apply-algorithm)

Eliminating values from $K$

For elimination, I noticed that it would be easier to continue my logic from before to see which values could not be in $K$ for each $n$.

(The $n=2$ case.)(elim-n-et-2)

(start elim-n-et-2)

The logic before was that the sum of two consecutive integers is always odd. Moreover, the converse is true: every odd is the sum of two consecutive integers. (Why?!Why the converse is true.)(elim-every-odd) This means that every odd $k$ cannot be in $K$, except for $k=1$, for which that sum of two consecutive integers is the trivial solution $S(-k + 1, k)$.

(start elim-every-odd)

Every odd is an even plus one, so an odd $k=2z+1$ for some $z$. Then $k=(z) + (z+1) = S(z,z+1)$, the sum of two consecutive integers.

(stop elim-every-odd)

(stop elim-n-et-2)

(The $n=3$ case.)(elim-n-et-3)

(start elim-n-et-3)

The logic before was that the sum of three consecutive integers is always divisible by three. The converse is true here as well: every multiple of three is the sum of three consecutive integers. (Why?!Why the converse is true.)(elim-every-mult-of-3) Since the sequence of three consecutive integers is never the trivial solution, (Why?!Why sequence of three is nontrivial.)(nontrivial-sum-of-3) every multiple of three is not in $K$.

(start elim-every-mult-of-3)

If $k$ is a multiple of three, then $k=3z$ for some $z$. Then $k=(z-1) + (z) + (z+1) = S(z-1,z+1)$, the sum of three consecutive integers.

(stop elim-every-mult-of-3)

(start nontrivial-sum-of-3)

The trivial solution $S(-k+1,k)$ always has an even number of values in the sequence,$n=2k$.

(stop nontrivial-sum-of-3)

(stop elim-n-et-3)

At this point, there are (only two $k$ left to eliminate)(elim-k-left) with $8\lt k\lt 16$.

(start elim-k-left)

They are $k=10$ and $k=14$. One thing to notice is that they are divisible by five and seven; perhaps that can be of use in the same way that we eliminated things divisible by three. Let's consider the $n=5$ case. In such a case, the middle value is still the average of $x$ and $y$, $(x+y)/2$, and the values below are as far below as the values above, so the differences cancel out, and $S(x,y)=5(x+y)/2$, which is divisible by five. And, sure enough, the converse works: for $k=5z$, $S(z-2,z+2)=5z=k$. This eliminates $k=10$ with $S(0,4)$. Similarly, for $k=7z$, $S(z-3,z+3)=7z=k$, eliminating $k=14$ with $S(-1,5)$.

(stop elim-k-left)

We can (generalize these results)(elim-divisible-by-not-2).

(start elim-divisible-by-not-2)

Suppose $k=nz$ for some odd prime $n=2m+1$. Then we can make a sequence of $n$ consecutive integers whose sum is $k$: $S(z-m,z+m) = nz = k$. Since $n$ is odd, this sequence presents a nontrivial solution, and $k$ cannot be in $K$. This generalized result implies that every element of $K$ is at most divisible by two, so the powers of two are the only potential elements of $K$, as predicted!

(stop elim-divisible-by-not-2)

Confirming values in $K$

Jesse and I reconvened, agreeing that we had now eliminated everything that we predicted should not be in $K$. All that remained was to show that everything else actually is in $K$.

At this point, it seemed clear that we had two cases to discuss when incorporating my new results into Jesse's algorithm.

(The $n$ is odd case.)(inco-odd)

(start inco-odd)

From the generalized results above, we now know that the sum must be divisible by $n$ in this case. For odd $n>1$, no power of two is divisible by $n$, so we may now skip all of these $n$ in Jesse's algorithm.

(stop inco-odd)

(The $n$ is even case.)(inco-even)

(start inco-even)

This case seems more interesting. We already know that if $n=2$, then the sum is odd, and we skip that case when $k$ is a power of two other than $1$. We can generalize that further and say the same when $n$ is divisible by two but not four, because then the sequence will contain an odd number of odd values, and the sum will be odd. That leaves the subcase of (when $n$ is divisible by four)(inco-divis-by-4).

(start inco-divis-by-4)

Now we have to study the result of the sum more closely. In particular, we know that for each power of two $k$, we will have the trivial solution $S(-k+1,k)$ with $n=2k$, so we will expect some solutions to come from this case. At this point, we noticed that the formula $S(x,y)=n(x+y)/2$ still holds, since every pair of sequence values, starting with the outermost and working in, add up to $x+y$. Since $x+y$ is always odd for even $n$, it contributes no factors of two to the sum; thus, $S$ is divisible by $n/2$ but not $n$. Then the only power of two that $S$ could be equal to is $n/2$ itself, and this is exactly the trivial solution we expect: when $k=n/2$, $S(-k+1,k)=k$.

(stop inco-divis-by-4)

(stop inco-even)

Sums of Sequences on the SAT

The Initial Question

Reasoning per start value \(x\)

Reasoning per length of sequence \(n\)

The Second Question

Getting a Feeling

Testing values we expect are in \(K\)

Eliminating values from \(K\)

Confirming values in \(K\)