# On a Generalization of Hofstadter’sQ-Sequence: A Family of Chaotic Generational Structures

Authors: Altug Alkan
Journal: Complexity
 (2018)

---

## Abstract

HofstadterQ-recurrence is defined by the nested recurrence Qn=Qn−Qn−1+Qn−Qn−2, and there are still many unanswered questions about certain solutions of it. In this paper, a generalization of Hofstadter’s Q-sequence is proposed and selected members of this generalization are investigated based on their chaotic generational structures and Pinn’s statistical technique. Solutions studied have also curious approximate patterns and considerably similar statistical properties with Hofstadter’s famous Q-sequence in terms of growth characteristics of their successive generations. In fact, the family of sequences that this paper introduces suggests the existence of conjectural global properties in order to classify unpredictable solutions to Q-recurrence and a generalization of it.


---

## Body

## 1. Introduction

Since the enigmatic concept of meta-Fibonacci has been introduced by Douglas Hofstadter with the invention of the originalQ-sequence (A005185 in OEIS), in the literature, there are many studies which focus on nested recurrence relations whose behaviors can alternate dramatically [1–5]. There are many examples of meta-Fibonacci sequences like Hofstadter-Conway $10000 sequence (A004001), Conolly sequence (A046699), Tanny sequence (A006949), Golomb’s sequence (A001462), Mallows’ sequence (A005229), etc. [6–10]. Some of meta-Fibonacci sequences are highly chaotic and unpredictable while some of them have completely predictable fashion such as quasipolynomial solutions to the Hofstadter Q-recurrence [11–13] and slow V-sequence (A063882) that is also 2-automatic [14]. Among the solutions which have an erratic nature, certain variants have underlying structures that contain conjecturally interesting approximate properties such as scaling, self-similarity, and period doubling [15, 16]. For these kinds of solutions of nested recurrences, known mathematical techniques for solving difference equations do not work because of the nature of nesting although there are alternative definitions for the generational structure of a chaotic meta-Fibonacci sequence [15–19]. The existence of universality classes for chaotic meta-Fibonacci sequences determined by common characteristics of their respective generational structures is a mysterious open question although there are a variety of attempts in order to search an affirmative answer for this question, partially [15–17]. Since the certain solutions to the Hofstadter Q-recurrence are investigated in this study, it would be nice to remember the scatterplots of Hofstadter’s original Q-sequence and the “Brother” sequence (A284644) that is defined by Qbn=Qbn−Qbn−1+Qbn−Qbn−2 and initial values Qb1=Qb2=2 and Qb3=1 (see Figure 1). Although there are many solutions to the Hofstadter Q-recurrence with different initial conditions [9, 11–13, 17, 20], these two solutions and their connection based on their generational structures provide a variety of interesting experimental results [17].Figure 1
Scatterplots of Hofstadter’sQ-sequence and Qbn.This paper is structured as follows. In Section2, Hofstadter’s Q-sequence is generalized according to the initial condition formulation and an intriguing sequence family is introduced. Then, in Section 3.1 and Section 3.2, selected members of this curious sequence family are studied based on their generational structures with the statistical perspective. Finally, some concluding remarks are offered in Section 4.


## 2. A Generalization of Hofstadter’sQ-Sequence according to Initial Conditions

