Problem. Given two natural numbers $a, b$ so that $ab+ \left ( a+ 1 \right )\left ( b+ 1 \right )= 2n= fixed,$ by programmin' find $a\left ( a\leq b \right )$ such that $b- a$ at the least.
I haven't been good at solving Diophantine-equations and commanding computer to do it. Seems like there exists no sequences like this on oeis.org., what I did by myself is transforming the problem into the acquainted one. My idea is using discriminants..
- First, $b- a$ at the least meaning $\left ( a+ b \right )^{2}- 4ab$ at the least,
- Second, $$ab+ \left ( a+ 1 \right )\left ( b+ 1 \right )= 2n\Rightarrow 2ab= 2n- a- b- 1$$ That means $\left ( a+ b \right )^{2}+ 2\left ( a+ b \right )+ 2-4n$ at the least, but in natural interval, what I can only do is checking the discriminant, which is a square,
$$4n- 1= m^{2}$$
Is that all for my problem, I need to your help, thank you.
Manipulate the given equation as follows $$ab + (a+1)(b+1) = 2n$$ $$2ab + a + b + 1 = 2n$$ $$4ab + 2a + 2b + 1 = 4n-1$$ $$(2a-1)(2b-1) = 4n-1$$ Now, you just need to factor $4n-1$ into two factors which are as close together as possible.
A naive approach is to set $f = \lfloor \sqrt{4n-1} \rfloor$, and while $f \not\mid 4n-1$, decrement $f$. When this terminates, $f$ will be the largest factor of $4n-1$ that is less than or equal to $\sqrt{4n-1}$. Then $\tfrac{4n-1}{f}$ will be the smallest factor of $4n-1$ that is greater than or equal to $\sqrt{4n-1}$. So $2a-1 = f$ and $2b-1 = \tfrac{4n-1}{f}$.
It might be better to compute the prime factorization of $4n-1$ and then list out the factors. Set $2a-1$ and $2b-1$ to be the middle two factors if $4n-1$ is not a perfect square, and set $2a-1 = 2b-1 = \sqrt{4n-1}$ if $4n-1$ is a perfect square.