Le cas continu de la suite Q de Hofstadter

par Ed Pegg
Article original

La fonction Q continue

Il y a un an, Stephen Wolfram a écrit un article au sujet des fonctions récursives imbriquées. Prenez le temps de réfléchir à sa chronique.
Out[]=
Il explore des centaines de fonctions différentes, donc il a conçu un code pour celles-ci. Celle qu’il appelle
F
4
12
est la suite Q de Hofstadter.
In[]:=
g[n_?NumericQ]:=g[n]=If[n<3,1,g[n-g[n-1]]+g[n-g[n-2]]];
Out[]=
Le cas des nombres entiers est réputé pour sa complexité.
In[]:=
Table[g[n],{n,2,55}]
Out[]=
{1,2,3,3,4,5,5,6,6,6,8,8,8,10,9,10,11,11,12,12,12,12,16,14,14,16,16,16,16,20,17,17,20,21,19,20,22,21,22,23,23,24,24,24,24,24,32,24,25,30,28,26,30,30}
Je me suis demandé ce qui se passerait si je le considérais comme une fonction continue. Il s’avère qu’il ressemble à la fonction entière.
Out[]=
Ainsi, au lieu de g[2]=1, j’ai essayé g[2]=2 à la place avec une nouvelle fonction.
In[]:=
f[n_?NumericQ]:=f[n]=If[n<3,n,f[n-f[n-1]]+f[n-f[n-2]]];
Les résultats semblent similaires, avec un décalage de 1.
In[]:=
Table[f[n],{n,1,54}]
Out[]=
{1,2,3,3,4,5,5,6,6,6,8,8,8,10,9,10,11,11,12,12,12,12,16,14,14,16,16,16,16,20,17,17,20,21,19,20,22,21,22,23,23,24,24,24,24,24,32,24,25,30,28,26,30,30}
Pour les 50 000 premiers nombres entiers,
f[n]=g[n+1]
.
In[]:=
Union[Table[f[n],{n,1,50000}]-Table[g[n],{n,2,50001}]]
Out[]=
{0}
La fonction présente une continuité et une complexité bien plus grande. J’appelle cette variante la fonction Q continue.
In[]:=
ListPlot[Table[{n,f[n]},{n,0,55,1/120}]]
Out[]=
Cela semble simple jusqu’à 25.
In[]:=
ListPlot[Table[{n,f[n]},{n,0,25,1/120}]]
Out[]=
Nous pouvons obtenir la fonction par morceaux.
In[]:=
ClearAll[f,n];​​f[n_?NumericQ]:=f[n]=If[n<3,n,f[n-f[n-1]]+f[n-f[n-2]]];​​h=1/120;​​(*detectintegerslopeflipsupto20*)​​leftD[k_]:=(f[k]-f[k-h])/h;​​rightD[k_]:=(f[k+h]-f[k])/h;​​changeInts=Select[Range[3,20],Round[leftD[#]]=!=Round[rightD[#]]&];​​x=Rationalize[Range[3,25,h],0];​​y=f/@x;​​sl=Rationalize[Differences[y]/h,0];​​xL=Most[x];xR=Rest[x];​​idxRuns=SplitBy[Range[Length[sl]],sl[[#]]&];​​toPiece[idx_List]:=Module[{a=xL[[First[idx]]],b=xR[[Last[idx]]],m=sl[[First[idx]]],v0=f[xL[[First[idx]]]],c},c=v0-ma;(*y=mn+c*){mn+c,a<=n<b}];​​piecesGE3=toPiece/@idxRuns;​​pw=Piecewise[Prepend[piecesGE3,{n,n<3}],Indeterminate];
In[]:=
pw
Out[]=
n
n<3
3
3≤n<4
-1+n
4≤n<6
5
6≤n<7
-2+n
7≤n<8
6
8≤n<10
-14+2n
10≤n<11
8
11≤n<13
-18+2n
13≤n<14
24-n
14≤n<15
-21+2n
15≤n<
31
2
10
31
2
≤n<
33
2
-23+2n
33
2
≤n<17
11
17≤n<18
-7+n
18≤n<19
12
19≤n<22
-76+4n
22≤n<23
154-6n
23≤n<
70
3
14
70
3
≤n<
1457
60
-
1373
6
+10n
1457
60
≤n<
583
24
-326+14n
583
24
≤n<
73
3
112-4n
73
3
≤n<
74
3
-36+2n
74
3
≤n<25
Indeterminate
True
In[]:=
Plot[pw,{n,0,25}]
Cela devient plus désordonné après cela :
Cela devient bien, bien pire après 49.
Voici du code pour étendre la fonction par morceaux d’une unité et pour fournir l’état au fur et à mesure que la fonction par morceaux se développe :

pw54

J’ai dû exécuter cette commande plusieurs fois car 56 ne fonctionne pas sur mon système.
Si j’ai bien fait ces calculs, voici le taux de croissance :
Je n’ai jamais réussi à obtenir 56. La dernière section est plus de deux fois plus grande que tout le reste réuni.
Je fournis les fonctions par morceaux pour 54 et 55, car mon vieil ordinateur ne peut pas dériver 55 pour la fonction par morceaux.
Pour cette raison, j'ai simplifié pw55 en points.
Voici la première partie complexe :
Voici la deuxième partie, jusqu’à 54.
La fonction continue atteint un niveau effrayant de complexité dans l’intervalle 52 à 55. Chaque point rouge est un point d’inflexion.
Le plus grand dénominateur dans la plage atteint 1713454620 :
Alors, que faire ensuite ? La fonction est continue jusqu’à 55, mais je ne suis pas sûr de ce qui se passe dans l’intervalle de 55 à 95.
Je ne suis pas sûr de savoir comment obtenir la fonction par morceaux ou une représentation ponctuelle jusqu’à 56, ou pour des valeurs plus élevées.
Quel est le taux de croissance du nombre de morceaux ?
Les autres fonctions issues des fonctions récursives imbriquées deviennent-elles considérablement plus complexes dans le cas continu ? Quels sont les monstres ?
Parfois, on peut résoudre des problèmes non résolus en les rendant plus complexes.
La fonction continue aide-t-elle pour la suite Q de Hofstadter ?
Je dois me demander à quel point cela devient complexe pour des valeurs plus élevées.

CITER CE NOTEBOOK

Le cas continu de la suite Q de Hofstadter​
par Ed Pegg​
Communauté Wolfram, CHOIX DE L’ÉQUIPE, 24 septembre 2025
​https://community.wolfram.com/groups/-/m/t/3550911