# Quick algorithm to find the first $n$ integers that can be expressed as a summation and as a perfect square… how does it work?

Edit: so it turns out these are called square triangular numbers

I was helping my sister out with her APCS homework and one of the questions was to find the first $$n$$ "magic squares" where a magic square is defined as a number that can be expressed as $$\sum_{i=0}^x i = \frac {x (x+1)} 2$$ and $$y^2$$ for some integers $$x, y$$, with the first 3 magic squares being 1, 36, and 1225. Yes, I know this is not the typical definition of magic square, and this was probably done to make the question less googlable.

Just for fun, I tried to find the most optimal solution. My final solution, although I have absolutely no idea how it works, is this:

n = 69

a = 1
b = 1
magic = [1]
while len(magic) < n:
b = 2 * a + b
a = b - a
magic.append(a * a * b * b)

I reached this solution because I was initally going through all the squares and checking if double the square minus 1 or double the square plus 1 was also a square (which would satisfy the equation $$n^2 + n - 2 a^2 = 0$$). For example, looking at the square 4, we see that $$4 \times 2 + 1 = 9$$ is a square, so the equation is satisfied for $$a=36$$. Looking at the squares that ended up producing magic square, the magic square ended up being $$1 \times 1 = 1^2 \times 1^2$$, $$4 \times 9 = 2^2 \times 3^2$$, $$25 \times 49 = 5^2 \times 7^2$$, $$144 \times 289 = 12^2 \times 19^2$$, etc, which follows the pattern described in my code. Why?

And yeah I've never used math stackexchange before so let me know if I should be asking this differently.

• Look it up at OEIS, they usually have all the information oeis.org/A001110 – Yuriy S Oct 23 '18 at 21:37
• wow, that's super helpful, i'll see if this is in there somewhere – Aayush Tyagi Oct 23 '18 at 22:07