哥伦布的序列

扫码查看
本文介绍了哥伦布的序列的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

的哥伦布的自描述序列{G(N)}是自然数的唯一的非减序列使得n恰出现G(N)倍的序列中。 G(n)的用于第一少数n个值是

The Golomb's self-describing sequence {G(n)} is the only nondecreasing sequence of natural numbers such that n appears exactly G(n) times in the sequence. The values of G(n) for the first few n are

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。

Given that G(10^3) = 86, G(10^6) = 6137.Also given that ΣG(n^3) = 153506976 for 1 <= n < 10^3.

查找ΣG(N ^ 3),1&LT; = N&LT; 10 ^ 6。这是很容易code客场公式寻找numbers.But的顺序是有什么办法轨迹G之间(10 ^ 3)和数学关系G(10 ^ 6),这样,code到发现一笔高达10 ^ 6可以优化?

Find ΣG(n^3) for 1<= n< 10^6.It is easy to code away the formula for finding the sequence of numbers.But is there any way to track a mathematical relation between G(10^3) and G(10^6) so that the code to find sum upto 10^6 can be optimised ?

推荐答案

根据 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 次)。

If you generate the sequence for a while, you will notice that the size of the groups that repeat k times is k * G(k). For example, what is the size of the groups that repeat 2 times? 2 * G(2) = 4: 2 2 3 3. Those that repeat 3 times? 3 * G(3) = 6: 4 4 4 5 5 5 (6 repeats 4 times).

请注意,总和 IG(K)= SUM I * G(I),I&LT; = K 为您提供了重复1,2组的大小, ...... K 倍,所以它会告诉你在哪里,即重复的组 K 时代结束。

Notice that the sum ig(k) = sum i * G(i), i <= k gives you the size of groups that repeat 1, 2, ..., k times, So it tells you where the groups that repeat k times end.

这OEIS公式也是有帮助的:

This OEIS formula is also helpful:

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

使用这个你可以逃脱计算的来能够找到它的大量涌现。例如,让我们找到 G(10 ^ 6)

Using this you can get away with computing only a few values of G to be able to find it for large numbers. For example, let's find G(10^6):

首先,找到 K ,使得 K * G [K]&LT; 10 ^ 6≤=(K + 1)* G [K + 1] 。这将帮助跟你组政[10 ^ 6] 中,因此它的价值。

First, find k such that k*G[k] < 10^6 <= (k + 1)*G[k + 1]. This will help tell you the group G[10^6] is in, and therefore its value.

查找有这 K 将意味着 G(10 ^ 6)是一组大小的 K + 1

Finding this k will mean that G(10^6) is in a group of size k + 1.

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

I used this C++ program to find this value:

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 值之间的插值。

Now you need to pinpoint the exact group by using sg: you find the n in the OEIS formula by using interpolation between the adjacent ig values.

这意味着:

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

获取答案和价值观,你需要计算被作为一个练习,问你是否有前进的道路上的任何问题数量的精确解。

The exact solution for obtaining the answer and the number of values you need to compute are left as an exercise, ask if you have any problems along the way.

这篇关于哥伦布的序列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-20 12:58
查看更多