betaFeedback

WorksMathematics

Meta-Nested Recurrences

Abstract

We study recurrences in which a previous sequence value determines the number of iterations of an inner map. Campbell's example has an explicit power-of-three formula and inner orbits of eventual period at most two. Its normalized lower and upper limits are 2/52/5 and 3/43/4. For a variable-depth Conway recurrence CC, we prove the golden-ratio lower bound, its exact equality set, a Fibonacci upper cap, and the landing of the inner orbit at every Fibonacci index FkF_k with k≥6k\ge6. These proofs are elementary and start from twenty-four initial values. The plateau of CC to the left of FkF_k has width exactly ⌊(2k−9)/3⌋\lfloor(2k-9)/3\rfloor, and C(Fk+t)=Fk−1+tC(F_k+t)=F_{k-1}+t for 0≤t≤⌊(k−8)/6⌋0\le t\le\lfloor(k-8)/6\rfloor. A maximum principle turns a finite exact computation into the bound lim sup⁡C(n)/n<0.65446923\limsup C(n)/n<0.65446923. We characterize the convergence of C(n)/nC(n)/n to α=(5−1)/2α=(\sqrt5-1)/2 in terms of negative selected orbit jumps and of a limiting convex profile, and we derive entropy and variance budgets for the recursive splits. Along inverse rays of the map x↦C(x)x\mapsto C(x), the relative errors are absolutely summable and the growth is asymptotically Fibonacci. For Grytczuk's fixed-depth recurrence, we give a Pascal-word proof of convergence with the sharp error order n/log⁡nn/\sqrt{\log n} along interval maxima. The full variable-depth limit remains open.

Introduction

Nested recurrences are recurrences in which values at earlier indices occur inside the arguments of the sequence. The classical Hofstadter QQ-sequence is defined by

Q(n)=Q(n−Q(n−1))+Q(n−Q(n−2)),Q(1)=Q(2)=1,(1)Q(n) = Q(n - Q(n - 1)) + Q(n - Q(n - 2)), \qquad Q(1) = Q(2) = 1, \tag*{(1)}

and was introduced in Gödel, Escher, Bach [1]. The two recurrences below add a second layer, in which the number of applications of an inner map is itself a previous sequence value. We call this a meta-nested recurrence.

The surrounding literature contains several Conway-type and Hofstadter-type recurrences, including the variants studied by Mallows [2], Kubo and Vakil [3], Tanny [4], and Grytczuk [5]. Isgur and Rahman [6] study a fixed-depth family containing Grytczuk’s example, prove generalized Fibonacci anchor identities, and ask whether the normalized sequences converge. § 10 proves convergence for their depth-two case and gives its sharp error order. The slow-growth property and the Fibonacci anchors are known. Our proof includes an independent word derivation, so that the asymptotic argument is self-contained. Pascal-word methods and their connection with Conway’s sequence also appear in Janvresse, de la Rue and Velenik [7].

Fixed iteration counts occur in other families, including Cloitre’s arithmetical solutions [8]. In (2) and (3), the iteration depth instead depends on the preceding sequence value. Cloitre’s scaling approach [9] relates geometric anchor sequences to linear limits for slow nested recurrences. For the variable-depth sequence CC, we prove an equivalent convergence criterion in terms of selected inner-orbit steps.

The paper has two purposes. First, it records complete results for the Campbell example and the global golden structure of the Cloitre example. Second, it isolates the remaining asymptotic problem in a form that can be checked locally, namely a negative landing-jump condition in the interiors of the Fibonacci intervals. A separate dispersion criterion gives a conditional rate of convergence. The proofs of the golden structure and of the collars are elementary. A finite exact computation gives a numerical tail bound, and the maximum principle extends it to all later indices. Along inverse rays of the map x↦C(x)x \mapsto C(x), the normalized sequence converges unconditionally, while the full variable-depth limit remains open.

Definitions

Definition 1 (Campbell recurrence). Let b(1)=1b(1)=1. For n≥2n \ge2 put

Tn(x)=n−b(x),b(n)=Tnb(n−1)(n−1).(2)T_n(x)=n-b(x), \qquad b(n)=T_n^{b(n-1)}(n-1). \tag*{(2)}

where the exponent denotes exactly that many applications of TnT_n.

Definition 2 (Cloitre recurrence). Let C(1)=C(2)=1C(1)=C(2)=1. For n≥3n \ge3 put

Tn(x)=n−C(x),g=TnC(n−1)(n−1),C(n)=C(g)+C(n−g).(3)T_n(x)=n-C(x), \qquad g=T_n^{C(n-1)}(n-1), \qquad C(n)=C(g)+C(n-g). \tag*{(3)}