Hofstadter’sQ-sequence is a very intriguing solution to the Q-recurrence, and it is believed that the most notable meta-Fibonacci sequence is Hofstadter’s Q-sequence [11]. Indeed, many famous mathematicians such as Erdős, Guy, and Sloane found it really very interesting [21, 22]. At this point, it is natural to ask, “Can a generalization of solutions to the Q-recurrence be based on the initial conditions for variants that behave in a similar fashion with a Q-sequence?” If the answer is yes, there can be a collection of curious chaotic patterns and generational structures hidden in genes of the Q-recurrence. Solutions with three initial conditions are studied before [17]. In order to go further, computer experiments can be made with four and five initial conditions but empirical results suggest that there is no sign of any sequence family with generational common characteristics except Q-sequence and “Brother” sequence (A284644) although there are some more chaotic solutions such as A278056 [9, 11]. So experiments suggest that computation of all living permutations of initial conditions is not very fruitful in order to discover a solution family that has members which behave very similar with the original Q-sequence. Also, recently, the Hofstadter Q-recurrence and a generalization of it are studied with initial conditions 1 through N and detailed analysis showed that living solutions have notably different properties from the Q-sequence with the increasing values of N [11]. At this point, it would be nice to remember if limn→∞Qn/n exists, it must be equal to 1/2 [13]. From this fact, initial conditions which are n/2 may be meaningful for the Hofstadter Q-recurrence. Additionally, this approach inspired by reasonable heuristic can be generalized with the initial condition formulation as below.Definition 1.
LetQd,ln be defined by the recurrence Qd,ln=∑i=1lQd,ln−Qd,ln−i for n>d∗l, l≥2, and d≥1, with the initial conditions Qd,ln=n∗l−1/l for n≤d∗l.By definition,Q1,2 is the original Q-sequence and Q3,2 is essentially the same with Q1,2. Q2,2 is extremely wild sequence that there are no signs of any underlying structure (see Figure 2).Figure 2
Scatterplot ofQ2,2n.However, ford≥4, many curious chaotic patterns fascinatingly start to appear for Sd,2n=Qd,2n−n/2 (see Figure 3). In the next section, certain members of this family are investigated in order to search the signs of a similar inheritance with the original Q-sequence although Q2,2 exhibits quite different experimental characteristics, at least in the range of this study.Figure 3
Scatterplots ofSd,2n for 4≤d≤12, respectively.In this study, solutions toQd,2n and Qd,3n recurrences will be studied with certain examples while Qd,ln continues to provide intriguing generational structures with an increasing level of complexity for l≥4.


## 3. Analysis of Certain Members ofQd,ln Family

### 3.1. Selected Solutions toQd,2n

Approximate self-similar block structures of certain members oftheQd,2n family can be studied thanks to auxiliary sequences similar with different works which give definitions of generations [15–18]. In here, the main purpose is to model and compute the rescaling of amplitudes for self-similar successive block structures of Sd,2n for the selected values of d which are in the range of this study, since this computation will give a chance to search a conjectural global property for certain solutions to the Hofstadter Q-recurrence. Certain auxiliary sequences can be used in order to compute statistical quantities which this paper focuses on. Experiments that use alternative definitions for the determination of generational boundaries are also carried out precisely. Since the results are mainly similar in terms of the values of Table 1, only one method’s table is reported in here. Corresponding method’s definitions follow as below. See Figure 4 for some examples of partitions.Table 1
Values ofαk,S4,2n, αk,S7,2n, and αk,S10,2n for 10≤k≤25.
k
αk,S4,2n
αk,S7,2n
αk,S10,2n
10
0.847
0.798
0.837
11
0.828
0.895
0.776
12
0.853
0.886
0.803
13
0.764
0.824
0.883
14
0.869
0.861
0.877
15
0.858
0.875
0.880
16
0.862
0.870
0.863
17
0.875
0.890
0.877
18
0.869
0.880
0.886
19
0.878
0.884
0.882
20
0.884
0.883
0.882
21
0.882
0.886
0.884
22
0.883
0.885
0.885
23
0.885
0.884
0.886
24
0.887
0.886
0.886
25
0.888
0.886
0.886Figure 4
Illustrations ofPd,217 and Pd,218 on scatterplots of Sd,2n where d∈4,7,10, respectively.Definition 2.
LetWd,2n be the least m such that the minimum of father m−Qd,2m−2 and mother m−Qd,2m−1 spots is equal or greater than n.Definition 3.
LetPd,2n=Wd,2Pd,2n−1 where d∈4,7,10 for n>1, with Pd,21=1.
See Tables2–4 for the corresponding values of Pd,2n.Table 2
The values ofP4,2n sequence for n≤25.
m
1
2
3
4
5
P4,2m+0
1
3
5
9
17
P4,2m+5
33
65
129
257
513
P4,2m+10
1025
2049
4088
8163
16227
P4,2m+15
32206
63943
127182
253527
504715
P4,2m+20
1001529
1990206
3956008
7852309
15566939Table 3
The values ofP7,2n sequence for n≤25.
m
1
2
3
4
5
P7,2m+0
1
3
5
9
18
P7,2m+5
37
76
155
314
630
P7,2m+10
1264
2538
5076
10155
20269
P7,2m+15
40309
80178
158920
315670
626261
P7,2m+20
1242680
2461343
4881527
9689364
19208568Table 4
The values ofP10,2n sequence for n≤25.
m
1
2
3
4
5
P10,2m+0
1
3
5
9
17
P10,2m+5
34
69
140
283
569
P10,2m+10
1141
2285
4573
9147
18292
P10,2m+15
36542
72974
145867
291183
581442
P10,2m+20
1160383
2313867
4614469
9202451
18337568The given sequenceSd,2n=Qd,2n−n/2,Sd,2nk denotes the average value of Sd,2n over the kth generation boundaries that are determined by Pd,2n for corresponding Qd,2n and define αk,Sd,2n as below. See Table 1 and Figure 5 in order to observe the considerable similarities between α values with the increasing number of generations. These results are very close to the values that are reported before [15–17]. In other words, the initial condition pattern that this study focuses on provides significant behavioral similarities with the original Q-sequence in terms of growth characteristics of successive generations. Additionally, other solutions for 4≤d≤12 are checked thanks to certain auxiliary sequences and careful examination of their data. Results observed are mainly similar to the values of Table 1.
(1)MkSd,2n2=Sd,2n2k−Sd,2nk2,αk,Sd,2n=log2MkSd,2nMk−1Sd,2n.Figure 5
Blue:αk,S4,2n. Red: αk,S7,2n. Green: αk,S10,2n.


