algorithm - 求 [x/2] y x*y 不能表示的正整数？

Question

有一个表达式:[x/2] + y + x * y，x和y都是正整数，[x/2]表示向下取整，比如[3/2] = 1。这个表达式不能表示正整数，例如1、3。现在的问题是如何快速找出前40个数字？

当x = 1时，表达式为2*y，所以这个数一定不能是偶数。当y = 1时，表达式为[x/2] + x + 1，不包括3*n。然后我尝试如下:

int64_t givean( int n )
{
    if( n == 1 ) return 1;
    if( n == 2 ) return 3;
    int i = 3;
    int count = 2;
    while( true ){
        int64_t m = i * 3;
        bool ok = true;
        for( int x = 3; x <= ( 2*m - 2 ) / 3; x++ ){
           if( ( x / 2 + x + 1 ) >= m ){
               ok = false;
           }
           if( !( ( m - x/2 ) % ( x + 1 ) ) ){
               ok = false;
               break;
           }
        }
        if( ok && ++count == n ){
           return m;
        }
        i += 2;
    }
}

可以快速找到前7个号码，找到第8个号码大约需要2分钟...前 8 个数字是:

1
3
15
63
4095
65535
262143
1073741823

有没有其他高性能算法可以解决这个问题？

Answer 1

这个非常无辜的问题被证明是非常棘手的。让我们分别看看 x 奇数和 x 偶数的情况。

如果x 是奇数，写x = 2k - 1 一些正整数k。那么，我们有

n = (k-1) + y * 2k = 2ky + k - 1 = y(2k+1) - 1

注意y是任意正整数，2k+1是任意大于1的奇数。表达式y*(2k+1) 因此可以生成任何 具有奇数质因数的整数。因此，如果 n+1 有一个奇数质因数，则它有一个解，所以为了使它成为一个非解，n+1 必须是 1 (根本没有质因数)或二的幂。由于 n+1 是非法的(它会使 n 为 0，这不会发生，因为 x 和 y是正整数)，我们得出结论，所有非解决方案 n 必须有 n+1 是二的幂。

因此，对于某个正整数 m，我们可以将所有非解写成 2^m-1。

---

现在让我们看一下 even x 的情况。我们有

n = 2^m-1 = k + y * (2k+1) = k + 2ky + y

看2n+1:

2n+1 = 2^(m+1)-1 = 2k + 4ky + 2y + 1 = (2k + 1)(2y + 1)

2k+1 和 2y+1 是任意奇数。因为 2n+1 总是奇数，所以我们得出结论 2n+1 一定是合数。每个解决方案(对于 x 甚至)都必须具有这种形式。因此，n 是无解当且仅当 n+1 是 2 的幂，并且 2n+1 是素数。

事实上，这意味着 2n+1 是梅森素数，因此前 40 个非解对应于前 40 个梅森素数(给定梅森素数 Mp，对应的非解为(Mp-1)/2)。

---

找到前 40 个 Mersenne 素数的最快算法是上网询问。 (说真的——找到梅森素数是一项艰苦的工作；第 50 个梅森素数甚至还不知道!)前 42 个梅森素数的指数由 OEIS A000043 给出。 :

1       2
2       3
3       5
4       7
5       13
6       17
7       19
8       31
9       61
10      89
11      107
12      127
13      521
14      607
15      1279
16      2203
17      2281
18      3217
19      4253
20      4423
21      9689
22      9941
23      11213
24      19937
25      21701
26      23209
27      44497
28      86243
29      110503
30      132049
31      216091
32      756839
33      859433
34      1257787
35      1398269
36      2976221
37      3021377
38      6972593
39      13466917
40      20996011
41      24036583
42      25964951

因此，例如，第 40 个无解是 2^(20996011-1)-1，这是一个非常大的数字。