An interesting problem about balanced sums

The problem

Consider an equation of the following form

$$\begin{array}{}\text{(1)}& \sum _{i=a}^{a+p-1}i=\sum _{j=a+p}^{a+p+q-1}j,a\in \mathbb{N}\end{array}$$

or, perhaps in a more readable notation

$$\underset{\text{p terms}}{\underbrace{a+(a+1)+\dots +(a+p-1)}}=\underset{\text{q terms}}{\underbrace{(a+p)+(a+p+1)+\dots +(a+p+q-1)}}$$

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

$$1+2=3$$ $$9+10+11+12=13+14+15$$ $$12+13+14+15+16+17+18=19+20+21+22+23$$

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 $$\underset{\text{p=18}}{\underbrace{9+10+\dots +26}}=\underset{\text{q=10}}{\underbrace{27+28+\dots +36}}$$ $$\underset{\text{p=15}}{\underbrace{18+19+\dots +32}}=\underset{\text{q=10}}{\underbrace{33+34+\dots +42}}$$ $$\underset{\text{p=11}}{\underbrace{100+101+\dots +110}}=\underset{\text{q=10}}{\underbrace{111+112+\dots +120}}$$

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:

$$\frac{(2a+p-1)p}{2}=\frac{(2a+2p+q-1)q}{2}$$ $$\begin{array}{}\text{(2)}& 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}\end{array}$$

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

$$q=2^j\cdot a^k\cdot b^l\cdot c^m\cdot \dots$$

then

$$\begin{array}{}\text{(3)}& n=1\cdot (2k+1)\cdot (2l+1)\cdot (2m+1)\cdot \dots \end{array}$$

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 $\text{(2)}$

$$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}$$ $$\begin{array}{}\text{(4)}& 2a=\frac{2q^2}{p-q}-(p-q)+1\end{array}$$ $$\begin{array}{}\text{(5)}& 2a-1=\underset{X}{\underbrace{\frac{2q^2}{p-q}}}-\underset{Y}{\underbrace{(p-q)}}\end{array}$$

It follows from $\text{(5)}$ 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 $\text{(5)}$ 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 $\text{(5)}$ 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 $\text{(3)}$.

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 $\text{(4)}$ 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

  $$4+5+6=7+8$$ $$25+26+27+28+29+30=31+32+33+34+35$$

  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 $\text{(4)}$ 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 $\text{(1)}$. 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

  $$\underset{\text{p=35}}{\underbrace{(-8)+(-7)+\dots +0+\dots +26}}=\underset{\text{q=10}}{\underbrace{27+28+\dots +36}}$$

  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

  $$\underset{\text{sums to zero}}{\underbrace{(-(A-1)+(-(A-2))+\dots +(-1)+0+1+\dots +(A-1)}}+A+(A+1)+\dots$$

  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 $\text{(1)}$ (which is already ilustated by the above $(8,25)$ example)

• Obtaining $a=0$ from $\text{(4)}$ is only possible when $2q^2$ is a product of two consequitive natural numbers. For example, for $q=6$: $2q^2=72=8\times 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

  $$\frac{x(x+1)}{2}=q^2,x\in \mathbb{N}$$

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