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 
{
    p开发者_运维知识库ublic 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;
            }
        }
    }
}

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.

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.

For lots of numbers we can easily see if they might fit a certain X or not:

• Y must be divisible by 3, since at least one of the consecutive numbers must be divisible by 3
• Y must be divisible by 4, since at least one of the consecutive numbers must be divisible by 4

So Y must be at least divisible by 12 (3*4). This means that you can easily throw away about 92% of all numbers.

Since the value of Y will contain at least the 4-th power of X, you could start by taking the 4-th root (or how do you call this in English) of Y, then rounding this of to an integer value, calling it X and calculate the result of X(X+1)(X+2)(X+3).

The result will probably be higher (because we omitted the other factors like X to the power of 3, X to the power of 2, ...).

Now subtract 1 from X and perform the same calculations.

As long the result is higher than Y, repeat this until the result is lower, or you exactly obtained Y.

Count the fourth root of y, round it down and call it a. a(a-1)(a-2)(a-3) is much less than y. Count the fourth root of y, round it up, and call it b. b(b+1)(b+2)(b+3) is much more than y. Now you have three possible numbers to start from: a-2, a-1 and a (note a = b or a = b-1). So it should be enough to check (a-2)(a-1)a(a+1), (a-1)a(a+1)(a+2) and a(a+1)(a+2)(a+3).

Edit: read the question wrongly, but for what it's worth (a quick way to test if it is not a product of four consecutive integers):

Any product of four consecutive integers is equal to one less than a perfect square.

I'd start by getting the fourth-root of 'y'. This would give you an approximation for the smallest factor of y (ie. 'x') that you could use. Use this as the basis of a standard factorisation algorithm.

Answer is very simple.
For given number y if y+1 is not perfect square then y is not product of four consecutive numbers. If y+1 is perfect square then y is product of four consecutive number if and only if sqrt(5+4*sqrt(y+1)) is integer.

Your equation can be simplified as

y = x^4 + 6*x^3 + 11*x^2 + 6x

You can start from x=1 and go upwards to check. We can note a very easy-to-compute upper bound: the 4th root of y (or the square root of the square root of y). Meaning, when you reach that number, you can stop. This is fortunate for you, because luckily for us, 4th roots are very very very very small.

For numbers up to 10,000, this is pretty easy to check, because you're going to check at most ten integers. If your number is under 500, you'll only need to check four integers at most.

At 1,000,000+, you're going to have to start checking 31 and more numbers, so it might start getting less trivial.

UPPER AND LOWER BOUNDS

After some careful refinement due to Wolfram Alpha, two things have been concluded:

1. A more refined upper bound of y^0.25 - 1.2
2. A definite lower bound of y^0.25 - 1.5

so...

y = num_to_check
k = Math.sqrt(Math.sqrt(y))   # or Math.pow(y,0.25)
lower = int(k-1.5)
upper = int(Math.ceil(k-1.2))
for n in (lower...upper)
  if n * (n+1) * (n+2) * (n+3) == y
    return n
  end
end
return nil

Note that in this case, there are a maximum of two numbers to be checked for any given y.

edit: after refining x to only the integers, it appears that there is only one number to check, in all cases, as your range reduces to one number. Cool! (thanks to Brian)

As others have said, start with the 4th root of y (let's call it z).

Out of the sequence x, x+1,...x+3, we know that some values must be less than z, and some must be greater than z (since they can't all be equal to z).

So, we know that

x <= ceiling(z)
x+3 >= floor(z)

That gives you a very small range of numbers to try for x.