$ k x^2 +4x = n $, Algorithm or any other method needed

Question

I want to find any $n < 10^{18} $ so that the equation below has at least two pairs of solutions $(k, x)$

$ k x^2 +4 x = n $

constraints: $x > 10^6; \; x > k ; \; k, x \in \mathbb{N}$

I can not solve this mathematically, nor I can think of any fast brute-force algorithm. Is there any integer programming method which deals with such kind of problem?

Answer 1

Take $$(k_1,x_1)=(500004,1000002)$$ $$(k_2,x_2)=(500000,1000006)$$ Then, $$k_1x_1^2 + 4x_1 = k_2x_2^2 + 4x_2 = 500006000022000024$$

---

More generally, any integer $S$ can be used to produce an at-least-twice-expressible number: $$(k_1,x_1)=(S+4, 2S+2)$$ $$(k_2,x_2)=(S,2S+6)$$ both result in $$n=4(S+1)(S+2)(S+3)$$

Answer 2

My thoughts go to Pell’s equation, my favorite. $k x^2 +4x = n$

$n-4x-kx^2=0$ or $(n-4x+1)-kx^2=1$

We need $(n-4x+1)= a^2$ (eq.1) so that we have $a^2-kx^2=1$

We know a number of cases where Pell’s equation is given of simple expression:

$a^2-(a^2-1)1^2=1$ this is the case for $d=a^2-1, a^2-2, a^2+1, a^2+2$ and d=n(n+1).

If we take the simplest $d=a^2-1$ and $x=1$ we have for (eq.1)

$n-4x+1 =a^2$ x=1 implies $n=a^2+3$ Take the first, a=2, which gives us n=4 which implies k=3 and x=1

This obviously only give one solution but would perhaps be a starting point for finding nr 2 (or perhaps not).

The solutions are often very high and may violate the requirement on n.However, I notice that Košinár’s solution k= 500 004 has the very short Pell's equation solution x =470935, y =666
($x^2-500004 y^2=1$)

Edit: It occurs to me that if you have a lot of calculating power (as e.g. Košinár has) then you don't need to restrict yourself to the simple cases $d=a^2+-1,a^2+-2$ such as I would need to.

EDIT2: I forgot the last step in my earlier version I rewrite the equation $ky^2+4y=n$ $(n-4y+1)-ky^2=1$ so that $(n-4y+1)=x^2$ in Pell’s equation which always has a solution. I use the relation $(2a^2-1)^2-(a^2-1)(2a)^2=1$,so that $x=2a^2-1$,$ k=(a^2-1)$ and $y=2a$ As I mentioned above we get

$x^2=n-4y+1= n-8*a+1 =(2*a^2-1)^2$

for a=1,2,3,4 we get n=8,64,312,992 etc and we now check if this equation’s other roots are integers.

This is a algorithm (it is at least a series of instructions) but there is no guarantee it will find a solution. I went through the first 13 solutions up to n= 113672 and all the second real solutions look terrible.

We can redo it for the other well known relations of Pell’s equation still without guarantees.