Find four consecutive numbers that sum to given number

Question

Suppose there is a given number we should test if it is product of four consecutive numbers?

So if y is our given number we should test if y = x(x+1)(x+2)(x+3) for any arbitrary x?

How to design an algorithm for this problem?

I have done it like this:

import java.util.*;

public class Product 
{
    public static int product(int i)
    {
         return i * (i+1) * (i+2) * (i+3);
    }

    public static void main(String[] args) 
    {
        Scanner scnr = new Scanner(System.in);
        int x = scnr.nextInt();
        for (int i = 0; i < x/2; i++)
        {
            if (product(i) == x)
            {
                System.out.println("number is product of 4 consecutive numbers");
                break;
            }
        }
    }
}

Answer 1

Starting with

y = x(x+1)(x+2)(x+3) = x^4 + 6x^3 + 11x^2 + 6x

Notice that the coefficients almost look symmetric, but there's no 1 at the end.

So suppose that

y = z^2 - 1

i.e.

z^2 = x^4 + 6x^3 + 11x^2 + 6x + 1 

There are coefficients of all powers of x up to 4, and those of x^4 and x^0 are 1, so we need to find the coefficient of x^1, which we call a:

z = (x^2 + ax + 1)^2 = x^4 + 2ax^3 + (2+a^2)x^2 + 2ax + 1

comparing coefficient of x^1, x^2, or x^3 gives a = 3

(the equations above do not require that any of x,y or z is an integer, but will possibly lose complex or negative roots we are not interested in)

so we can solve a quadratic for x:

x^2 + 3x + 1 - sqrt(y+1) = 0

gives

x = -3 +/- sqrt(9 - 4 * (1-sqrt(y+1))) 
    ---------------------------------
                2

  = -3 +/- sqrt(5 + 4 sqrt(y+1)) 
    ----------------------------
                2

which will be an integer if sqrt(y+1) is a perfect square z, and (5+4z) is also a perfect square (if z is an integer, 5-4z is odd, so its square root, if an integer, is also odd and x will be an integer).

So test whether z = sqrt(y+1) is an integer, then test whether 5+4z is a perfect square.

Answer 2

You only need to test floor(y**(0.25)-1). As y approaches infinity, x approaches y**0.25-1.5 (from underneath).

To some extent, this is rather intuitive. x*(x+1)*(x+2)*(x+3) is a product of four numbers whose average is equal to x+1.5. When x is high, 1.5 looks small.