The prescribed depth is part of the definition. The split is not an arbitrary periodic point of the inner map.

We use F0=0F_0=0, F1=1F_1=1, Fj+1=Fj+Fj−1F_{j+1}=F_j+F_{j-1} and

α=5−12=1ϕ,G(n)=⌊α(n+1)⌋.\alpha=\frac{\sqrt{5}-1}{2}=\frac{1}{\phi}, \qquad G(n)=\lfloor\alpha(n+1)\rfloor.

Lemma 3 (Well-definedness and cyclic selection). The sequence CC is well-defined and satisfies

⌈n/2⌉≤C(n)≤n−1(n≥2),C(n)≤3n/4(n≥2),C(n)≥3n/5(n≥3).\lceil n/2\rceil\le C(n) \le n-1 \quad(n \ge2), \qquad C(n) \le3n/4 \quad(n \ge2), \qquad C(n) \ge3n/5 \quad(n \ge3).

For every n≥3n \ge3, g(n)g(n) lies on the cycle reached from n−1n-1.

The proof is in Appendix § 16.§ 1. In particular, cycle reduction computes the prescribed iterate exactly, without changing the starting point or the iteration depth.

Worked examples

The definition of CC is short, but each value is obtained through a small dynamical computation. We describe this computation for a few values of nn, each chosen to show one new feature.

Recall that C(1)=C(2)=1C(1) = C(2) = 1 and that, for n≥3n \ge3,

Tn(y)=n−C(y),hn=C(n−1),g(n)=Tnhn(n−1),C(n)=C(g(n))+C(n−g(n)).T_n(y) = n - C(y), \qquad h_n = C(n-1), \qquad g(n) = T_n^{h_n}(n-1), \qquad C(n) = C(g(n)) + C(n-g(n)).

Since 1≤C(y)≤y1 \le C(y) \le y, the map TnT_n sends {1,…,n−1}\{1,\ldots,n-1\} into itself and only uses values of CC that are already known. We write yr=Tnr(n−1)y_r = T_n^r(n-1) for the orbit of n−1n-1. This orbit is eventually periodic. Its entry rank τn\tau_n is the first rr for which yry_r lies on a cycle, and pnp_n denotes the length of that cycle. For every n≥3n \ge3 one has hn≥τnh_n \ge\tau_n (Lemma 3). The point g(n)g(n) therefore lies on the cycle and

g(n)=yτn+((hn−τn) mod pn).g(n) = y_{\tau_n+((h_n-\tau_n)\bmod p_n)}.

In practice one never iterates hnh_n times. Once the orbit has reached its cycle, only the residue of hn−τnh_n-\tau_n modulo pnp_n matters.

If the depth hnh_n is replaced by 1, then g(n)=n−C(n−1)g(n)=n-C(n-1) and the recurrence becomes C(n)=C(n−C(n−1))+C(C(n−1))C(n)=C(n-C(n-1))+C(C(n-1)). This is the Hofstadter–Conway recurrence a(n)=a(a(n−1))+a(n−a(n−1))a(n)=a(a(n-1))+a(n-a(n-1)) of A004001 with its two terms exchanged. The sequence CC follows the same map for C(n−1)C(n-1) steps instead of one. Table 1 gives the first values of both sequences together with the data of the computation.

The value n=4n=4. The first value where CC and aa differ is n=4n=4. Since C(3)=2C(3)=2 and C(2)=1C(2)=1, the orbit of 3 under T4(y)=4−C(y)T_4(y)=4-C(y) is 3,2,3,2,…3,2,3,2,\ldots, a cycle of length 2 from the start. Thus τ4=0\tau_4=0, p4=2p_4=2, and the even depth h4=C(3)=2h_4=C(3)=2 brings the orbit back to y2=3y_2=3. Hence g(4)=3g(4)=3 and C(4)=C(3)+C(1)=3C(4)=C(3)+C(1)=3. A single step stops at y1=2y_1=2 and gives C(2)+C(2)=2C(2)+C(2)=2, which is the value a(4)=2a(4)=2 of the Hofstadter–Conway sequence.

The value n=10n=10. Here h10=C(9)=6h_{10}=C(9)=6. Since C(9)=6C(9)=6, C(4)=3C(4)=3, C(7)=5C(7)=5 and C(5)=3C(5)=3, the orbit of 9 under T10T_{10} is

