哥伦布序列

Question

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 的代码可以优化吗？

Answer 1

根据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通过使用相邻ig值之间的插值在 OEIS 公式中找到。

这意味着：

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

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