确定一个数字是否由两个其他数的乘积之和的算法

Question

假设它被指定为2k+2+3p=n作为测试，那么如何确定测试是真的，因为当k>=0, p>=0, n>=0时，一个数字是有效的

example1 : n=24应该是true，因为k=5 & p=4 => 2(5)+2+3(4)=24 example2 : n=11应该是true，因为k=0 & p=3 => 2(0)+2+3(3)=11 example3 : n=15应该是true，因为k=5 & p=1 => 2(5)+2+3(1)=15

我想知道这是否有一个数学的解决办法。我解决了这件事，就像这样：

//let say 2k+2+3p=n
var accepted = false;
var betterNumber= n-2;
//assume p=0
var kReminder= (betterNumber)%2==0;
//assume k=0
var pReminder= (betterNumber)%3==0;

if (kReminder || pReminder){
    accepted=true;
}else{
    
    var biggerChunk= Math.Max(2,3); //max of 2k or 3p, here i try to find the bigger chunk of the 
    var smallerChunk= Math.Min(2,3);

    if ((betterNumber%bigger)%smallerChunk==0){
        accepted=true;
    }else
    {
        accepted=false;
    }    
}

但还是有一些我没看到的边缘病例。所以我想知道它是否有一个更好的解决方案。

更新

上面的测试只是一个例子。该解决方案对于大数字或任何数字组合(如1000000k+37383993+37326328393p=747437446239902 )都应该是有效的。

Answer 1

戴夫已经给出了一个有建设性和有效率的答案，但我想分享一下背后的一些数学。

在一段时间内，我将忽略+ 2部分，因为它不太重要，并集中讨论这个问题的一个泛型:给定两个正整数a和b，检查数字X是否可以表示为k*a + m*b，其中k和m是非负整数。扩展欧氏算法基本上保证：

1. 如果数字X不能被GCD(a,b)整除，则它不能表示为带有整数k和m的k*a + m*b
2. 如果数字X可被GCD(a,b)整除，且大于或等于a*b，则可以表示为具有非负整数k和m的k*a + m*b。这源于这样一个事实，即d = GCD(a,b)可以用这样的形式表示(让我们称之为d = k0*a + m0*b)。如果是X = Y*d，那么X = (Y*k0)*a + (Y*m0)*b.如果这两个系数中的一个是负的，您可以用一个来交换另一个，添加和减去a*b的次数与X = (Y*k0 + b)*a + (Y*m0 - a)*b中所需的一样多。由于X >= a*b，你总是可以得到这两个系数都是非负的，在这种情况下。(注:这显然不是找到合适的系数对的最有效的方法，但是既然你只要求这些系数是否存在，那么它就足够了。)
3. 因此，唯一的灰色区域是数字X，它可以被位于(0, a*b)范围内的GCD(a,b)整除。我不知道关于这个领域的任何一般规则，但是你可以明确地检查它。

所以你只需做#3中描述的预计算，然后你就可以立即回答这个问题，简单的比较+可能检查根据预先计算的(0, a*b)范围的布尔值数组。

如果您的实际问题是关于k*a + m*b + c表单，其中a、b和c是固定的，那么通过从X中减去c就可以很容易地转换成k*a + m*b问题。

更新( a和b的大值)

如果您的a和b很大，所以无法预先缓存(0, a*b)范围，那么我唯一的想法是根据需要通过一个合理有效的算法检查该范围内的值。代码是这样的：

function egcd(a0, b0) {
    let a = a0;
    let b = b0;
    let ca = [1, 0];
    let cb = [0, 1];

    while ((a !== b) && (b !== 0)) {
        let r = a % b;
        let q = (a - r) / b;
        let cr = [ca[0] - q * cb[0], ca[1] - q * cb[1]];
        a = b;
        ca = cb;
        b = r;
        cb = cr;
    }

    return {
        gcd: a,
        coef: ca
    };
}

function check(a, b, x) {
    let eg = egcd(a, b);
    let gcd = eg.gcd;
    let c0 = eg.coef;

    if (x % gcd !== 0)
        return false;

    if (x >= a * b)
        return true;

    let c1a = c0[0] * x / gcd;
    let c1b = c0[1] * x / gcd;
    if (c1a < 0) {
        let fixMul = -Math.floor(c1a / (b / gcd));
        let c1bFixed = c1b - fixMul * (a / gcd);
        return c1bFixed >= 0;
    }
    else { //c1b < 0
        let fixMul = -Math.floor(c1b / (a / gcd));
        let c1aFixed = c1a - fixMul * (b / gcd);
        return c1aFixed >= 0;
    }
}

这段代码背后的思想是基于上面第2步中描述的逻辑：

1. 使用扩展的欧几里得算法计算GCD和Bézout系数(如果a和b是固定的，则可以缓存，但即使没有，这也是相当快的)。
2. 检查上述条件#1 (绝对否)和#2 (绝对是)。
3. 对于(0, a*b)范围内的值，只需将Bézout系数乘以X/gcd来修正一些系数。F
4. 找出两者中的哪一个是负的，并通过用一个系数换另一个系数来找出修正它的最小乘数。
5. 将此乘数应用于另一个(最初为正)系数，并检查它是否仍为正。

该算法之所以有效，是因为X = k*a + m*b的所有可能的解都可以从某个基解(k0, m0)中得到，它可以作为整数n的(k0 + n*b/gcd, m0 + n*a/gcd)。因此，要找出是否存在k >= 0和m >= 0的解，只需找到最小正k的解，并检查m。

该算法的复杂度主要由对数扩展的欧几里德算法控制。如果它可以被缓存，其他的一切都是恒定的时间。

Answer 2

经检验，2是最小有效偶数，5是最小有效奇数：

2 is valid (k=0, p=0)
5 is valid (k=0, p=1)

All even numbers >= 2 and all odd numbers >= 5 are valid.
Even numbers: k=n/2-1, p=0
odd numbers: k=(n-3)/2-1, p=1

我们在这里做的是增加k，把2s加到最小的有效偶数和奇数上，得到更大的偶数和奇数。

除3外，n >= 2的所有值都是有效的。

Answer 3

定理:用这个公式可以表示数字2和任意数>= 4。

答案:最简单的测试是检查这个数字是等于2，还是大于或等于4。

证明：n=2k+2+3p其中k>=0, p>=0, n>=0与n=2m+3p m>0, p>=0和m=k+1相同。使用p=0可以表示任何偶数，例如，使用m=10，可以表示n=20。这个偶数左边的奇数可以用m'=m-2, p=1表示，例如19=2*8+3。右边的奇数可以用m'=m-1, p=1表示，例如21=2*9+3。此规则适用于m大于或等于3，即从n=5开始。很容易看出，对于p=0，还有两个额外的值，n=2，n=4。