algorithm - 找出四个相加等于给定数字的连续数字

Question

假设有一个给定的数字，我们应该测试它是否是四个连续数字的乘积？

因此，如果 y 是我们给定的数字，我们应该测试 y = x(x+1)(x+2)(x+3) 是否为任意 x?

如何针对这个问题设计算法？

我是这样做的:

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

开始于

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

请注意，系数看起来几乎是对称的，但末尾没有 1。

那么假设

y = z^2 - 1

即

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

x到4的所有次方的系数都有，x^4和x^0的系数都是1，所以需要求x^1的系数，我们称之为a:

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

比较 x^1、x^2 或 x^3 的系数得到 a = 3

(上面的等式不要求 x,y 或 z 中的任何一个是整数，但可能会丢失我们不感兴趣的复根或负根)

所以我们可以求解 x 的二次方程:

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

给予

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

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

如果 sqrt(y+1) 是一个完美的正方形 z 并且 (5+4z) 也是一个整数一个完美的平方(如果 z 是一个整数，5-4z 是奇数，所以它的平方根，如果是一个整数，也是奇数并且 x 将是一个整数)。

所以测试z = sqrt(y+1)是否是一个整数，然后测试5+4z是否是一个完美的正方形。