On a conjecture about generalized Q-recurrence

1 Introduction

Since substantial experimental studies have been done by Hofstadter and Huber on certain meta-Fibonacci sequences which are inspired by original Q-sequence that is defined by Q(n) = Q(n−Q(n−1))+Q(n−Q(n− 2)) with initial conditions Q(1) = Q(2) = 1 [1], there is a wide variety of significant contributions which are mainly focused on nested recurrence relations in theoretical and empirical literature [2, 3, 4, 5, 6, 7, 8, 9, 10]. While empirical works try to find order signs and some patterns in chaotic meta-Fibonacci sequences, theoretical literature mainly focuses on properties of slow and quasi-periodic solutions for various types of nested recursions and some curious concepts such as binary trees and undecidability [11, 12, 13,]. Despite the complexity of many inquiries which these contributions have, an essential and natural question about a meta-fibonacci sequence is whether it is defined for all indices [14, 15,]. It is well-known that properties of solutions to meta-Fibonacci recursions can differ extremely and the answer of this question strongly depends on the selection of initial conditions in general [16]. While modified nested recurrences can exhibit different properties of solutions with the same initial conditions, a selected recurrence can also show dissimilar behaviours under certain initial condition sets [17, 18]. For example, let us define Q(1) = Q(2) = Q(3) = 1, Q(4) = 4, Q(5) = 3, and for n ≥ 5, Q(n) = Q(n − Q(n − 1)) + Q(n − Q(n − 2)) + Q(n − Q(n − 3)), that is A296413 in OEIS [19]. This sequence is highly chaotic and finite since Q(509871) = 519293. On the other hand, the same recurrence can have slow solution with appropriate initial conditions [20] while it can be naturally quasi-periodic for certain set of initial conditions such as A296518 and A296786 in OEIS [21]. Also, intriguing generational structures which are analysed by spot-based generation concept appear with a family of initial conditions for Q(n) = Q(n − Q(n − 1)) + Q(n − Q(n − 2)) + Q(n − Q(n − 3)) [21]. This behavioral diversity observed in three-term Hofstadter Q-recurrence can be interpreted as a sign of difficulty of problems about certain types of nested recurrences, especially for Hofstadter-like recurrences. On the other hand, the coexistence of order and chaos in some unpredictable meta-Fibonacci sequences can be recreated experimentally thanks to inital condition patterns in terms of considerable behavioral similarities. At this point, it would be beneficial to remember the definition of a generalization of Hofstadter’s Q-sequence [21].

1.1 A motivational new generalization to beginning

In this section, we observe the potential of initial condition patterns in order to construct infinitely many different solutions for a selected nested recurrence. Although sequences that we focus on in next sections are not slow, this part suggests that infinitely many different solutions that have strong behavioral similarities can be really constructed with the formulation of initial conditions, at least for certain recurrences. It is well-known that Newman generalization on Hofstadter-Conway $10000 sequence (A004001 in OEIS) provides a variety of interesting results that Fibonacci-type behaviours appear in their generational analysis [23, 24, 25,]. However, we will generalize Hofstadter-Conway $10000 sequence thanks to its asymptotic property which is proved by Conway [24]. In order to eliminate duplicate sequences, we define them as below. Note that a₁(n) is Conway’s original sequence.

Definition 1.2

Let a_i(n) = a_i(a_i(n −1))+a_i(n −a_i(n −1)) for n > 4. i, with the initial conditionsai(n)=⌈n2⌉for 1 ≤ n ≤ 4 · i.

Proposition 1.3

ai(n+1)−ai(n)∈{0,1}for all n, i ≥ 1 and a_i(n) hits every positive integer for all i ≥ 1.

Proposition 1.4

ai(n)≥n2forall i≥1.

Both propositions are easy to prove by induction since initial conditions of the form⌈n2⌉provide necessary and sufficient basis to this aim. Based on these basic properties, see Figure 1 in order to observe certain members ofai(n)−n2.While it provides a fractal-like collection of fractal-like sequences, it clearly suggests that this is a new and natural generalization which perfectly guarantees the existence of infinitely many different solutions and our approach can be potentially applied for some other recurrences. In next sections we search for the signs of some similar behaviours in terms of existence of solutions for Q _d,ℓ(n) with the stability of noise levels, although their chaotic nature prevents the perfection which a_i(n) exhibits.

Fig. 1

a2t(n)−n2for212≤n≤213and 0 ≤ t ≤ 7, respectively.

2 On termination of Q_d,ℓ(n) forℓ≥ 3

In this section, an existence of breaking point for termination of Q _d,ℓ(n) is investigated. It is a relatively easy fact that Q_2,3(n) is a finite sequence due to Q_2,3(66) = 73 [21]. On the other hand, our following analysis confirms that the termination of Q_2,3(n) is an exceptional behaviour for Q_d,ℓ(n), at least, in the range of experiments that the next section focuses on.

Sinced+2ℓ=d+3ℓfor l ≥ 7 andd=ℓ⋅(ℓ−1)−1+(−1)ℓ2,from Proposition 2.2,

Thanks to Equation 3, Q_d,ℓ(d · ℓ + 3) can be expressed as follows for l ≥ 7,

In here if ℓ is odd, thend=ℓ⋅(ℓ−1)2−1and Q_d,ℓ(d · ℓ + 3) can be expressed as follows,

And if ℓ is even, thend=ℓ⋅(ℓ−1)2and similar way can be used,

These two cases can be combined into one equation that isQd,l(d⋅ℓ+3)=d⋅(ℓ−1)+7+(−1)ℓ+12

