# $O(k)$ Algorithm to find the first $k$ pairs of Magic numbers $a$ and $b$ such that $\sum_{i=1}^{a-1} i = \sum_{k=a+1}^b k$, with restrictions

Provide an $$O(k)$$ algorithm to find $$k$$- magic pairs of positive integers a and b of type signed int where a magic pair is defined as $$\sum_{i=1}^{a-1} i = \sum_{k=a+1}^b k$$. You can't use the summation formula $$\frac{N \cdot (N+1)}{2}$$ as it would result in an overflow. Even you can't run sums such as sum1 and sum2, it's still going to overflow.

Example: (6,8) (35,49) (204,288) are the first three Magic Pairs.
P.C: This was our recent examination question, I am curious to know the algorithm.

• Your formulas are not well formed? Do you mean $\sum_{i=1}^{a-1} i$? Also "of type signed int" doesn't say much about the range of the integers as the maximum value representable by a signed int varies across languages and architectures. – Steven Nov 26 '19 at 9:55
• @Steven It meant that while writing a program we can't directly use the formula for summation or run two sums from 1 to $a-1$ and $a+1$ to $b$ and compare them, which on doing so, leads to integer overflow. I Hope the question is clear now! – Akash Tadwai Nov 26 '19 at 9:58
• What computational complexity are you aiming for? – Steven Nov 26 '19 at 10:04

One simple but inefficient solution is just that of just computing the two sums in parallel while only keeping track of the difference between their partial sums. I.e., if you added the first $$x$$ terms of the first sum and first $$y$$ terms of the second sum, then you'll only remember $$x$$, $$y$$, and $$\Delta = \sum_{i=1}^x i - \sum_{k=a+1}^{a+1+y} k$$. If $$\Delta$$ is non-positive, then consider the next term of the first sum (i.e., increment $$x$$ by one and add $$x$$ to $$\Delta$$). If $$\Delta$$ is positive, then consider the next term of the second sum (i.e., increment $$y$$ by one and subtract $$a+1+y$$ from $$\Delta$$). In this way $$|\Delta|$$ will never exceed $$\max\{a,b\}$$.
Another more efficient solution is as follows. Using the summation formula you can write: $$\sum_{i=1}^{a-1} i = \frac{a(a-1)}{2} = \frac{b(b+1)}{2} - \frac{a(a+1)}{2} = \sum_{k=a+1}^{b} k$$, and some simplifications lead to: $$2a^2 = b(b+1)$$.
This means that, once you fix $$b$$, you can find the corresponding value of $$a$$ as follows: $$a= \frac{1}{\sqrt{2}} \cdot \sqrt{b} \cdot \sqrt{b+1}.$$
Notice that $$\sqrt{b} \cdot \sqrt{b+1}$$ must always be greater than $$b$$ and smaller than $$b+1$$, meaning that $$\frac{b}{\sqrt{2}} < a < \frac{b}{\sqrt{2}} + \frac{1}{\sqrt{2}}$$ and, since $$\frac{1}{\sqrt{2}} < 1$$, there is at most one integer in that interval, namely $$1+ \left\lfloor \frac{b}{\sqrt{2}} \right\rfloor = 1+ \left\lfloor \frac{\sqrt{2} b}{2} \right\rfloor$$.