### 3.2. Selected Solutions toQd,3n

In this section, certain members ofQd,3n are analysed thanks to properties of their generational structures. It is easy to show that Q1,3n and Q2,3n die immediately since Q1,34=6 and Q2,366=73. See Figure 6 for Q3,3n that is highly chaotic sequence although there appear to be some weak signs of order in it. Then, more orderly generational structures evolve in terms of the determination of main blocks (see Figure 7 for curious examples where Sd,3n=Qd,3n−2∗n/3). In that case, in order to detect the limits of approximate self-similar block structures, spot-based generation concept can be used for d∈4,7,10 based on spot n−Qd,3n−1 [18].Definition 4.
Letgd,3n be the least value of t such that Mp,d,3t is equal to n where d∈4,7,10 and Mp,d,3n=Mp,d,3n−Qd,3n−1+1 with initial conditions Mp,d,3n=1 for n≤3∗d.Figure 6
Scatterplot ofQ3,3n.Figure 7
Scatterplots ofSd,3n where d∈4,7,10, respectively.See Tables5–7 for the corresponding values of gd,3n and Figure 8 for some illustrations of generational boundaries.Table 5
The values ofg4,3n sequence for n≤15.
m
1
2
3
4
5
g4,3m+0
1
13
39
114
327
g4,3m+5
970
2911
8650
25875
77058
g4,3m+10
228424
678683
2020707
6016683
17966896Table 6
The values ofg7,3n sequence for n≤15.
m
1
2
3
4
5
g7,3m+0
1
22
66
195
570
g7,3m+5
1699
5102
15224
45510
136182
g7,3m+10
406324
1209535
3611564
10797842
32259345Table 7
The values ofg10,3n sequence for n≤15.
m
1
2
3
4
5
g10,3m+0
1
31
93
276
813
g10,3m+5
2428
7289
21802
65263
195493
g10,3m+10
584332
1743893
5216310
15587996
46668176Figure 8
Illustrations ofgd,39 and gd,310 on scatterplots of Sd,3n where d∈4,7,10, respectively.Similar with the previous section, for a given sequenceSd,3n=Qd,3n−2∗n/3, Sd,3nk denotes the average value of Sd,3n over the kth generation boundaries that are determined by gd,3n for corresponding Qd,3n and define αk,Sd,3n as below. Also, similarly, see Table 8 and Figure 9 in order to observe the considerable similarities between α values that are different from the values which are reported in the previous section since the recurrence is Qn=Qn−Qn−1+Qn−Qn−2+Qn−Qn−3 in that case.
(2)MkSd,3n2=Sd,3n2k−Sd,3nk2,αk,Sd,3n=log3MkSd,3nMk−1Sd,3n.Table 8
Values ofαk,S4,3n, αk,S7,3n, and αk,S10,3n for 5≤k≤15.
k
αk,S4,3n
αk,S7,3n
αk,S10,3n
5
0.837
0.838
0.838
6
0.937
0.925
0.926
7
0.928
0.894
0.898
8
0.936
0.927
0.933
9
0.937
0.944
0.942
10
0.954
0.947
0.949
11
0.951
0.952
0.949
12
0.948
0.951
0.949
13
0.952
0.952
0.953
14
0.952
0.954
0.953
15
0.954
0.954
0.954Figure 9
Blue:αk,S4,3n. Red: αk,S7,3n. Green: αk,S10,3n.


