When will the sequence $k \mapsto A + Bk + k^2$ yield a perfect square?

Question

Consider the following sequence:

$$a(k) = A + Bk + k^2 ,$$

where $A$ and $B$ are both integers, and $A < B$ ($k$ is of course an integer variable, B is even).

Problem:

For which $k^*$ is $a(k^*) = r^2$ (in other words for which $k$ the given sequence will yield a perfect square)?

Thanks in advance for any advice.

Answer 1

Here is the beginning of a systematic method in the case $B$ even, $B=2B'$:

"Complete the square" i.e., write your expression in the form

$$A'+(B'+k)^2=s^2 \ \ \ \leftrightarrow \ \ \ A'=(s-k-B')(s+k+B')$$

where $A'=A-B'^2$.

You have now to adjust the two parameters $k$ and $s$, but it opens the way for a systematic search by computer.

Answer 2

This seems to be a quadratic Diophantine equation $$ X^2 + B X - Y^2 + A = 0 \quad (*) \\ $$ in the unknowns $X, Y$ with $A, B, X, Y \in \mathbb{Z}$ and additional constraints $$ A < B\\ B \bmod 2 = 0 $$ where the particular $Y$ is not of interest, just that it exists.

Here is a page with algorithm and calculator for $(*)$. It must then be checked if such solutions honor the additional constraints.

The later introduced condition, that $B$ is even, allows to transform $(*)$ into the simpler equation $$ X^2 + B X - Y^2 + A = 0 \iff \\ (X + B/2)^2 - Y^2 + A - (B/2)^2 = 0 \iff \\ (X')^2 - Y^2 + (A - (B/2)^2) = 0 \iff \\ (X')^2 - Y^2 = N \quad (**) $$ with $X' = X + B/2$ and $N = (B/2)^2 - A$. This is called a generalized Pell's equation (the case $N=1$ is called a Pell's equation), see here.

Answer 3

By repeatedly replacing $k$ by either $k-1,$ or repeatedly by $k+1,$ we can demand that $0 \leq B < 2.$ This will alter $A,$ let us now call it $C.$ This is simply Gauss reduction, if you think in terms of the quadratic form $f(k,j)=k^2 + B k j + A j^2.$

Two sub-problems only:

$$k^2 + C = u^2$$

$$ k^2 + k + C = v^2 $$

$k^2 + C = u^2$ becomes $u^2 - k^2 = C.$ There is at least one solution as long as $C \neq 2 \pmod 4.$ Then write $C = mn,$ with $m \equiv n \pmod 2,$ and then $u-k=m, u+k = n$

$ k^2 + k + C = v^2 $ becomes $4 k^2 + 4k + 4C = 4v^2, $ $4 k^2 + 4k + 1 +(4C - 1 ) = 4v^2, $ $ (2k+1)^2 + (4C-1) = 4v^2. $ Or $ (4C-1) = 4v^2 - (2k+1)^2 $ and. Write all factorings, including negative, for $4C-1 = mn,$ so that $m,n$ are both odd, agree $\pmod 2,$ so we can then solve $2v-2k-1 = m,$ $2v+2k+1 = n.$

Answer 4

Short answer: If you can factor $B^2 - 4A$, there is an effective procedure to find solutions for $k$.

Suppose $A+B+k^2 = r^2$. Then $$ k = \frac{1}{2}\left( -B \pm \sqrt{-4A + B^2 + 4 r^2} \right) \text{.} $$ Already nicer, no term linear in $k$. So suppose $-4A + B^2 + 4 r^2 = s^2$. Then $$ r = \pm \frac{1}{2} \sqrt{4A - B^2 + s^2} \text{.} $$ Getting simpler... So suppose $4A - B^2 + s^2 = t^2$. Then $$ s = \pm\sqrt{-4A + B^2 + t^2} \text{.} $$ And we stop, because (1) this is about as simple as this sort of expression can get, (2) continuing two more steps beings us back to this equation, and (3) the next step is pretty much the same (only changes the signs of $4A - B^2$).

Now this last equation says $$ s^2 - t^2 = (s+t)(s-t) = B^2 - 4A $$ so further progress depends on factorization of $B^2 - 4A$. This is a common rquirement for solving variants of Pell equations. (See Hardy, K.; Muskat, J. B.; and Williams, K. S. "A Deterministic Algorithm for Solving $n=fu^2+gv^2$ in Coprime Integers u and v." Math. Comput. 55, 327-343, 1990.)(See also Robertson, J. "Solving the generalized Pell equation $x^2 − D y^2 = N$".)

For your example in the comments to the Question, you give $A = 67290798539959189308492380660371729680847996127544$ and $B = 156082287421605062049158293357937484075620027600780$. I don't know how to factor this $B^2 - 4A$, but I can factor it for $A = 67290798539959189308492380660371729680847996127544$ and $B = 15608228742160506204915829335793748$ (which is the same except I've chopped off the tail of $B$). For this choice, $$ n = B^2 - 4A = 2^4 \times 17 \times 199039 \times 310867027 \times 1943730433 \times 623415512339964828920869528942638293 $$ is its factorization into primes. Cutting this factorizations into pairs $(f, n/f)$, we get 160 pairs, starting with $(1,n)$ and ending with $(390777578750325841604290401088496, 623415512339964828920869528942638293)$ (sorted by first entry). The last pair says \begin{align*} s-t &= 390777578750325841604290401088496, \\ s+t &= 623415512339964828920869528942638293 \end{align*} so \begin{align*} s &= \frac{1}{2}(390777578750325841604290401088496 + 623415512339964828920869528942638293), \\ t &= \frac{1}{2}(623415512339964828920869528942638293 - 390777578750325841604290401088496) \text{,} \end{align*} which are not integers. Eliminating the pairs which don't leave integers for $s$ and $t$, we are left with 96 pairs. The last of these is $(195388789375162920802145200544248,$ $1246831024679929657841739057885276586)$, so $s = 10623513206734652410381270601542910417$, $t = 10623317817945277247460468456342366169$. Tracking back through our equations, this gives $$ r = \pm \frac{3}{2} \sqrt{1253986547076234555535695745438155722542742227874253722939659385796397 0729} $$ which is again not an integer. Restricting to pairs that give an integer for $r$, we are left with 32 pairs. Restricting to pairs that give an integer for $k$, we are left with one pair and then $k = -15226050279225333588533484146336583979006836353230520139679243607958$. Your choice of word, "sequence", suggests that you are only interested in $k>0$, so there is no solution of the form you desire for this choice of $A$ and $B$.