algorithm - 哥伦布序列

Question

哥伦布自描述序列 {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]是，因此它的值(value)。

找到这个 k将意味着 G(10^6)在一组大小 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 之间的插值值(value)观。

这意味着:

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

获取答案的确切解法和需要计算的值的个数留作练习，过程中有什么问题可以问。