A summoning of sums

Note first that for $a \ge 1$ we have that $a^{2} \lt a^{2} + a + 1 \lt a^{2} + 2a + 1 = (a + 1)^{2}$ , so as $a^{2} + a + 1$ lies strictly between successive squares it cannot itself be a perfect square $b^{2}$ . So $S(1) = 0$ and thus $n_{0} = 1$ .

Now $a^{2} + a + n = b^{2} \Longrightarrow (a + \frac{1}{2})^{2} - \frac{1}{4} + n = b^{2} \Longrightarrow (2a + 1)^{2} + 4n - 1 = 4b^{2}$

$\Longrightarrow (2b)^{2} - (2a + 1)^{2} = 4n - 1 \Longrightarrow (2b - (2a + 1))(2b + (2a + 1)) = 4n - 1$ .

Note first that for $a \ge 1$ we have that $2b + (2a + 1) - (2b - (2a + 1)) = 4a + 2 \ge 6$ . So if we factor $4n - 1$ into positive integer divisor pairs $(d_{1}, d_{2}), d_{1} + 6 \le d_{2}$ then set $d_{1} = 2b - (2a + 1), d_{2} = 2b + (2a + 1)$ we see that $d_{1} + d_{2} = 4b$ . So we are looking for $n$ such that $4n - 1$ has $k$ divisor pairs where each pair $(d_{1}, d_{2})$ is such that $|d_{2} - d_{1}| \ge 6$ and $4 | (d_{2} - d_{1})$ .

For $n = 2$ we have $4n - 1 = 7$ , for which we have precisely $1$ suitable divisor pair $(d_{1}, d_{2}) = (1,7)$ . Thus $S(2) = 1$ and $n_{1} = 2$ .

We can then quickly work our way up integers $n$ checking for values $4n - 1$ that have multiple divisor pairs. We first reach $n = 7, 4n - 1 = 27$ giving us suitable divisor pairs $(1,27)$ and $(3,9)$ , and so $S(7) = 2, n_{2} = 7$ .

The next level is reached with $n = 19, 4n - 1 = 75$ with suitable divisor pairs $(1,75), (3,25)$ and $(5,15)$ , giving us $S(19) = 3, n_{3} = 19$ . Next up is $n = 34, 4n - 1 = 135$ with divisor pairs $(1,135), (3,45), (5,27)$ and $(9,15)$ , giving us $S(34) = 4, n_{4} = 34$ .

(I'm sure that there is a more elegant way to determine $n_{3}, n_{4}$ rather than going from one integer $n$ to the next, but factoring successive values $4n - 1$ only took a few minutes so the motivation to be more clever wasn't there. That said, the focus for $n_{3}$ is to find the first $n$ such that $4n - 1$ has $6$ divisors satisfying the divisor pair difference condition, (DPC), and for $n_{4}$ to find the first $n$ such that $4n - 1$ has $8$ divisors again satisfying the DPC.

For example, for $n_{3}$ we first reach $4(16) - 1 = 63 = 3^{2}*7$ , which has $6$ (positive) divisors, but one of the divisor pairs, namely $(7,9)$ , does not satisfy the DPC. With $75 = 3*5^{2}$ we have the first value $4(19) - 1$ that has $6$ divisors such that all divisor pairs satisfy the DPC, making $n_{3} = 19$ . With $4(34) - 1 = 135 = 3^{3}*5$ we have the first $n$ such that $4n - 1$ has $8$ positive divisors, and since the associated divisor pairs all satisfy the DPC we need look no further for $n_{4}$ .)

We thus have $\displaystyle\sum_{k=0}^{4} n_{k} = 1 + 2 + 7 + 19 + 34 = \boxed{63}$ .

