Distribution of integer solution pairs (x,y) for $2x^2 = y^2 + y$

Question

I am looking for integer pairs $(x,y)$ that respect $$2x^2 = y^2 + y$$

For example $(6,8)$ is a solution for that. Simple solution is to enumerate on $x$ or $y$ and test if the corresponding variable is an integer. However, I am searching for number too big to enumerate and test (just takes too long). By enumerating, I noticed that the values for $x$ increase by a factor around $5$ or $6$ every solution. This pattern I see with the first $17$ solutions, but I cannot figure out how to describe that pattern. Solution number $17$ took $8$ hours computation since solution $16$, and computation time increases by the same factor $5$ or $6$, so finding solution 18 or further is not doable by just enumerating.

Is there a way to predict where the next integer pair will be?

Thanks

Answer 1

You are looking for solutions to Pell's equation: If you multiply both sides of $2x^2=y^2+y$ by $4$, you can rewrite it as

$$8x^2=(2y+1)^2-1$$

which can be rewritten as

$$u^2-8x^2=1$$

with $u=2y+1$. The "fundamental solution" is $(u+x\sqrt8)(u-x\sqrt8)=(3+\sqrt8)(3-\sqrt8)$, and all other solutions are expansions of $(3+\sqrt8)^n$. For example $(3+\sqrt8)^2=17+6\sqrt8$ gives $x=6$ and $u=17$, which corresponds to $y=8$. Once you've computed $(3+\sqrt8)^n$ as $u_n+x_n\sqrt8$, you can get $(u_{n+1},x_{n+1})$ from $u_{n+1}+x_{n+1}\sqrt8=(3+\sqrt8)(u_n+x_n\sqrt8)=(3u_n+8x_n)+(u_n+3x_n)\sqrt8$.

Remark: I should have noted that this procedure produces the solutions with positive values of $u$ and $x$. You can, or course, stick a negative sign in front of either variable. Finally, if $x=0$, there are the two solutions, $u=1$ and $u=-1$, corresponding to $y=0$ and $=-1$.

Answer 2

If you have an equation $2x^2 = y^2+y = y(y+1)$, then, since $y$ and $y+1$ are coprime, either $y$ is a square and $y+1$ twice a square, or $y$ is twice a square and $y+1$ a square. Either way, $y$ corresponds to a solution of

$$k^2 - 2m^2 = \pm 1.\tag{1}$$

The (positive) integer solutions are obtained from the powers of $1+\sqrt{2}$, if $k_n + m_n\sqrt{2} = (1+\sqrt{2})^n$, then

$$k_n^2 - 2 m_n^2 = (-1)^n,$$

and we obtain the possible values for $y$ as the $k_{2n+1}^2 = 2m_{2n+1}^2-1$ resp. $2m_{2n}^2 = k_{2n}^2-1$.

Since $k_{n+1} + m_{n+1}\sqrt{2} = (1+\sqrt{2})(k_n+m_n\sqrt{2}) = k_n + 2m_n + (k_n + m_n)\sqrt{2}$, it is easy to obtain the next $(k,m)$ pair from any particular, and via that, you also get a recurrence for the $(x,y)$ pairs.

Answer 3

You can use any non-negative integer $n$ in order to generate an integer solution for $x$ and $y$:

• $\displaystyle x=\pm\frac{{(3-2\sqrt{2})}^{n}-{(3+2\sqrt{2})}^{n}}{4\sqrt{2}}$

• $\displaystyle y=\frac{(3-2\sqrt{2})^n+(3+2\sqrt{2})^n-2}{4}$

Answer 4

It is clear that decisions are determined by the Pell equation, but I think the record is not a lot easier to read easier.

Of course the solution of equation: $$Y^2=\frac{X(X\pm1)}{2}$$

Defined solutions of Pell's equation: $$p^2-2s^2=\pm1$$

But it is necessary to write the formula describing their solutions through solving Pell's equation: $$X=p^2+4ps+4s^2$$ $$Y=p^2+3ps+2s^2$$

And more. $$X=2s^2$$ $$Y=ps$$ $p,s$ - These numbers can be any character.

If you need to have a solution of the equation: $$Y^2=\frac{X(X\pm{a})}{2}$$