9↦4↦7↦5↦7↦5↦⋯9 \mapsto4 \mapsto7 \mapsto5 \mapsto7 \mapsto5 \mapsto\cdots
nn3456789101112131415161718192021
hnh_n1233455677889101112121313
τn\tau_n0001342235643556456
pnp_n1222112221122211211
g(n)g(n)2323455767898101011121213
C(n)C(n)23345567788910111212131313
a(n)a(n)22344456778888910111212

Table 1. Depth hn=C(n−1)h_n = C(n - 1), entry rank τn\tau_n, period pnp_n, selected point g(n)g(n) and value C(n)C(n) for 3≤n≤213 \le n \le21, compared with the Hofstadter–Conway sequence aa (A004001). Both sequences start with 1, 1.

After a transient of two steps it enters the 2-cycle {5,7}\{5, 7\}, so τ10=p10=2\tau_{10} = p_{10} = 2. As h10−τ10=4h_{10} - \tau_{10} = 4 is even, the iteration stops at y2=7y_2 = 7 and

C(10)=C(7)+C(3)=5+2=7.C(10) = C(7) + C(3) = 5 + 2 = 7.

An odd depth would have stopped at 5 and given C(5)+C(5)=6C(5) + C(5) = 6. When the cycle has two points, the parity of the depth decides which one is used.

Fibonacci arguments, n=13n = 13. For n=13n = 13 the depth is h13=C(12)=8h_{13} = C(12) = 8 and the orbit of 12 is

12↦5↦10↦6↦9↦7↦8↦8↦⋯ .12 \mapsto5 \mapsto10 \mapsto6 \mapsto9 \mapsto7 \mapsto8 \mapsto8 \mapsto\cdots.

It alternates on both sides of 8 and reaches the fixed point 8 at rank 6≤h136 \le h_{13}. Therefore g(13)=8g(13) = 8 and C(13)=C(8)+C(5)=5+3=8C(13) = C(8) + C(5) = 5 + 3 = 8. The same picture holds at every Fibonacci number Fk≥8F_k \ge8. The value C(Fk−1)=Fk−2C(F_{k-1}) = F_{k-2} makes Fk−1F_{k-1} a fixed point of TFkT_{F_k}, the orbit of Fk−1F_k - 1 ends there, and

C(Fk)=C(Fk−1)+C(Fk−2)=Fk−2+Fk−3=Fk−1.C(F_k) = C(F_{k-1}) + C(F_{k-2}) = F_{k-2} + F_{k-3} = F_{k-1}.

References

  1. [1]D. R. Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid, Basic Books, 1979.
  2. [2]C. L. Mallows, Conway’s challenge sequence, Amer. Math. Monthly 98 (1991), 5–20, https://doi.org/10.1080/00029890.1991.11995694.
  3. [3]T. Kubo and R. Vakil, On Conway’s recursive sequence, Discrete Math. 152 (1996), 225–252, https://doi.org/10.1016/0012-365X(94)00303-Z.
  4. [4]S. Tanny, A well-behaved cousin of the Hofstadter sequence, Discrete Math. 105 (1992), 227–239.DOI
  5. [5]J. Grytczuk, Another variation on Conway’s recursive sequence, Discrete Math. 282 (2004), 149–161, https://doi.org/10.1016/j.disc.2003.10.022.
  6. [6]A. Isgur and M. Rahman, On variants of Conway and Conolly’s meta-Fibonacci recursions, Electron. J. Combin. 18 (2011), no. 1, Paper P96, https://doi.org/10.37236/583.
  7. [7]É. Janvresse, T. de la Rue and Y. Velenik, Self-similar corrections to the ergodic theorem for the Pascal-adic transformation, Stoch. Dyn. 5 (2005), 1–25, https://doi.org/10.1142/S0219493705001250.
  8. [8]B. Cloitre. On a family of nested recurrences and their arithmetical solutions, preprint, 2025, https://arxiv.org/abs/2506.00093.
  9. [9]B. Cloitre, On the Mallows–Conway sequence, undated preprint, https://oeis.org/A005229/a005229.pdf, accessed 27 October 2026.
  10. [10]N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences: Hofstadter’s Q-sequence (A005185), Hofstadter’s G-sequence (A005206), the Hofstadter–Conway 10, 000 sequence (A000001), Grytczuk’s recurrence (A093878), and Peter Bala’s nested recurrence (A356988), https://oeis.org.

Paper details

vlnc:W_fnjpbpw8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude Opus 5.5, GPT-6 Astra, GPT-6.1 Sol, GPT-6 Pro, AI tools

View statement
Looking for related papers…
Contents