## 3.1. Selected Solutions toQd,2n

Approximate self-similar block structures of certain members oftheQd,2n family can be studied thanks to auxiliary sequences similar with different works which give definitions of generations [15–18]. In here, the main purpose is to model and compute the rescaling of amplitudes for self-similar successive block structures of Sd,2n for the selected values of d which are in the range of this study, since this computation will give a chance to search a conjectural global property for certain solutions to the Hofstadter Q-recurrence. Certain auxiliary sequences can be used in order to compute statistical quantities which this paper focuses on. Experiments that use alternative definitions for the determination of generational boundaries are also carried out precisely. Since the results are mainly similar in terms of the values of Table 1, only one method’s table is reported in here. Corresponding method’s definitions follow as below. See Figure 4 for some examples of partitions.Table 1
Values ofαk,S4,2n, αk,S7,2n, and αk,S10,2n for 10≤k≤25.
k
αk,S4,2n
αk,S7,2n
αk,S10,2n
10
0.847
0.798
0.837
11
0.828
0.895
0.776
12
0.853
0.886
0.803
13
0.764
0.824
0.883
14
0.869
0.861
0.877
15
0.858
0.875
0.880
16
0.862
0.870
0.863
17
0.875
0.890
0.877
18
0.869
0.880
0.886
19
0.878
0.884
0.882
20
0.884
0.883
0.882
21
0.882
0.886
0.884
22
0.883
0.885
0.885
23
0.885
0.884
0.886
24
0.887
0.886
0.886
25
0.888
0.886
0.886Figure 4
Illustrations ofPd,217 and Pd,218 on scatterplots of Sd,2n where d∈4,7,10, respectively.Definition 2.
LetWd,2n be the least m such that the minimum of father m−Qd,2m−2 and mother m−Qd,2m−1 spots is equal or greater than n.Definition 3.
LetPd,2n=Wd,2Pd,2n−1 where d∈4,7,10 for n>1, with Pd,21=1.
See Tables2–4 for the corresponding values of Pd,2n.Table 2
The values ofP4,2n sequence for n≤25.
m
1
2
3
4
5
P4,2m+0
1
3
5
9
17
P4,2m+5
33
65
129
257
513
P4,2m+10
1025
2049
4088
8163
16227
P4,2m+15
32206
63943
127182
253527
504715
P4,2m+20
1001529
1990206
3956008
7852309
15566939Table 3
The values ofP7,2n sequence for n≤25.
m
1
2
3
4
5
P7,2m+0
1
3
5
9
18
P7,2m+5
37
76
155
314
630
P7,2m+10
1264
2538
5076
10155
20269
P7,2m+15
40309
80178
158920
315670
626261
P7,2m+20
1242680
2461343
4881527
9689364
19208568Table 4
The values ofP10,2n sequence for n≤25.
m
1
2
3
4
5
P10,2m+0
1
3
5
9
17
P10,2m+5
34
69
140
283
569
P10,2m+10
1141
2285
4573
9147
18292
P10,2m+15
36542
72974
145867
291183
581442
P10,2m+20
1160383
2313867
4614469
9202451
18337568The given sequenceSd,2n=Qd,2n−n/2,Sd,2nk denotes the average value of Sd,2n over the kth generation boundaries that are determined by Pd,2n for corresponding Qd,2n and define αk,Sd,2n as below. See Table 1 and Figure 5 in order to observe the considerable similarities between α values with the increasing number of generations. These results are very close to the values that are reported before [15–17]. In other words, the initial condition pattern that this study focuses on provides significant behavioral similarities with the original Q-sequence in terms of growth characteristics of successive generations. Additionally, other solutions for 4≤d≤12 are checked thanks to certain auxiliary sequences and careful examination of their data. Results observed are mainly similar to the values of Table 1.
(1)MkSd,2n2=Sd,2n2k−Sd,2nk2,αk,Sd,2n=log2MkSd,2nMk−1Sd,2n.Figure 5
Blue:αk,S4,2n. Red: αk,S7,2n. Green: αk,S10,2n.