(Additional analysis: Curiously, I'm finding that $n_{5} \gt n_{6}$ , with $n_{5} = 142$ and $n_{6} = 79$ .)

Normally we'd try something like $b^2 - a^2 = (b+a)(b-a)$ , but here that would leave us with an undesirable term $a$ . To incorporate it, we complete the square: $a^2 + a = (a+\tfrac12)^2 - \tfrac14$ , and so $n = b^2 - (a^2 + a) = b^2 - (a+\tfrac12)^2 + \tfrac14\ \ \therefore\ \ 4n-1 = (2b)^2 - (2a+1)^2.$ We define $p = 2b$ and $q = 2a+1$ and so obtain $4n-1 = p^2 - q^2 = (p-q)(p+q) = xy.$

Lemma : For every factorization of the form $4n-1 = xy$ , with $x < y$ , the equation is satisfied with $(a,b) = (\tfrac14(y-x-2),\tfrac14(x+y))$ .

Let's apply this.

• There is always the trivial factorization with $x = 1$ , $y = 4n-1$ . This produces the solution $(a,b) = (n-1,n)$ . However, this solution is invalid for $n = 1$ , which corresponds to the factorization $3 = 1\cdot 3$ . Since there are no other factorizations of 3, we have $S(1) = 0;\ \ n_0 = 1.$
• For all $n > 1$ , if $4n-1$ is prime then this trivial solution is the only one, so that $S(n) = 1$ in that case. This occurs when $n = 2$ : 7 is prime. Therefore $S(2) = 1;\ \ n_1 = 2.$
• The first non-prime happens at $n = 4$ . But the factorization $15 = 3\cdot 5$ results in the solution $(a,b) = (0, 2)$ , which is not valid. Thus $S(4) = 1$ as well.
• The next non-prime is when $n = 7$ . The non-trivial factorization $27 = 3\cdot 9$ gives $(a,b) = (1,3)$ in addition to the trivial solution $(6,7)$ . Therefore $S(7) = 2;\ \ n_2 = 7.$
• Next we look for a value of $4n-1$ that can be factored in at least 3 different ways; it must have at least 6 divisors. This happens when $n = 16$ and $4n-1 = 63$ . But one of the three factorizations is $63 = 7\cdot 9$ , resulting in the invalid solution $(a,b) = (0, 4)$ . Thus $S(16) = 2$ and the search continues.
• We get luckier with $n = 19$ : each of the factorizations $1\cdot 75 = 3\cdot 25 = 5\cdot 15$ produces a valid solution. They are $(a,b) = (18,19);\ (10, 7$ ;\ (2, 5)). So we have $S(19) = 3;\ \ n_3 = 19.$
• Continuing in search of a number with at least eight divisors, we run into $n = 34$ . The factorizations are $1\cdot 135 = 3\cdot 45 = 5\cdot 27 = 9\cdot 15$ , and the corresponding solutions $(a,b) = (33,34);\ (10,12);\ (5, 8);\ (1,6)$ . This finally gives $S(34) = 4;\ \ n_4 = 34.$ To finish up the problem: $\sum n_k = 1 + 2 + 7 + 19 + 34 = \boxed{63}$ .

I thought I would share my solution as my method was slightly different to the ones I found here.

Firstly, the solution to this problem (https://brilliant.org/practice/quadratic-diophantine-equations-level-2-3/) tells us that $n_{0}=1$ .

Since $a, b>0$ , we know $b>a$ , so $b=a+k$ for some positive integer k. I will characterise solutions by this difference, k, considering each possible k and seeing which values of n can have solutions (a,b) with a difference of k.

Substituting $b=a+k$ into the equation:

$a^2+a+n=(a+k)^2$

$a^2+a+n=a^2+2ak+k^2$

$a(1-2k)=k^2-n$

$a=\frac{n-k^2}{2k-1}$

For this to be a valid solution, we need a to be a positive integer, so we need two things: $\frac{n-k^2}{2k-1}$ is an integer, and $a≥1$ (given this, it follows that b is also a positive integer and thus (a,b) is a solution)

$\boxed{k=1}$

$a=\frac{n-1}{1}=n-1≥1$ so $n≥2$ . This is always an integer since n is an integer. $(b=n)$

So there is a " $k=1$ " solution for $n=2,3,4,5,...$

$\boxed{k=2}$

$a=\frac{n-4}{3}≥1$ so $n≥7$ and n is 1 more than a multiple of 3.

So there is a " $k=2$ " solution for $n=7,10,13,16,...$

$\boxed{k=3}$

$a=\frac{n-9}{5}≥1$ so $n≥14$ and n is 1 less than a multiple of 5.

So there is a " $k=3$ " solution for $n=14,19,24,29,..., 14+5m,...$

Repeating this method tells us:

" $k=4$ " solutions for $n=23,30,37,43,...,23+7m,...$

" $k=5$ " solutions for $n=34,43,52,61,...,34+9m,...$

" $k=6$ " solutions for $n=47,58,69,80,...,47+11m,...$

and in general, for a given k, there is a solution when $n=k^2+m(2k-1)$ for $m=1,2,3,...$

Shove this in a spreadsheet and do some stuff and you'll find that

$n_{0}=1$

$n_{1}=2$

$n_{2}=7$

$n_{3}=19$

$n_{4}=34$ and hence $\sum_{k=0}^4 n_{k}=\boxed{63}$

I'm glad you stopped there, because if you had included $n_{5}$ , I may have used $n_{5}=79$ when in fact $S(79)=6$ so $n_{6}=79$ , while $n_{5}=142$

The equation $a^2 +a + n = b^2$ can be written $4n-1 \;=\; (2b + 2a + 1)(2b - 2a -1)$ Since $4n-1$ is never a square, the number of divisors $\sigma_0(4n-1)$ is even, and any pair of factors $4n-1\,=\, uv$ with $u > v \ge 1$ gives a single solution $a,b$ , except when $u = v+2$ , which happens when $n$ is a perfect square. Thus $S(n) \;=\; \left\{ \begin{array}{lll} \tfrac12 \sigma_0(4n-1) & \qquad & n \text{ not a square} \\ \tfrac12\sigma_0(4n-1) - 1 & & n \text{ a square} \end{array} \right.$ Checking gives $S(1)=0$ , $S(2)=1$ , $S(7)=2$ , $S(19)=3$ and $S(34)=4$ are the first occurrences of these values, so the answer is $1+2+7+19+34=\boxed{63}$ .