整数\(n, -10^{14}\leq X\leq 10^{14}\)に対して\(n^2+n+X\)が平方数になるとします.

このとき上界として以下が得られます.

\[n^2+n+X \leq |n|^2+|n|+10^{14} \leq (|n|+10^7)^2 \]

さらに下界として以下が得られます.

• \(|n|\leq10^7\)のとき

\[(|n|-|n|)^2=0\leq n^2+n+X\]

• \(|n|\gt10^7\)のとき

\[ \begin{aligned} (|n|-10^7)^2 &= |n|^2 - 2\cdot 10^7 |n| + 10^{14} \\ &= |n|^2 - |n| - (2\cdot 10^7 - 1) |n| + 10^{14} \\ &\leq |n|^2 - |n| - (2\cdot 10^7 - 1) (10^7+1) + 10^{14} \\ &= |n|^2 - |n| - 10^{14} -10^7+1\\ &\lt n^2+n+X \end{aligned} \]

よってある整数\(-10^7\leq k\leq 10^7\)が存在し, \(n^2+n+X =(|n|+k)^2\)を満たします.

これを解くと\(n=\dfrac{k^2-X}{1\pm2k}\)が得られます.

したがってこの範囲の\(k\)に対し条件を満たすか調べれば解くことができます. (\((n+k)^2=(-n-k)^2\)であることを考えれば実際には\(\pm\)の両方の符号を調べる必要はなく, 片方について全て調べれば十分です. )