2

有一个表达式：[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个数字可以很快找到，找到第八个数字大约需要2分钟......前8个数字是：

1
3
15
63
4095
65535
262143
1073741823

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

4

1 回答 1

7

这个非常无辜的问题原来是相当棘手的。让我们分别看看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（根本没有素因数），要么是 2 的幂。由于n+1是非法的（它会变成n0，这不会发生，因为x并且y是正整数），我们得出结论，所有非解决方案n必须n+1是 2 的幂。

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

现在让我们看看 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 个梅森素数的最快算法是上网查询。（说真的——找到梅森素数是一项艰巨的工作；甚至还不知道第 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，这是一个非常大的数字。

于 2013-08-13T05:43:02.970 回答