An interesting problem about balanced sums

The problem

Consider an equation 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} \label{eq:main} \end{equation}

or, perhaps in a more readable notation

\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}

Lets refer to sums of this form as balanced sums. In other words, we are looking at 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} \begin{equation} 12 + 13 + 14 + 15 + 16 + 17 + 18 = 19 + 20 + 21 + 22 + 23 \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}

Straightforward solution

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{2pq - (p-q)(p+q-1)}{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 presents us with an algorithm that solves the problem (if not very efficiently).

A second look

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 identical 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?

Odd divisors

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 \label{eq:2a} \end{equation} \begin{equation} 2a - 1 = \underbrace{\frac{2q^2}{p-q}}_{X} - \underbrace{(p-q)}_{Y} \label{eq:xy} \end{equation}

It follows from \eqref{eq:xy} that \(p-q\) must divide \(2q^2\). More specifically, each \(a\) corresponds to a complementary pair \((X, Y)\) of divisors of \(2q^2\). Since \(2q^2\) cannot possibly be a perfect square, \(X\) and \(Y\) will always be different.

Also, \(2a - 1\) is odd, meaning that divisors \(X\) and \(Y\) must have different parity: if \(X\) is even, \(Y\) must be odd and vice versa.

Finally, \(2a - 1\) is positive. This means that a complementary pair \((X, Y)\) can only be used in \eqref{eq:xy} in one specific order: the smaller out of two divisors should be used as \(p-q\). In other words, each complementary pair of divisors produces only one valid value of \(a\), not two.

So, the number of different odd values of the right-hand side of \eqref{eq:xy} coincides with the number of different even-odd pairs 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

• Since \(2q^2\) is even, there is always at least one complementary even-odd pair of divisors that satisfies the above requirements: \((2q^2, 1)\). Substituting \(p-q=1\) into \eqref{eq:2a} we get \(a=q^2\). I.e. every perfect square \(q^2\) is a starting point for a balanced sum with \(q+1\) terms on the left-hand side and \(q\) terms on the right-hand side

  \begin{equation} 4+5+6=7+8 \nonumber \end{equation} \begin{equation} 25+26+27+28+29+30=31+32+33+34+35 \nonumber \end{equation}

  Conversely, all balanced sums of with "almost equal" number of terms on both sides (i.e. \(p=q+1\)) start from a pefect square.

  When \(q\) is a power of \(2\), a balanced sum of this kind is the only one available.

• Using a complementary even-odd pair of divisors \((X, Y)\) in \eqref{eq:2a} in "reverse" order (i.e. substituting the larger divisor as \(p-q\)) results in negative value of \(a\). Of course, we'll still get a sum that satisfies the equality \eqref{eq:main}. For example, for \(q=10\): \(2q^2=200\), for pair \((8, 25)\) we can substitute \(p-q=25\) and end up with \(2a=200/25-25+1=-16, a=-8\). \(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.

• It is easy to show that if the smaller divisor produces value \(a=A > 0\), then the larger divisor will from the same pair will produce \(a=-(A-1)\). Consequently, the the left-hand side sum corresponding to the negative value of \(a\) will have the following form

  \begin{equation} \underbrace{(-(A-1) + (-(A-2)) + \ldots + (-1) + 0 + 1 + \ldots + (A-1)}_\text{sums to zero} + A + (A+1) + \ldots \nonumber \end{equation}

  The left-hand side includes a symmetrical sequence of \(2A-1\) additional terms before \(A\), which all sum to zero. This means that a sequence of terms starting from \(a=-(A-1)\) will ultimately lead to the same sum as a sequence starting from \(a=A\), i.e. both divisors from a complementary pair lead to the same value of the sum and to the same right-hand side in \eqref{eq:main} (which is already ilustated by the above \((8, 25)\) example)

• Obtaining \(a=0\) from \eqref{eq:2a} 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\quad,\quad x \in \mathbb{N} \nonumber \end{equation}

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