An interesting problem about balanced sums

We are intrested in equations of the following form

\begin{equation} \sum_{i = a}^{a+p-1}i = \sum_{j = a+p}^{a+p+q-1}j\quad,\quad a \in \mathbb{N} \end{equation}

or, perhaps in a more readable form

\begin{equation} \underbrace{a + (a+1) + \ldots + (a+p-1)}_\text{p terms} = \underbrace{(a+p) + (a+p+1) + \ldots + (a+p+q-1)}_\text{q terms} \nonumber \end{equation}

In other words, we are looking for sequences of natural numbers of length \(p+q\), in which the sum of the first \(p\) numbers is equal to the sum of the remaining \(q\) numbers. For example

\begin{equation} 1 + 2 = 3 \nonumber \end{equation} \begin{equation} 9 + 10 + 11 + 12 = 13 + 14 + 15 \nonumber \end{equation}

Obviously, \(p\) is always going to be greater than \(q\).

The problem: given \(q\) - number of terms in the right-hand sum - determine \(n\) - how many different sums there are for the given value of \(q\).

For example, for \(q=10\) there are three different sums \begin{equation} \underbrace{9 + 10 + \ldots + 26}_\text{p=18} = \underbrace{27 + 28 + \ldots + 36}_\text{q=10} \nonumber \end{equation} \begin{equation} \underbrace{18 + 19 + \ldots + 32}_\text{p=15} = \underbrace{33 + 34 + \ldots + 42}_\text{q=10} \nonumber \end{equation} \begin{equation} \underbrace{100 + 101 + \ldots + 110}_\text{p=11} = \underbrace{111 + 112 + \ldots + 120}_\text{q=10} \nonumber \end{equation}

A straighforward constructive solution for this problem can be obtained by applying the formula for the sum of arithmetic progression to both sides of the equation:

\begin{equation} \frac{(2a + p - 1)p}{2} = \frac{(2a + 2p + q - 1)q}{2} \nonumber \end{equation} \begin{equation} a = \frac{-p^2 + (2q+1)p + q^2 - q}{2(p - q)} = \frac{pq}{p-q} - \frac{p+q-1}{2} \label{eq:a} \end{equation}

From the last expression it is obvious that increasing \(p\) while keeping \(q\) fixed will result in monotonically decreasing \(a\). So, all we need to do is to iterate through all increasing \(p>q\) as long as \(a\) remains positive. Every integer \(a\) we encounter along the way defines one of the sums we are looking for. This solves the problem (if not very efficiently).

However... Looking at the results for different values of \(q\), once can probably notice some vaguely familiar patterns and other properties of the results

q	n
1	1
2	1
3	3
4	1
5	3
6	3
7	3
8	1
...	...

q	n
30	9
31	3
32	1
33	9
34	3
35	9
36	5
37	3
...	...

q	n
60	9
61	3
63	15
64	1
65	9
66	9
67	3
68	3
...	...

All results are odd numbers. Powers of \(2\) seem to always produce \(1\), for all other values of \(q\) the results are always greater than \(1\). Primes always produce \(3\). The results appear to be identcial for \(q\) and \(2q\). And so on... In other words, \(n\) seems to be invariant with regard to factors \(2\) present in \(q\). And looking into odd factors of \(q\) one can eventually figure out the following relationship: if the prime factorization of \(q\) is

\begin{equation} q = 2^j \cdot a^k \cdot b^l \cdot c^m \cdot \ldots \nonumber \end{equation}

then

\begin{equation} n = 1 \cdot (2k + 1) \cdot (2l + 1) \cdot (2m + 1) \cdot \ldots \label{eq:nodd} \end{equation}

which is nothing else than the number of odd divisors of \(q^2\). For example, \(60^2=3600\) has \(9\) odd divisors - \(1, 3, 5, 9, 15, 25, 45, 75, 225\). Therefore for \(q=60\) the answer is \(n=9\).

This raises an interesting question: how does this connection between the above balancing sums and odd divisors comes into existence?

Let's apply some transformations to \eqref{eq:a}

\begin{equation} a = \frac{pq}{p-q} - \frac{p+q-1}{2} = \frac{pq - q^2 + q^2}{p-q} - \frac{p+q-1}{2} = q + \frac{q^2}{p-q} - \frac{p+q-1}{2} \nonumber \end{equation} \begin{equation} 2a = \frac{2q^2}{p-q} - (p-q) + 1 \nonumber \end{equation} \begin{equation} 2a - 1 = \underbrace{\frac{2q^2}{p-q}}_\text{term X} - \underbrace{(p-q)}_\text{term Y} \label{eq:xy} \end{equation}

It follows from \eqref{eq:xy} that \(p-q\) must divide \(2q^2\). Also, the entire right-hand side must be an odd number. This immeditaley means that terms \(X\) and \(Y\) must have different parity: if \(X\) is even, \(Y\) must be odd and vice versa. So, the number of different odd values of the right-hand side of \eqref{eq:xy} coincides with the number of different pairs \((even, odd)\) whose product equals \(2q^2\). This is nothing else than the number of odd divisors of \(2q^2\), which is the same as the number of odd divisors of \(q^2\).

And this is exactly what's expressed by \eqref{eq:nodd}.

Some additional remarks:

• Each even-odd pair can be substituted into \eqref{eq:xy} in two ways: use either the even member of the pair as \(p-q\) or the odd one. However, in order to obtain the positive result from \eqref{eq:xy} we have to use the smaller element of the pair as \(p-q\). If we use the larger element as \(p-q\), we'll end up with zero or negative result. The original statement of the problem eliminates such results from consideration. So, each even-odd pair gives up exactly one (not two) eligible balanced sum.

  For example, for \(q=10\): \(2q^2=200\). For pair \((8, 25)\) we can substitute \(p-q=8\), obtaining \(2a=200/8-8+1=18\). But if we substitute \(p-q=25\), we'll end up with \(2a=200/25-25+1=-16\). Note, that \(a=-8\) also provides us with a balanced sum

  \begin{equation} \underbrace{(-8) + (-7) + \ldots + 0 + \ldots + 26}_\text{p=35} = \underbrace{27 + 28 + \ldots + 36}_\text{q=10} \nonumber \end{equation}

  but it "doesn't count" in the original statement of the problem.

• BTW, obtaining zero result on the right-hand side of \eqref{eq:xy} is only possible when \(2q^2\) is a product of two consequitive natural numbers. For example, for \(q=6\): \(2q^2=72=8×9\).

  Substituting \(p-q=8\) we obtain \(2a=72/8-8+1=2\). Substituting \(p-q=9\) we obtain \(2a=72/9-9+1=0\). Again, the latter gives us a balanced sum starting from \(0\), but it is not eligible in the original statement of the problem.

• Finally, values of \(2q^2\) representable as product of two consequitive natural numbers satisfy

  \begin{equation} \frac{x(x + 1)}{2} = q^2 \nonumber \end{equation}

  The left-hand side represents triangular numbers. So, obtaining zero on the right-hand side of \eqref{eq:xy} is only possible when \(q^2\) is a triangular number.