Since each computed term Q_d,ℓ(d · ℓ + k) is also determinative for Q_d,ℓ(d · ℓ + k + 1) for all k ≥ 1 by definition of our nested recurrences, the properties of further terms can also be shown with similar propositions. Table 1 contains some related patterns which guarantee the successive computations of recursions without termination in these short intervals as below. See also decreasing order of corresponding bursts in Figure 2 for an example Q_209,21(n).

Fig. 2

Graph of Q_209,21(n)−2021⋅nfor 4000 ≤ n ≤ 10000.

3 Experiments for Strange Members of Q_d,ℓ(n)

Although previous section is really helpful in order to understand the certain facts about possible termination cases of Q_d,ℓ(n) sequences for increasing values of ℓ and its relation with d, it is practically impossible to continue to prove these similar successive propositions forever. At this point, power of computer experiments may be meaningful in order to see the big picture about behaviours of these chaotic sequences in relatively long run and indeed this is the case. Our first purpose is the investigation of chaotic behaviours of these sequences for increasing values ofd≥ℓ⋅(ℓ−1)−1+(−1)ℓ2for a selected ℓ. To this aim, let〈Sd,ℓ(n)〉Ndenotes the average value of S_d,ℓ(n) for d . ℓ + 1 ≤ n ≤ N + d . ℓ where S_d,ℓ(n) is defined by Equation 4 and σ_ℓ(d) is defined by Equation 5. In our experiments, we focus on N = 10⁶, 2 ≤ ℓ ≤ 19 although several other values are also checked. Figure 3 particularly shows fascinating order signs of σ₃(d) for such a chaotic

Fig. 3

Graph of σ₃(d) for 20 ≤ d ≤ 250.

sequence family Q_d,3(n). While σ₃(d) has a very characteristic distributional behaviour based on d mod 3, meaningful observations also can be made in Figure 5 and Figure 6 that suggest behaviour of these sequences has considerable similarities in terms of fluctuations of σ_ℓ(d).

Fig. 5

Logarithmic plots of σ_ℓ(d) forℓ⋅(ℓ−1)−1+(−1)ℓ2+0|ℓ−3|≤ d ≤ 250 and N = 10⁶ where 2 ≤ ℓ ≤ 10, respectively.

Fig. 6

Logarithmic plots of σ_ℓ(d) forℓ⋅(ℓ−1)−1+(−1)ℓ2≤ d ≤ 300 and N = 10⁶ where 11 ≤ ℓ ≤ 19, respectively.

This is a strong evidence that there are different branches in scatterplots which are dominated by values of d in a particular residue class for such chaotic sequences. Indeed, other graphs have also some similar patterns which are more irregular and weaker than patterns of σ₃(d) in terms of their ℓ values. While perfect explanation of such distributions is very hard to formulate due to chaotic nature of them, the main common property of them is that they do not tend to increase in terms of general trends. More precisely, trend line slopes for selected intervals are negative for all of them in the range of our experiments. Additionally, there are some sharp transitions between some levels of σ_ℓ(d). In order to observe the meaning of a characteristic decrease example in σ₄(d) plot, see Figure 4 that displays line graphs of S_59,4(n) and S_60,4(n) which small increase of d notably diminishes the amplitude of generational oscillations. Such a graphical observation is named as Yosemite Graph similarly in another curious work related to integer sequences [26]. Although this behaviour is not always the case for all consecutive values of d, empirical evidences suggest that more stability is a general tendency of Q_d,ℓ(n) for ascending d.

Fig. 4

Line graphs of S_59,4(n) and S_60,4(n) for n ≤ 10⁴.

Our second purpose is understanding the behaviour of Q_d,ℓ(n) whered=ℓ⋅(ℓ−1)−1+(−1)ℓ2.Section 2 clearly shows that there is a breaking point for finiteness of Q_d,ℓ(n). Computer search also confirms this stage of experimentation since Q_d,ℓ(n) is successfully computed up to 5 · 10⁷ without any termination case for all 4 ≤ ℓ ≤ 100 whered=ℓ⋅(ℓ−1)−1+(−1)ℓ2.

4 Discussion and Result

More detailed analysis on these strange recursions can be done thanks to investigation of generational structures of Q_d,ℓ(n) but this could be extremely diffucult for all chaotic sequences in the range of our experiments since the confirmation of generational boundaries necessitates very careful examination of block structures of each generation for any known generational method [21, 22, 23,]. On the other hand, Section 2 and Section 3 both fairly conclude that increasing values ofd≥ℓ⋅(ℓ−1)−1+(−1)ℓ2tend to stabilize σ_ℓ(d) levels which are exhibited by oscillations of Q_d,ℓ(n) around its conjectural slope for sufficiently large fixed N. Additionally, these sections suggest that Q_d,ℓ(n) tends to be well defined whered=ℓ⋅(ℓ−1)−1+(−1)ℓ2for ℓ ≥ 4. So following conjectures are proposed based on reasonable heuristic, analysis and these empirical evidences that previous sections provide.

5 Conclusion

This paper suggests that a generalization Q_d,ℓ(n) tends to provide coexistence of chaos and order that are recreated by increasing values of d for an arbitrary ℓ. The target of our conjecture is finding a reasonable answer for the most fundamental question about these nested recurrences which this study focuses on. Understanding the behaviors of generalizations of meta-Fibonacci sequences may be really significant and helpful in order to discover curious properties of these kinds of nonlinear recurrences and there can pave the way in this direction due to wealth inheritance of these enigmatic sequences. For example, a new generalization can also be proposed for slow Hofstadter-Conway $10000 sequence which has curious fractal-like structure [27] as mentioned in A296816. So nature of generalizations of meta-Fibonaci sequences and probable unexpected interactions [22] between curious members of these generalizations contain new enigmatic inquiries for possible future works.