It is necessary to substitute into the formulas uravneniyaPellya solutions: $$p^2-2s^2=\pm{a}$$

Answer 5

Apologies for the non-mathematical response, but maybe it is considered helpful nevertheless:

It seems like the sequence of the x-values can be written as

$x_0 = 1$

$x_1 = 6$

$x_n = 6 x_{n-1} - x_{n-2}$

Based on this, one can directly enumerate the x-values and solve for y.

If this is correct, the first results should be

1, 1
6, 8
35, 49
204, 288
1189, 1681
6930, 9800
40391, 57121
235416, 332928
1372105, 1940449
7997214, 11309768
46611179, 65918161
271669860, 384199200
1583407981, 2239277041
9228778026, 13051463048
53789260175, 76069501249
313506783024, 443365544448
1827251437969, 2584123765441
10650001844790, 15061377048200
62072759630771, 87784138523761
361786555939836, 511643454094368
2108646576008245, 2982076586042449
12290092900109634, 17380816062160328

These have been computed (within a few milliseconds, of course) with the following program (implemented in Java)

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;

public class EquationTest
{
    public static void main(String[] args)
    {
        BigInteger SIX = BigInteger.valueOf(6);
        BigInteger x0 = BigInteger.valueOf(1);
        BigInteger x1 = BigInteger.valueOf(6);
        for (int i=0; i<100; i++)
        {
            BigInteger x = x1.multiply(SIX);
            x = x.subtract(x0);
            BigInteger xx = x.multiply(x);
            BigInteger t = xx.add(xx);
            BigDecimal z = new BigDecimal(t.toString(10));
            BigDecimal minusPHalf = BigDecimal.valueOf(-0.5);
            BigDecimal pHalfPow2 = BigDecimal.valueOf(0.25);
            BigDecimal disc = pHalfPow2.add(z);
            BigDecimal r = minusPHalf.add(bigSqrt(disc));
            String s = r.toString();
            BigInteger y = new BigInteger(s.substring(0, s.indexOf(".")));
            System.out.println(x+", "+y+" correct? "+verify(x, y));
            x0 = x1;
            x1 = x;
        }
    }

    private static boolean verify(BigInteger x, BigInteger y)
    {
        BigInteger a = BigInteger.valueOf(2).multiply(x).multiply(x);
        BigInteger b = y.multiply(y).add(y);
        return a.equals(b);
    }


    // From http://stackoverflow.com/questions/13649703/square-root-of-bigdecimal-in-java
    private static final BigDecimal SQRT_DIG = new BigDecimal(150);
    private static final BigDecimal SQRT_PRE = new BigDecimal(10).pow(SQRT_DIG.intValue());

    /**
     * Private utility method used to compute the square root of a BigDecimal.
     * 
     * @author Luciano Culacciatti 
     * @url http://www.codeproject.com/Tips/257031/Implementing-SqrtRoot-in-BigDecimal
     */
    private static BigDecimal sqrtNewtonRaphson  (BigDecimal c, BigDecimal xn, BigDecimal precision){
        BigDecimal fx = xn.pow(2).add(c.negate());
        BigDecimal fpx = xn.multiply(new BigDecimal(2));
        BigDecimal xn1 = fx.divide(fpx,2*SQRT_DIG.intValue(),RoundingMode.HALF_DOWN);
        xn1 = xn.add(xn1.negate());
        BigDecimal currentSquare = xn1.pow(2);
        BigDecimal currentPrecision = currentSquare.subtract(c);
        currentPrecision = currentPrecision.abs();
        if (currentPrecision.compareTo(precision) <= -1){
            return xn1;
        }
        return sqrtNewtonRaphson(c, xn1, precision);
    }

    /**
     * Uses Newton Raphson to compute the square root of a BigDecimal.
     * 
     * @author Luciano Culacciatti 
     * @url http://www.codeproject.com/Tips/257031/Implementing-SqrtRoot-in-BigDecimal
     */
    public static BigDecimal bigSqrt(BigDecimal c){
        return sqrtNewtonRaphson(c,new BigDecimal(1),new BigDecimal(1).divide(SQRT_PRE));
    }
}

(Note: I have not verified the square root method)