找到与给定数字相加的四个连续数字

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是一个完美的正方形.

Answer 2

你只需要测试floor(y**(0.25)-1).随着y接近无穷大,x接近y**0.25-1.5(从下面).

在某种程度上,这是相当直观的. x*(x+1)*(x+2)*(x+3)是四个数的乘积,其平均值等于x+1.5.当x高时,1.5看起来很小.

Answer 3

对于很多数字,我们可以很容易地看出它们是否适合某个X:

• Y必须可被3整除,因为至少有一个连续数字必须可被3整除
• Y必须可被4整除,因为至少有一个连续数字必须可被4整除

所以Y必须至少能被12(3*4)整除.这意味着您可以轻松丢弃所有数字的92%.

由于Y的值至少包含X的4次方,你可以从Y的第4个根(或者你用英语怎么称)开始,然后将其舍入为整数值,调用它X并计算X(X + 1)(X + 2)(X + 3)的结果.

结果可能会更高(因为我们省略了其他因素,如X为3的幂,X为2的幂,......).

现在从X中减去1并执行相同的计算.

只要结果高于Y,重复此操作直到结果更低,或者您完全获得Y.

Answer 4

编辑:错误地阅读问题,但是对于它的价值(快速测试它是否不是四个连续整数的乘积):

连续四个整数任何产品是等于一个比一个完美的正方形.

Answer 5

计算第四个根y,将其向下舍入并调用它a.a(a-1)(a-2)(a-3)比...少得多y.计算第四个根y,将其四舍五入,然后调用它b.b(b+1)(b+2)(b+3)不仅仅是y.现在,你有三种可能的数字从开始:a-2,a-1和a(注a = b或a = b-1).所以它应该足以检查(a-2)(a-1)a(a+1),(a-1)a(a+1)(a+2)并且a(a+1)(a+2)(a+3).