1

ゴロンブの自己記述シーケンス{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と仮定します。また、1 <= n <10 ^ 3に対してΣG（n ^ 3）=153506976と仮定します。

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)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

次に、を使用して正確なグループを特定する必要があります。隣接する値間の補間を使用して、OEIS式でsgを見つけます。nig

この意味は：

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

答えを得るための正確な解決策と計算する必要のある値の数は演習として残されています。途中で問題がないか尋ねてください。

于 2012-10-08T18:58:56.537 に答える