Solution 1:

This is a famous class of elliptic curves, called Mordell's equation, or sometimes Mordell-Bachet equation. See also here, or here for some discussions on MSE. For a specific example with $k=2000000$ see also here. A further reference is this article by Keith Conrad.