## 3.2. Selected Solutions toQd,3n

In this section, certain members ofQd,3n are analysed thanks to properties of their generational structures. It is easy to show that Q1,3n and Q2,3n die immediately since Q1,34=6 and Q2,366=73. See Figure 6 for Q3,3n that is highly chaotic sequence although there appear to be some weak signs of order in it. Then, more orderly generational structures evolve in terms of the determination of main blocks (see Figure 7 for curious examples where Sd,3n=Qd,3n−2∗n/3). In that case, in order to detect the limits of approximate self-similar block structures, spot-based generation concept can be used for d∈4,7,10 based on spot n−Qd,3n−1 [18].Definition 4.
Letgd,3n be the least value of t such that Mp,d,3t is equal to n where d∈4,7,10 and Mp,d,3n=Mp,d,3n−Qd,3n−1+1 with initial conditions Mp,d,3n=1 for n≤3∗d.Figure 6
Scatterplot ofQ3,3n.Figure 7
Scatterplots ofSd,3n where d∈4,7,10, respectively.See Tables5–7 for the corresponding values of gd,3n and Figure 8 for some illustrations of generational boundaries.Table 5
The values ofg4,3n sequence for n≤15.
m
1
2
3
4
5
g4,3m+0
1
13
39
114
327
g4,3m+5
970
2911
8650
25875
77058
g4,3m+10
228424
678683
2020707
6016683
17966896Table 6
The values ofg7,3n sequence for n≤15.
m
1
2
3
4
5
g7,3m+0
1
22
66
195
570
g7,3m+5
1699
5102
15224
45510
136182
g7,3m+10
406324
1209535
3611564
10797842
32259345Table 7
The values ofg10,3n sequence for n≤15.
m
1
2
3
4
5
g10,3m+0
1
31
93
276
813
g10,3m+5
2428
7289
21802
65263
195493
g10,3m+10
584332
1743893
5216310
15587996
46668176Figure 8
Illustrations ofgd,39 and gd,310 on scatterplots of Sd,3n where d∈4,7,10, respectively.Similar with the previous section, for a given sequenceSd,3n=Qd,3n−2∗n/3, Sd,3nk denotes the average value of Sd,3n over the kth generation boundaries that are determined by gd,3n for corresponding Qd,3n and define αk,Sd,3n as below. Also, similarly, see Table 8 and Figure 9 in order to observe the considerable similarities between α values that are different from the values which are reported in the previous section since the recurrence is Qn=Qn−Qn−1+Qn−Qn−2+Qn−Qn−3 in that case.
(2)MkSd,3n2=Sd,3n2k−Sd,3nk2,αk,Sd,3n=log3MkSd,3nMk−1Sd,3n.Table 8
Values ofαk,S4,3n, αk,S7,3n, and αk,S10,3n for 5≤k≤15.
k
αk,S4,3n
αk,S7,3n
αk,S10,3n
5
0.837
0.838
0.838
6
0.937
0.925
0.926
7
0.928
0.894
0.898
8
0.936
0.927
0.933
9
0.937
0.944
0.942
10
0.954
0.947
0.949
11
0.951
0.952
0.949
12
0.948
0.951
0.949
13
0.952
0.952
0.953
14
0.952
0.954
0.953
15
0.954
0.954
0.954Figure 9
Blue:αk,S4,3n. Red: αk,S7,3n. Green: αk,S10,3n.


## 4. Conclusion

In the literature, there are many studies that are primarily concerned with finding initial conditions to corresponding meta-Fibonacci recurrences where the solutions have a provable universal property such as having an ordinary generating function and being slow [11, 12, 20]. On the other hand, properties of Hofstadter’s Q-sequence depend on experimental studies because of its complicated nature that is extremely resistant to known mathematical proof techniques [15–17, 19]. In this study, a variety of evidences are provided in order to claim the existence of a family that certain members have considerably similar conjectural properties with famous Q-sequence. A generalization of Q-sequence according to the initial condition patterns which are determined by asymptotic properties of recurrences is introduced, and meaningful statistical results are provided in terms of the classification of chaotic solutions to recurrences that this study focuses on.



---

*Source: 8517125-2018-06-25.xml*