1

Golomb 的自描述数列 {G(n)} 是唯一的自然数非递减数列，使得 n 在数列中恰好出现 G(n) 次。前几个 n 的 G(n) 值为

n       1   2   3   4   5   6   7   8   9   10  11  12  
G(n)    1   2   2   3   3   4   4   4   5   5   5   6

假设 G(10^3)​​ = 86，G(10^6) = 6137。还假设 ΣG(n^3) = 153506976，对于 1 <= n < 10^3。

对于 1<= n< 10^6，求 ΣG(n^3)。很容易编码掉找到数字序列的公式。但是有没有办法跟踪 G(10^3)​​ 和 G(10^6) 之间的数学关系，以便找到总和高达 10^6 的代码可以优化吗？

4

2 回答 2

5

根据OEIS，我们有：

G(1) = 1
G(n+1) = 1 + G(n + 1 - G(G(n)))

如果您生成序列一段时间，您会注意到重复k次数的组的大小为k * G(k). 例如，重复 2 次的组的大小是多少？2 * G(2) = 4: 2 2 3 3. 那些重复3次的？3 * G(3) = 6: 4 4 4 5 5 5（6重复4几次）。

请注意，总和ig(k) = sum i * G(i), i <= k为您提供了重复 1、2、...、k次的组的大小，因此它告诉您重复k次数的组在哪里结束。

这个 OEIS 公式也很有帮助：

for G(1) + G(2)+ ... + G(n-1) < k <= G(1) + G(2) + ... + G(n) = sg(n)
we have G(k) = n

使用它，您只需计算几个 的值G就可以找到大量的值。例如，让我们找到G(10^6)：

首先，找到k这样的k*G[k] < 10^6 <= (k + 1)*G[k + 1]。这将有助于告诉您该组G[10^6]所在的位置，以及它的价值。

找到这k将意味着它G(10^6)在一组 size 中k + 1。

我使用这个 C++ 程序来找到这个值：

int g[200000], ig[200000];

int main()
{
    g[1] = 1;
    ig[1] = 1;
    for (int i = 2; i < 1000; ++i) {
        g[i] = 1 + g[i - g[g[i - 1]]];
        ig[i] = ig[i - 1] + i * g[i];
    }

    int k = 1;
    while (ig[k] < 1000000) // 10^6
    {
        ++k;
    }

    cout << k - 1 << ' ' << ig[k - 1] << endl;
    cout << k << ' ' << ig[k] << endl;

    return 0;
}

这使：

k        k * G[k]       k + 1      (k + 1) * G[k + 1]
263      998827         264        1008859

现在您需要使用 精确定位确切的组sg：您可以通过使用相邻值n之间的插值在 OEIS 公式中找到 。ig

这意味着：

G(10^6) = sg(k = 263) + (ig(k + 1 = 264) - ig(k = 263)) / (k + 1 = 264)

获得答案的确切解决方案和您需要计算的值的数量留作练习，询问您在此过程中是否有任何问题。

于 2012-10-08T18:58:56.537 回答
3

由于您正在研究https://projecteuler.net/problem=341，我认为直接回答这个问题将是一个剧透。但是，如果您正确地解决了那里的特定问题（无论多么不理想），该网站会让您在那里看到关于优化技术的有趣讨论。

于 2013-07-23T01:34:43.340 回答