Selon OEIS, nous avons:
G(1) = 1
G(n+1) = 1 + G(n + 1 - G(G(n)))
Si vous générez la séquence pendant un certain temps, vous remarquerez que la taille des groupes qui se répètent k fois est k * G(k). Par exemple, quelle est la taille des groupes qui répètent deux fois? 2 * G(2) = 4: 2 2 3 3. Ceux qui répètent 3 fois? 3 * G(3) = 6: 4 4 4 5 5 5 (6 répète 4 fois).
Notez que la somme ig(k) = sum i * G(i), i <= k vous donne la taille des groupes qui se répètent 1, 2, ..., k fois, donc il vous indique où les groupes qui se répètent k fois fin.
Cette formule OEIS est également utile:
for G(1) + G(2)+ ... + G(n-1) < k <= G(1) + G(2) + ... + G(n) = sg(n)
we have G(k) = n
En utilisant cela, vous pouvez vous en sortir avec calcul seulement quelques valeurs de G pour être en mesure de le trouver pour un grand nombre. Par exemple, trouvons G(10^6):
D'abord, trouvez k de sorte que k*G[k] < 10^6 <= (k + 1)*G[k + 1]. Cela vous aidera à vous dire que le groupe G[10^6] est dedans, et donc sa valeur. Trouver k signifie que G(10^6) est dans un groupe de taille k + 1.
J'ai utilisé ce programme C++ pour trouver cette valeur:
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;
}
Ce qui donne:
k k * G[k] k + 1 (k + 1) * G[k + 1]
263 998827 264 1008859
Maintenant, vous devez identifier le groupe exact en utilisant sg: vous trouverez le n dans le OEIS formule en utilisant l'interpolation entre les valeurs ig adjacentes.
Cela signifie que:
G(10^6) = sg(k = 263) + (ig(k + 1 = 264) - ig(k = 263))/(k + 1 = 264)
La solution exacte pour obtenir la réponse et le nombre de valeurs dont vous avez besoin pour calculer sont laissés comme un exercice, demandez si vous avez des problèmes le long du chemin.
https://projecteuler.net/problem=341 –