WorksMathematics
Perturbing the Conway sequence
Abstract
We study the alternating perturbation of Conway's nested recurrence, for , with . We prove that the sequence is well defined and satisfies , where is the real root of .
Introduction
We consider the sequence (OEIS A399773 [5]) defined by
Without the alternating term, Conway’s recurrence has limiting ratio ; see Mallows [1] and Kubo–Vakil [2]. The alternating perturbation changes this limiting ratio. Let be the real root of , so that the candidate slope is . Throughout, denotes the natural logarithm.
Theorem 1. The recurrence (1) is well defined for every positive integer, and
In particular, .
The motivation was Mantovanelli’s addition of to Hofstadter’s -recurrence [3]. In [4], we proved that the resulting sequence is well defined and satisfies , with this error order optimal. That proof uses binary words, Dyck paths, and plane forests. Here the argument instead combines exact values on a geometric subsequence with a quadratic estimate on the recursion tree.
Motivation and proof outline
The first terms are
Although is not monotone, the graph of reveals a regular pattern of arches on a logarithmic horizontal scale (Figure 1). Examining selected local maxima of led to two empirical families of indices,
Figure 1. for , with a logarithmic horizontal axis. The markers show the computed values at the reference indices . The exact formulas proved in § 4 imply .
Starting at 488, they interleave as , with consecutive ratios appearing to approach . Since , it is natural to test the residual .
In the computed list, it alternated between and , beginning at . We therefore define the reference indices by
We shall prove exact formulas for and in § 4. In particular, , so the marked values of approach at order .
A comparison with the shifted sequence
also helped identify the local structure. This sequence satisfies [6]. Jeffrey Shallit supplied a conjectural automaton for in Narayana numeration [7]. Its repeating patterns included the reference families already observed and suggested examining short windows around them. The windows led to the two tables used below; their values are established directly from (1).
The proof has two steps. First, the odd and even positions of give two nondecreasing sequences whose increments are 0 or 1. Around each , a short table of their values, translated vertically by , repeats according to the parity of . The recurrence reads neighboring entries as well as the centers, so these tables contain just the extra information needed for induction. The main difficulty is locating the left endpoint of the next window. At the first index where reaches a value , the preceding value is necessarily ; this observation determines the endpoint from earlier tables.
The second step controls all indices between the reference points. Their spacing is comparable to their size, so monotonicity alone would leave a nonvanishing relative error. Expanding the recurrence on a binary tree gives weighted averages, with weights corresponding to descents of three and one reference levels. The key comparison is between the paths 10 and 01: their weights agree, but they end at different functions. This relates an error in a sequence value to changes of the arguments in the tree. Summing squared changes over levels gives an bound. The exact tables permit to be proportional to , yielding (2).
Sections 2–4 establish the parity properties, the first-passage lemma, and the local tables. Section 5 gives the tree estimate and completes the proof. The finite initial calculation is recorded in Appendix A.
Splitting the sequence
The perturbations at and have the same sign, so they cancel when the corresponding recurrences are subtracted. This gives monotonicity separately on the odd and even positions.
Lemma 2. The recurrence (1) is well defined. Its values are positive and odd, and
Both parity subsequences are unbounded, and each takes every positive odd integer value.
Proof. The values start the induction for well-definedness. Let , assume the earlier values are positive and odd with the stated bound, and put . Then , so both and are earlier positive indices. The recurrence gives a positive odd value. If , both arguments are at least 2, and
If , then and .
For the parity increments, use a separate induction on . The cases give and . For , put and . The preceding step gives , while subtraction yields
If , this is ; if , it is . In either case the induction hypothesis applies at a positive starting index smaller than .
If one parity subsequence were bounded, it would be eventually constant. Its fixed splitting value in (1) would then make the other parity eventually constant as well. Let the eventual odd and even values be , respectively. Both are positive and odd, and the recurrence at sufficiently large odd and even indices gives
a contradiction. An unbounded nondecreasing sequence of odd integers starting at 1 and taking steps 0 or 2 visits every positive odd integer.
Set and, for , define
Thus records the odd positions and the even positions, with and . Both are slow: their successive increments belong to . They are unbounded and satisfy . Moreover, all four maps
are nondecreasing and 1-Lipschitz. Consequently, compositions of these maps do not amplify absolute errors, a fact used in Section 5.
Substitution into (1) gives, for ,
For example, at position the splitting value is . The two arguments in (1) are therefore and , giving (5).
Pinpointing first passages
To propagate a table to a new window, we must first locate its left endpoint . Evaluating by (5) requires , just outside that window. We overcome this difficulty by asking where first reaches the desired value .
Since is slow and nondecreasing, at the first index where , its preceding value is necessarily . Substituting into (6) at a trial index suggests the candidate expression for . Feeding this candidate into (5) in turn yields a test function . In the application, this test can be evaluated from two earlier tables.
Lemma 3 (First passage). Let , and write . For , define
Then is nondecreasing and . If and
then
Proof. The bounds give , so all terms are defined. As increases by one, increases by zero or one; the same is true of . Hence is nondecreasing. At the first passage, . Since , equation (6) applies at and gives
(5) at now gives . If , monotonicity would imply ; if , it would imply . Both are impossible, so , and the preceding values follow.
The equality at is the essential point: it locates the first passage by testing on either side of a proposed index. The identities with the true sequence values are used only at that first passage. Once it has been located, we know both and and can compute the rest of the window in order.
Exact values near the reference indices
Put . Dividing (3) by two gives
For each , the tables below record the values in a short window around , after subtracting . Their width is chosen so that every nested call needed at level can be read in the tables at levels and $j-3.
Proposition 4. For every , put . At an even level , one has
Table 9.
::: and at an odd level , one has
caption:
:::
Here is the offset from . The parity of the level selects the table, whereas its two rows correspond to the odd and even positions of . We prove the proposition by strong induction on . Three initial levels are needed because the step uses levels and .
Starting the induction
Direct evaluation of (1) through index gives the following values. Each row is read over the offsets of the appropriate table, in increasing order.
| Values on the window | |||
| : ; : | |||
| : ; : | |||
| : ; : |
Table initial.
Subtracting gives (9)–(10). The largest parity index is , corresponding to . The program in Appendix A verifies these forty values.
Locating the left endpoint
Assume the proposition holds at levels , where , and write .
Even levels. The source levels are odd and use (10). Equation (8) gives
We seek . Set and in Lemma 3. For ,
The first term is read at level and the second at level . Using their known values, followed by the definition of , gives
Table 11.
For instance, the first column is
The offsets used for are ; those for are . They all lie between and , so the earlier odd-level tables supply every entry. Since , the first and last columns of (11) locate the passage:
For example, at , and . The initial tables locate the first occurrence of 759 at 2389:
Odd levels. Now is odd, and the source levels are even. We have
To obtain , take and . For ,
and the earlier even-level tables give
The offsets used for are , , ; those for are , , , all between and 0. For example,
Here and . Lemma 3 therefore gives
Completing the tables
In either case we now know and at the left endpoint. Apply (6) and (5) alternately to obtain
The values already obtained in the new window determine the arguments of the next calls. The values at those arguments come from the known tables at levels and .
For clarity, write . If , the two arguments used to compute have offsets
relative to and , respectively. The functions read there are and . Once is known, the two arguments used to compute have offsets
and both calls read . The two source value centers add to at an even level and to at an odd level. Including the in (5), the resulting offsets from are therefore the sums of the two table entries plus 6, 7 in the even case and minus 7, 6 in the odd case, for , respectively.
The following table lists all source offsets. Each pair gives the offset at level first, then that at level ; the first -value was fixed by the first-passage argument. For example, at the start of an even-level table,
| Even level | Odd level | ||||
| for | for | for | for | ||
| fixed | fixed | ||||
Table 1.
At the start of an odd-level table,
All offsets in the even case lie in the earlier odd window , and all offsets in the odd case lie in the earlier even window . Reading these entries in order gives precisely (9)–(10), completing the induction and proving Proposition 4.
At , the proposition gives
Since , these are the exact identities
The global estimate
The reference indices are geometrically spaced. To control the values between them, we expand the two recurrences through many levels and use a quadratic bound on the resulting weighted averages. The exact values from § 4 ensure that every argument in this expansion remains at the expected scale.
Geometric scales and bounded errors
Observe from (3) that satisfies the homogeneous Narayana recurrence . Its initial values are positive. The characteristic polynomial has one real root ; the other two roots are conjugate and have modulus . The coefficient of in the solution is positive, since positivity excludes a negative coefficient and the positive recurrence keeps the terms bounded away from zero. It follows that, for some ,
The sequence is increasing: the initial values are increasing, and (8) gives . In particular, (11)–(12) give a bounded error from the line on both parities at the selected indices.
Thus either map moves three reference levels down, while either complementary map moves one level down, with uniformly bounded errors. These shifts explain the weights and , whose sum is 1. The 1-Lipschitz property ensures that an error already present is not enlarged by further composition.
We also remove the shifts in (5)–(6), at a bounded cost:
For (15), replacing by leaves error if the two values agree. Otherwise they differ by one, and the error is
which lies in . For (16), removing the in (6) changes one -value by zero or one. The cases are checked directly.
The recursion tree
Fix an integer . A node is labeled by a binary word recording the successive branch choices. The empty word labels the root. At node , we record an argument and the function evaluated there. Choose or and put . Equations (15)–(16) suggest the following expansion:
In each row the two child arguments add to , while their evaluated values add to with an error of absolute size at most 2. Branch 0 always leads to , whereas branch 1 switches and . All arguments lie in .
Write for the numbers of zeros and ones in , and give the path the weight
For the linear model , the argument at would be . We therefore normalize by this scale:
At the root, and is or . Since , we have the exact relation
The corresponding relation for has a small error inherited from (15)–(16). The next lemma controls the root error from a common bound on and a bound on that one-step error.
A finite averaging estimate
The decisive feature of (17) is that reversing two branch choices preserves their weight but changes the function reached: 10 ends at and 01 at . At the latter node, supplies the next splitting argument. This lets us compare an -value with a nearby argument at the same scale. The proof turns that comparison into a bound by summing squared increments over the tree.
Lemma 5 (Tree averaging estimate). Construct (17) to depth and use (18). Suppose that
for constants and . Then, for either initial choice of or at the root.
Proof. Let . At the root this is the required error , and (19) shows that has the same averaging error as . Because satisfies the weighted-mean relation only up to a residual bounded by , its squared increments do not telescope cleanly across levels. To restore exact telescoping, we replace by the exact backward average of its terminal values at depth : set there and define upwards. Since , both and are at most , and backward induction gives
For any quantity , write . Define the mean square increment of and the mean square of by
The exact average relation gives
Averaging and summing over the levels makes the left side telescope. Applying the same identity to , we obtain
Equivalently, and are bounded martingales along a path with branch probabilities , . In particular, the total mean square change is bounded independently of .
We now relate the errors to these increments. The two paths 10 and 01 satisfy
The weights are unchanged when the order is reversed, whereas the function labels are different. At the next branch 0 uses as its splitting map, so and
The function is 1-Lipschitz, since its increment between lies between and . Comparing it at and , with the same denominator , gives
Thus an error in an evaluated value is bounded by changes of the normalized arguments. Insert between and . The right side of (23) is at most
Its square is at most five times the sum of the five squares. For , the weighted means of these squares are bounded, in the displayed order, by
For example, choosing the suffix 10 has weight , which explains the factor in the second bound. In the last term, the coefficient cancels the two prescribed zero-branch weights. Hence
It remains to pass from the selected grandchild to its parent. The two-step variance identity for is
Keeping the nonnegative term with gives
Decompose
By (21), the middle term has absolute size at most . The inequality therefore yields
Sum over . Each is at least . From (22) and (24),
For the second inequality, the sum telescopes to . Consequently,
Taking square roots and using (21) once more at the root gives (20), since .
The factor comes from summing a square estimate over levels: a fixed error at the root contributes at every level, while the total squared change stays bounded. We now use the reference values to allow a logarithmic choice of .
A logarithmic depth
Fix by and take , with sufficiently large. For a path , put
This counts the reference levels lost along the path. Since , all reference levels used below are at least 3. Monotonicity, the Lipschitz bounds, and (14) give by induction along a path
Indeed, if the current argument is at most , either branch-0 map is at most , and either complementary map is at most . Each step adds at most 5 to the previous error.
Dividing (30) by and using (18), uniformly in ,
for a fixed constant . Here , whereas . Thus the first hypothesis of Lemma 5 holds. For the second, (20)–(21) give
We may therefore take . For either root function or , the lemma gives
The second term is , and . Hence
Returning to and proves Theorem 1.
Further questions
Is the order in Theorem 1 optimal? What is the corresponding normalized limsup? On the upper side of the limiting line, we conjecture a bounded error.
Conjecture 6. For every ,
A combinatorial description of the intervals between the reference points could explain the shapes of the arches and help determine the optimal order of the error.
Acknowledgments
The author thanks Jeffrey Shallit for discussions and automata computations. The repeating patterns in an automaton he supplied suggested the search for the local tables used in the proof.
The finite initial calculation
The following Python 3 program verifies the three initial tables in Proposition 4 in integer arithmetic. The lists aa and bb contain the two rows for even and odd levels, and lo their first offsets.
C = [0, 1, 1]
for n in range(3, 3271):
u = C[n-1]
assert 1 <= u < n and 1 <= n-u < n
C.append(C[u] + C[n-u] + (1 if n % 2 == 0 else -1))
assert C[n] > 0 and C[n] % 2 == 1
assert C[n] - C[n-2] in (0, 2)
s = [244, 352, 521, 758, 1116, 1630]
lo = [-5, -1]
aa = [[1,1,2,2,2,2], [-4,-3,-3,-2,-2,-2,-1]]
bb = [[1,2,3,3,3,4], [-3,-2,-2,-2,-2,-2,-2]]
for j in (3, 4, 5):
e = j % 2
for i in range(len(aa[e])):
k = s[j] + lo[e] + i
assert (C[2*k-1]+1)//2 == s[j-3] + aa[e][i]
assert (C[2*k]+1)//2 == s[j-3] + bb[e][i]
print("PASS: all three initial tables")References
- [1]C. L. Mallows, Conway’s challenge sequence, Amer. Math. Monthly 98 (1991), 5–20. doi:10.1080/00029890.1991.11995694.DOI
- [2]T. Kubo and R. Vakil, On Conway’s recursive sequence, Discrete Math. 152 (1996), 225–252. doi:10.1016/0012-365X(94)00303-Z.DOI
- [3]M. Mantovanelli, Dyadic self-similarity in a perturbed Hofstadter Q-recursion, preprint, 2026. arXiv:2603.16111v1.
- [4]B. Cloitre, The Mantovanelli–Hofstadter Sequence, preprint, 2026. arXiv:2604.06237.arxiv.org/abs/2604.06237
- [5]B. Cloitre, entry A399773, The On-Line Encyclopedia of Integer Sequences, 2026.
- [6]B. Cloitre, On the Mallows–Conway Sequence, manuscript, 2026.
- [7]J. Shallit, conjectural automaton for the positive part of C − R in Narayana numeration, private communication to B. Cloitre, October 2026.
