Throwback Sequences of Positive Integers

Jesiah Darnell and Benjamin F. Dribus Department of Mathematics William Carey University 710 William Carey Parkway Hattiesburg, MS 39401 USA

                  JesiahTD@gmail.com
         bdribus@wmcarey.edu, bdribus@gmail.com

Abstract

We investigate positive integer sequences called throwback sequences, generated by moving the initial term of a given sequence to the right a number of places equal to its value, then repeating this step iteratively. Let X be a sequence of distinct positive integers. We prove that each term x of X appears infinitely often in the throwback sequence T (X) of X. Further, we provide an explicit formula for the limiting frequency with which x appears in X. If X is an increasing sequence, we prove that T (X) is uniformly recurrent, i.e., every block of consecutive terms in T (X) appears infinitely often with bounded gaps between consecutive appearances. We discuss how throwback sequences relate to familiar notions such as 2-adic valuations of natural numbers and the Gray code ubiquitous in modern telecommunications. Finally, we examine sorting and mixing properties of the iterated throwback operation in certain special cases.

1 Introduction

Sequence \underline{A357081} in the On-Line Encyclopedia of Integer Sequences (OEIS) is constructed iteratively by beginning with the sequence of consecutive integers X = (3, 4, 5, …, n+3, …) and “throwing back the leader” a number of places equal to its value at each iteration. This particular choice of sequence X to demonstrate the throwback idea, rather than a more obvious choice such as (1, 2, 3, …), is a mere historical quirk [1]. The first few iterations in this case yield the sequences shown in Table 1, where bold font indicates the leader at each iteration, and parentheses indicate the term thrown back. \underline{A357081} is defined to be the sequence (3, 4, 5, 6, 3, 7, …) of “leaders” at each iteration, called the throwback sequence T (X) of X. Kozar [2, 3] conjectured that every integer n ≥ 3 recurs infinitely often in T (X). The throwback procedure generalizes to define a throwback sequence of any sequence of positive integers, and Kozar’s conjecture prompts us to undertake a broader examination of the recurrence properties of such sequences.

index n  0 1 2 3 4 5 6 7 ⋯
sequence X: 3 4 5 6 7 8 9 10 ⋯
3 thrown back: 4 5 6 (3) 7 8 9 10 ⋯
4 thrown back: 5 6 3 7 (4) 8 9 10 ⋯
5 thrown back: 6 3 7 4 8 (5) 9 10 ⋯
6 thrown back: 3 7 4 8 5 9 (6) 10 ⋯
3 thrown back: 7 4 8 (3) 5 9 6 10 ⋯

Table 1: Several iterations of the throwback operation on the beginning sequence X = (3, 4, 5, …, n + 3, …).

The rest of this paper is structured as follows. In Section 2, we give precise definitions of the throwback sequence T (X) and related notions. In Section 3, we present two theorems. Theorem 2 establishes a generalized version of Kozar’s conjecture for the throwback sequence T (X) of any sequence X of distinct positive integers. Theorem 4 provides a formula to compute the limiting frequency of each term x in such T (X). In Section 4, we introduce the closely related placement sequence P (X), which is useful for proving deeper results about throwback sequences. In Section 5, we present Theorem 7, which establishes that T (X) is uniformly recurrent in the case where X is an increasing sequence. This means that every block of consecutive terms appearing at least once in T (X) recurs infinitely often with bounded gaps between consecutive appearances. In Section 6, we illustrate examples with Python code. In Section 7, we offer a thorough discussion and present an additional theorem. We explain how throwback sequences relate to familiar notions such as the ruler function \underline{A001511} describing 2-adic valuations of natural numbers [2, 4], and the Gray code [5, 6] used for error correction purposes in modern telecommunications. We also discuss some interesting sorting and mixing properties of the iterated throwback operation that apply to certain special cases including \underline{A357081}. Theorem 9 establishes that the throwback operation constitutes a perfect mixing process for certain types of sequences.

2 Throwback sequence and related definitions

Let X = (x_{n})_{n=0}^{∞} be a sequence of positive integers, and construct a modified sequence τ(X) via the throwback operation τ defined by moving the initial term x_{0} to the right a number of places equal to its value, moving all terms of index less than or equal to x_{0} one place to the left, and leaving all terms of index greater than x_{0} in their current positions. Formally, τ(X) := (x_{1}, x_{2}, …, x_{x_{0}}, x_{0}, x_{x_{0}+1}, x_{x_{0}+2}, …). Now construct the associated throwback sequence T = (t_{n})_{n=0}^{∞} by taking t_{n} to be the initial term (“leader”) of the sequence τ^{n}(X) given by performing the throwback operation iteratively n times on X. In the case where the terms of X are distinct, define the position of a given term x after iteration n to be its index in τ^{n}(X). In the same case, define the associated sorted sequence S(X) to be the sequence whose terms are the terms of X in increasing order, and denote by σ(x) the index of x in S(X). Table 2 shows an example of a sequence of distinct positive integers X with terms x_{n}, its sorted sequence S(X) with terms s_{n}, the indices σ(x_{n}) of its terms in S(X), and its throwback sequence T (X) with terms t_{n}.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & ⋯ \\ x_{n} & 5 & 7 & 3 & 4 & 6 & 9 & 8 & 10 & ⋯ \\ s_{n} & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & ⋯ \\ σ(x_{n}) & 2 & 4 & 0 & 1 & 3 & 6 & 5 & 7 & ⋯ \\ t_{n} & 5 & 7 & 3 & 4 & 6 & 9 & 3 & 5 & ⋯ \end{matrix}

Table 2: A sequence, sorted sequence, indices in the sorted sequence, and throwback sequence.

Returning to the general case of a sequence of positive integers X, and given a pair of positive integers n and a, denote by F_{X}(n, a) the number of times a appears among the first n terms of X. Define the limiting frequency f_{X}(a) of a in X to be lim_{n→∞} F_{X}(n, a)/n, if this limit exists. It is evident that if f_{X}(a) exists for all a ≥ 1, then ∑_{a=1}^{∞} f_{X}(a) = 1. Since f_{X}(a) = 0 if a does not appear among the terms of X (the converse is generally false), we focus on the limiting frequencies f_{X}(x) for terms x of X. While we define limiting frequency for an arbitrary sequence, we are actually interested in the limiting frequency f_{T (X)}(x) of x in the throwback sequence T (X) of a given sequence X.

3 Recurrence and limiting frequency of individual terms

We begin with the following simple lemma:

Lemma 1. Let X = (x_{n})_{n=0}^{∞} be a sequence of positive integers and x a term of X. Then x either reaches a final nonleader position after a finite number of iterations of the throwback operation τ, or else becomes leader infinitely often.

Proof. The leader position cannot be the final position of x, because a positive integer is thrown back a positive number of positions by definition. Suppose that x fails to reach a final nonleader position. Then x moves an infinite number of times. Motion to the right occurs precisely when x is thrown back from the leader position, so if x moves right an infinite number of times, there is nothing to show. Assume then that x moves left an infinite number of times. Then x returns to the leader position infinitely often since each return requires only a finite number of moves to the left.

We now prove a generalization of Kozar’s conjecture.

Theorem 2. Let X be a sequence of distinct positive integers. Then each term x of X appears infinitely often in the associated throwback sequence T (X).

Proof. Suppose that a term x = x̄_{0} in X reaches a final nonleader position n_{0} > 0. The overbar on x̄_{0} is used to clarify that this term is generally not the term x_{0} of index 0 in X. Because the terms of X are distinct, the terms to the left of x̄_{0} must include a term x̄_{1} of size at least n_{0}. Throwing back x̄_{1} would move x̄_{0} left, so x̄_{1} can never be made leader and must therefore reach a final nonleader position n_{1} > 0. This argument may be repeated to obtain a strictly decreasing sequence of positive integers n_{0} > n_{1} > … whose terms all exceed 0, a contradiction. Therefore x cannot reach a final nonleader position, and must become leader infinitely often by Lemma 1.

The hypothesis of distinct terms cannot be removed in general; for example, a sequence beginning with (1, 1, …) yields a throwback sequence with constant value 1. Fully characterizing the precise conditions under which repetition negates the conclusion of Theorem 2 in the general case remains to be done. A key point seems to be that assembling terms of size at most n in the first n + 1 positions at some point in the process precludes subsequent involvement of other terms. A familiar physical analogy is the tendency of a food blender to remix already-chopped fragments at the bottom, while larger pieces remain motionless at the top. This analogy anticipates our discussion of the iterated throwback operation as a “mixing process” in Section 7.

The proof of Theorem 2 suggests a method to find an upper bound for the number of iterations between consecutive appearances of a given term as leader. For a sequence of distinct positive integers X and an index n ≥ 0, let N(n) be the number of terms in X of value less than n, and note that N(n) < n by distinctness. Let M(n) be the maximum number of iterations of τ required for the term at position n in any of the sequences τ^{m}(X) to move to the leader position. This number exists by induction on n beginning with the value M(0) = 0 given by definition of the leader position. We then have the following lemma:

Lemma 3. Let X be a sequence of distinct positive integers. Then

M(n) ≤ M(n − 1) + M(N(n)) + 1.  (1)

Proof. Let x be a term in X, and apply the throwback operation τ to X iteratively. Whenever x is at position n, at least n−N(n) terms of value at least n appear among the n terms to the left of x, so at least one of these terms has position at most N(n). After at most M(N(n)) further iterations, this term becomes leader and is thrown back at the next iteration, so x moves to position n − 1 after at most M(N(n)) + 1 iterations. By definition, at most M(n − 1) further iterations move x to the leader position. Adding these expressions yields Equation (1).

Besides its intrinsic interest, the existence of such a bound contributes to the proof of Theorem 7. The bound is not sharp in general because the terms to the left of x are generally not in the most unfavorable configuration for moving x to the left. However, this bound is seen to be sharp in the case of the ruler function \underline{A001511} via Theorem 9. Table 3 compares the predictions of Equation (1) to the actual number of iterations required for the first few terms initially at position n in the sequence X = (3, 4, 5, …, n + 3, …) to reach the leader position. The latter numbers seem to equal the terms of the sequence \underline{A155167}, which is the (L)-sieve transform of the sequence \underline{A004747} = (3, 7, 11, …, 4n − 1, …). This apparent connection was pointed out by Sloane [2].

n  0 1 2 3 4 5 6 7 8 9 10 ⋯
x_{n} 3 4 5 6 7 8 9 10 11 12 13 ⋯
bound 0 1 2 3 5 8 12 18 27 40 59 ⋯
actual 0 1 2 3 5 7 10 14 19 26 35 ⋯

Table 3: Upper bound versus actual number of iterations before first leader appearance for the sequence X = (3, 4, 5, …, n + 3, …).

We next provide a formula for the limiting frequencies of terms in the throwback sequence of a sequence of distinct positive integers.

Theorem 4. Let X be a sequence of distinct positive integers and x a term of X. Then the limiting frequency f_{T (X)}(x) of x in the associated throwback sequence T (X) is

f_{T (X)}(x) = \frac{1}{x − σ(x) + 1} ∏_{w<x} \frac{w − σ(w)}{w − σ(w) + 1},  (2)

where σ(x) is the index of x in the associated sorted sequence S(X).

Proof. Let x be a term in X. We first observe that f_{T (X)}(x) is unaffected by the frequency F_{T (X)}(n, x)/n over a finite number of terms n. We may therefore assume that all terms w < x have already been thrown back at least once. These terms thereafter remain at positions less than the value of x. The number of terms y > x to the left of x upon throwing back x is therefore equal to x − σ(x). Each such y is made leader before x is made leader again, so henceforth x appears among the terms of T (X) greater than or equal to x once every x − σ(x) + 1 times. Therefore, if the limiting frequencies f_{T (X)}(w) for all terms w < x exist, then

f_{T (X)}(x) = \frac{1 − ∑_{w<x} f_{T (X)}(w)}{x − σ(x) + 1}.

Equation (2) then follows by induction, since x_{0} moves at every iteration, and therefore f_{T (X)}(x_{0}) = 1/(x_{0} + 1).

The following easy corollary enhances Theorem 2 by establishing that appearances of a given term x in T (X) do not become arbitrarily rare:

Corollary 5. Let X be a sequence of distinct positive integers and x a term of X. Then the limiting frequency f_{T (X)}(x) of x in the associated throwback sequence T (X) is nonzero.

Proof. Because the terms of X are distinct positive integers and indexing starts at zero in the associated sorted sequence S(X), the numerator w − σ(w) in each factor in Equation (2) is strictly positive. Hence, all the factors of f_{T (X)}(x) are nonzero.

Theorem 4 may be used to infer interesting mixing properties of the iterated throwback operation, as seen in the proof of Theorem 9.

4 Placement sequence

The proof of Theorem 4 suggests an illuminating alternative construction of the throwback sequence T (X) in the case where X is increasing. Cloitre described a special case of this construction in the OEIS entry \underline{A001511} involving the ruler function, and similar constructions leading to special sequences of zeros and ones called Toeplitz sequences have previously appeared in the literature [7]. If X = (x_{n})_{n=0}^{∞} is an increasing sequence of positive integers, then we define the associated placement sequence P (X) = (p_{n})_{n=0}^{∞} iteratively by beginning with a sequence of empty positions ( , , , …), indexed starting at 0, which are then filled by copies of the terms of X in the following way. First, copies of x_{0} are placed at positions 0, x_{0} + 1, 2(x_{0} + 1), and so on, skipping over x_{0} positions each time. Next, copies of x_{1} are placed periodically in the remaining positions, beginning with the first open position and skipping x_{1} − 1 open positions each time. Continuing in this way for each positive integer n in turn, copies of x_{n} are placed periodically in the remaining positions, beginning with the first open position and skipping x_{n} − n open positions each time. The placement sequence P (X) of an increasing sequence X coincides with the throwback sequence T (X), because the number of terms greater than x_{n} to the left of x_{n} after x_{n} is thrown back is always x_{n} − n, and these terms correspond to the skipped open positions at each stage of the construction of P (X). In general, however, the two sequences differ. As illustrated by the proof of Theorem 4, the limiting frequency with which each term appears in the placement sequence P (X) is easily understood in terms of the limiting frequencies of smaller terms, since each term occupies a specified proportion of the remaining empty positions.

For the proof of Theorem 7 below, it is useful to extend the process used to construct the placement sequence P (X) to include negative indices. This yields a family {P_{n}(X)}_{n=0}^{∞} of partially defined doubly infinite sequences, called partial placement sequences, where P_{0}(X) is defined by placing copies of x_{0} at positions 0, ±(x_{0} + 1), ±2(x_{0} + 1), and so on, beginning with a doubly infinite sequence P_{−1}(X) of empty positions. P_{1}(X) is then constructed from P_{0}(X) by first placing a copy of x_{1} at position 1, then placing additional copies sequentially in both directions, skipping x_{1} − 1 open positions each time. Given P_{n−1}(X), the next partial placement sequence P_{n}(X) is defined by placing a copy of x_{n} at the first open positively indexed position, then placing additional copies sequentially in both directions, skipping x_{n} − n open positions each time. Table 4 shows the sequence X = (3, 4, 5, …, n + 3, …), its associated placement sequence P (X), in this case equal to its throwback sequence \underline{A357081}, and the partial placement sequences P_{0}(X), P_{1}(X), and P_{2}(X), with terms labeled p_{0n}, p_{1n}, and p_{2n}, respectively. Reflection symmetry about the position −2 is obvious by construction in this case. The positions −3, −2, −1 are never filled, so the construction process does not yield a complete doubly infinite sequence in the limit.

n x_{n} p_{n} p_{0n} p_{1n} p_{2n} ⋯ −7 −6 −5 −4 −3 −2 −1 01234567 ⋯ (undefined for n < 0) 3456789 10 ⋯ (undefined for n < 0) 34563748 · · · · · · 333 · · · · · · 433434 · · · · · · 54334534 ⋯

Table 4: Sequence, placement sequence, and partial placement sequences.

Periodicity of partial placement sequences plays an important role in our discussion of uniform recurrence in Section 5. Such periodicity may be viewed in terms of invariance under the actions of certain translational groups, and this leads naturally to a broader examination of symmetry properties of such sequences. A unified viewpoint is given by regarding the step-by-step construction of each P_{n}(X) from P_{n−1}(X) as a progressive symmetry breaking process. Consider the action of the group G_{−1} of all shifts and reflections on the set of all positions parameterized by ℤ. The empty doubly infinite sequence P_{−1}(X) = (…, , , , …) is invariant under the entire group. Construction of P_{0}(X) breaks this symmetry, since P_{0}(X) is invariant only under a particular subgroup G_{0}, which, in the case of X = (3, 4, 5, …, n + 3, …), shifts by multiples of 4 and/or reflects across index positions that are multiples of 2. Construction of each P_{n}(X) further breaks this symmetry, yielding a descending chain G_{−1} ⊃ G_{0} ⊃ G_{1} ⊃ … of subgroups. The intersection ⋂_{m=−1}^{∞} G_{m} is isomorphic to ℤ_{2}, generated by the reflection across −2 noted above.

5 Uniform recurrence

A sequence is called recurrent if every block B of consecutive terms in the sequence recurs infinitely often. Theorem 2 establishes a restricted form of recurrence that applies to blocks of size 1 in certain throwback sequences. A stronger property is uniform recurrence, which means that the gaps between recurrences of a given block are bounded in size. Uniform recurrence implies nonzero “block frequencies” generalizing the result for frequencies of blocks of size 1 established by Corollary 5. Theorem 7 below establishes uniform recurrence for throwback sequences of increasing sequences of positive integers in general.

To set up the proof of Theorem 7, we first consider the notion of generalized blocks in partially defined sequences for which each index position may contain either a positive integer or an empty space. The examples of present interest are the partial placement sequences P_{n}(X) defined above. We define a block B in such a partially defined sequence to be the ordered contents of a finite number of consecutive index positions, where the content at each position may be either an empty space or a positive integer. Every block of consecutive terms in a totally defined sequence is also a block in this generalized sense. Two blocks beginning at different positions are considered to be equal if they share the same size and if the corresponding positions in each block share the same contents. For example, the block of size 4 with ordered contents 3, 4, , and beginning at position 0 in the partial placement sequence P_{1}(X) of the sequence X = (3, 4, 5, …, n+3, …) is equal to the block with the same ordered contents beginning at position 16. We denote this block by (3, 4, , ) regardless of its starting position, and similarly for other blocks.

We define the past B^{−} of a block B to be the ordered contents of all index positions preceding the initial position of B. We define the future B^{+} of B to be the ordered contents of all index positions succeeding the terminal position of B. A complete block in the nth partial placement sequence P_{n}(X) of an increasing sequence of positive integers X is defined to be a block containing all the terms x_{0}, …, x_{n} from X whose copies are used to construct P_{n}(X). For a block B in P_{n}(X), the direct past B_{1}^{−} of B is defined to be the minimal complete block whose terminal position directly precedes the initial position of B, and the direct future B_{1}^{+} of B is defined to be the minimal complete block whose initial position directly succeeds the terminal position B. Figure 1 shows an incomplete block B = (3, 5, ) in the partial placement sequence P_{2}(X) of the sequence X = (3, 4, 5, …, n+3, …), together with its direct past B_{1}^{−} and direct future B_{1}^{+}.

⋯ 543345343543534 ⋯ n = 0 B_{1}^{−} B B_{1}^{+}

Figure 1: A block B in the partial placement sequence P_{2}(X) of the sequence X = (3, 4, 5, …, n + 3, …), together with its direct past B_{1}^{−} and direct future B_{1}^{+}.

Two equal blocks occurring at different positions in the partial placement sequence P_{n}(X) may have different pasts and/or futures; for example, the block (3, 4) of size 2 beginning at position 0 in Figure 1 is preceded by an empty position, while the same block beginning at position 16 is preceded by a copy of 5. However, by construction, a complete block uniquely determines its entire past and future, and hence the entire partial placement sequence P_{n}(X). Indeed, specifying a single position occupied by x_{0} determines all other such positions; supplementing this information by specifying a single position occupied by x_{1} determines all other such positions, and so on. These determinations involve only relative distances from the specified positions. Hence, if two copies of the same complete block begin at different positions l < m in P_{n}(X), then the entire sequence is periodic with period m − l since the empty space or positive integer at each position m + k for each k ∈ ℤ must match the empty space or positive integer at each position l + k. Further, a minimal complete block in P_{n}(X) has size bounded in terms of n by Equation (1), so only a finite number of minimal complete blocks exist, since the number of possible configurations of copies of x_{0}, …, x_{n} in a finite number of positions is finite.

A more refined counting argument gives an upper bound for the number of minimal complete blocks in P_{n}(X). Given the starting position of such a block, there are at most x_{0} + 1 possible positions for the first appearance of x_{0}, then x_{1} remaining possible positions for the first appearance of x_{1}, and so on, up to x_{n} −n+1 remaining possible positions for the first appearance of x_{n}. Once these positions are specified, the entire block, and indeed the entire sequence P_{n}(X), are determined. Hence, the maximum possible number of minimal complete blocks is

∏_{k=0}^{n}(x_{k} − k + 1).  (3)

For example, there are at most 4^{3} = 64 minimal complete blocks in the partial placement sequence P_{2}(X) of the sequence X = (3, 4, 5, …, n + 3, …), since the first copy of 3 may appear in any of the first four positions in the block, after which the first copy of 4 may appear in any of the first four remaining positions, after which the first copy of 5 may appear in any of the first four remaining positions. It is easy to check that 64 distinct minimal complete blocks actually occur in this case, so the bound in Equation (3) can be sharp in some cases. Theorem 9 explains and extends this observation. On the other hand, complications such as the presence of common factors among consecutive terms in the original sequence can reduce the number of minimal complete blocks that actually appear in P_{n}(X); for example, sequences beginning with (2, 4, …) or (3, 6, …) or (4, 6, …) produce partial placement sequences with fewer than the maximum possible number of minimal complete blocks given by Equation (3). However, the mere fact that the number of such blocks is finite is sufficient for the proof of the following lemma:

Lemma 6. The partial placement sequence P_{n}(X) of an increasing sequence of positive integers X is periodic.

Proof. Given a block B, first extend B to a complete block B_{0}, if necessary, by adding a finite number of positions to the right and/or left; this is always possible due to the bound given by Equation (1). Next, construct a sequence of disjoint minimal complete blocks (B_{m})_{m=1}^{∞}, where B_{1} is the direct future of B_{0}, and where each B_{m} is the direct future of B_{m−1} for m > 1. Since the number of such blocks is finite, two of them must coincide, so P_{n}(X) is periodic by the previous discussion.

Establishing such periodicity is the motivation for extending the partial placement sequences P_{n}(X) to include negative indices and for noting that both the past B^{−} and the future B^{+} of a complete block B are determined by B. Restricting attention to positive indices and future determinations would yield only eventual periodicity of blocks. Theorem 7 now follows from the simple observation that any block in the placement sequence P (X) of an increasing sequence of positive integers X is already present in one of the partial placement sequences.

Theorem 7. The throwback sequence T (X) of an increasing sequence of positive integers X is uniformly recurrent.

Proof. Let B be a block in T (X), and let x_{n} be the largest term in B. Since X is increasing, T (X) coincides with the placement sequence P (X) of X. The partial placement sequence P_{n}(X) contains all the terms of P (X) up to and including x_{n}, in the same positions, so B appears as a block in P_{n}(X). Therefore, by Lemma 6, B appears periodically in P_{n}(X), and hence also in T (X).

While the period arising from Lemma 6 bounds the gaps between consecutive appearances of B in T (X), additional appearances of B are possible and seem to occur in most cases. This phenomenon seems to be related to the existence of several different pasts and futures for incomplete blocks occurring at different index positions. For example, the block (3, 5) in the partial placement sequence P_{2}(X) of the sequence X = (3, 4, 5, …, n + 3, …) illustrated in Figure 1 occurs at position 8 with direct future ( , 4, 3, , , 5), at position 36 with direct future (4, , 3, , , 4, 3, 5), and at position 44 with direct future ( , , 3, 4, , 5). The gaps between consecutive appearances of this block seem to follow the pattern of sizes 28, 8, 28, which sum to the period size 64.

We now establish the useful though unsurprising fact that minimal complete blocks in the partial placement sequence P_{n}(X) of an increasing sequence X correspond bijectively to configurations of the terms x_{0}, …, x_{n} that result from repeated application of the throwback operation τ to X. This relationship is expected because the same counting argument leading to Equation (3) applies to such configurations: there are x_{0} + 1 possible positions for x_{0}, leaving x_{1} remaining possible positions for x_{1}, and so on. Such configurations are of interest because they measure how repeated application of the throwback operation τ sorts and/or mixes the terms of X, the subject of Theorem 9 below. For example, the minimal complete block (4, 3, , , 5) beginning at index position 11 in the partial placement sequence P_{2}(X) of X = (3, 4, 5, …, n + 3, …) illustrated in Figure 1, indicates that the sequence τ^{11}(X) begins (4, 3, ∗, ∗, 5, …), where the symbol ∗ is used as shorthand for any term greater than 5 (in this case 6 and 10). The index positions of the terms 3, 4, and 5 in τ^{11}(X) are therefore 1, 0, and 4, respectively. Generalizing this example, we define a configuration C of the terms x_{0}, …, x_{n} of an increasing sequence of positive integers X to be an ordered list of n + 1 non-negative integers specifying the index positions of these terms in X or in a rearranged version of X, including the sequences τ^{k}(X). Note that τ may be applied unambiguously to such a configuration since throwing back a term larger than x_{n} moves all the terms x_{0}, …, x_{n} one place to the left. We now have the following lemma:

Lemma 8. Minimal complete blocks in the partial placement sequence P_{n}(X) of an increasing sequence of positive integers X correspond bijectively to configurations of the terms x_{0}, …, x_{n} appearing in the sequences τ^{k}(X) for nonnegative integers k.

Proof. Given a configuration of x_{0}, …, x_{n} in τ^{k}(X) for some k ≥ 0, it is clear that additional applications of τ will produce a specific minimal complete block beginning at position k in the partial placement sequence P_{n}(X) of X, and that every minimal complete block appearing in P_{n}(X) arises in this way. It remains to show that different configurations lead to different blocks. Consider two different configurations C_{1} and C_{2}, and let x_{m} be the smallest among the terms x_{0}, …, x_{n} whose positions in C_{1} and C_{2} differ; assume without loss of generality that the position of x_{m} is smaller in C_{1}. If x_{m} is the leader in C_{1}, then there is nothing to show. Otherwise, apply τ to both configurations. The terms thrown back are either both larger or both smaller than x_{m} because the positions of the smaller terms agree in C_{1} and C_{2}. If both terms thrown back are larger than x_{m}, then x_{m} moves one place to the left in both cases, and the argument may be repeated because the positions of the smaller terms change in the same way for both configurations. If both terms thrown back are smaller than x_{m}, then they are the same term for C_{1} and C_{2}, since x_{m} is the smallest term whose positions in the two configurations differ. Hence, if x_{m} moves left in C_{2}, then it also moves left in C_{1}, and the argument may be repeated because the positions of the smaller terms change in the same way for both configurations. Therefore x_{m} becomes leader earlier in the case of C_{1}, producing a different block than in the case of C_{2}.

6 Examples with code

We now illustrate how some of these ideas may be explored numerically, using for illustration the increasing sequence X = (1, 3, 4, 5, …, n + 3, …), which consists of all positive integers except 2. The following Python code generates the first 10^{4} terms of the associated throwback sequence T (X) and prints its first 20 terms:

X=[1]
for i in range(0,100):
  X.append(i+3)
Y=X; T=[]; loops=10000
for l in range(0,loops):
  leader=Y[0]
  T.append(leader)
  Y.pop(0)
  Y.insert(leader,leader)
print(T[0:20])

The output is

   [1, 3, 1, 4, 1, 5, 1, 3, 1, 6, 1, 4, 1, 3, 1, 7, 1, 5, 1, 3].

The following Python code computes and prints the frequencies of the first 10 terms of X over the first 10^{4} terms of T (X):

M=max(T)
counter vector=np.zeros(M); freq vector=np.zeros(M)
for i in range(0,M):
  for j in range(0,len(T)):
     if T[j]==i:
       counter vector[i]+=1
for i in range(0,M):
  freq vector[i]=counter vector[i]/loops
for i in range(0,10):
  print(round(freq vector[i],5),end=", ")

The output is

   0.0, 0.5, 0.0, 0.1667, 0.1111, 0.0741, 0.0494, 0.0329, 0.0220, 0.0146,

which closely agrees with the formulae f_{T (X)}(x_{0}) = 1/2 and f_{T (X)}(x_{n}) = 2^{n−2}/3^{n} for n ≥ 1 from Equation (2). The following Python code generates the first few terms of the corresponding placement sequence P (X):

places=100
P=np.zeros(places,dtype=int)
max fill=11
for i in range(0,max fill):
  counter=0
  for j in range(0,places):
     if P[j]==0:
       if counter%(X[i]-i+1)==0:
         P[j]=X[i]
       counter+=1
print(P[0:20])

The output is, as expected, the same as for the throwback sequence T (X):

   [1, 3, 1, 4, 1, 5, 1, 3, 1, 6, 1, 4, 1, 3, 1, 7, 1, 5, 1, 3].

The following Python code generates and prints recurrences of the initial block (1, 3, 1, 4) in the first 300 terms of T (X):

recur list=[]
gaps list=[]
for i in range(0,300):
  if T[i]==1:
     if T[i+1]==3:
       if T[i+2]==1:
         if T[i+3]==4:
           recur list.append(i)
for k in range(0,len(recur list)-1):
  gaps list.append(recur list[k+1]-recur list[k])
print(gaps list)

The output is

   [18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18],

which suggests that this block recurs periodically with gaps of size 18, the largest possible size in view of Equation (3).

7 Discussion and historical notes

The throwback sequence of the sequence ℤ^{+} = (1, 2, 3, …) of all positive integers is the familiar ruler function \underline{A001511} [2, 4], whose value at n is the 2-adic valuation of 2n; i.e., the highest power of 2 that divides 2n. This is readily seen from the viewpoint of the placement sequence, since each number fills half the remaining open positions. The ruler function defines the order in which bits are changed for purposes of binary counting in the Gray code [5, 6], used extensively in modern telecommunications for the purpose of error correction. A basic advantage of the Gray code is that incrementing a number from n to n + 1 changes only one bit, in contrast to ordinary binary counting, where, for example, incrementing from 3 to 4 changes all the bits 011 to 100. Changing only one bit at a time reduces the risk of computing errors of physical origin caused by lack of precise simultaneity in changing multiple bits. Some of these notions might generalize in interesting ways to other throwback sequences. Kozar [3] outlined a number of additional questions and open problems involving throwback sequences, such as describing the precise patterns in which terms recur, and investigating the sequences of indices at which terms first appear. Other closely-related sequences and/or sequences involving variants of the throwback procedure include \underline{A087165}, \underline{A155167}, \underline{A354223}, and \underline{A355080} on the OEIS.

Despite close similarities in construction and/or structure among such sequences, their levels of complexity seem to differ in significant ways, and certain properties that appear likely to be true based on numerical evidence seem significantly easier to prove for some such sequences than for others. For example, both \underline{A357081} (the throwback sequence of X = (3, 4, 5, …, n + 3, …)) and \underline{A001511} (the ruler function, or throwback sequence of ℤ^{+}) are uniformly recurrent by Theorem 7, but the precise behavior of blocks seems to be much simpler in the latter sequence. Each block B in \underline{A001511} seems to recur with gaps of size 2^{n}, where n is the largest element in the block. An easy application of Theorem 9 below shows that this is indeed the case. By contrast, blocks in \underline{A357081} exhibit a variety of different types of behavior. For example, the block (3, 4, 5) appears to recur with uniform gaps of size 4^{3} = 64, while the block (6, 3, 7) appears to recur with the pattern of gap sizes 228, 492, 228, 76, which sum to 1024 = 4^{5}, the apparent gap size for the complete “parent” block (3, 4, 5, 6, 3, 7), which matches the upper bound given by Equation (3). More generally, it appears to be true that τ^{4^{n}} fixes the first n terms of the sequence (3, 4, 5, …, n + 3, …). This observation, also established by Theorem 9, leads to consideration of two other general properties that seem to be satisfied by the iterated throwback operation in certain cases, and that are of obvious interest in computer science.

First, repeated application of τ to an arbitrary sequence of distinct positive integers X may be regarded as an average sorting process in the sense that each term x of X remains within distance x of position zero after it is first thrown back. This idea could be quantified and refined by deriving formulae for the limiting average positions of terms, analogous to the limiting frequencies established by Theorem 4. Such results might be of interest in the context of random number generation, since a specified distribution of integers would result from querying a given position repeatedly while running many iterations of τ. The same notion of average sorting could also be extended to a broader context including negative integers and doubly infinite sequences, in which positive integers are thrown to the right from position zero, while negative integers are thrown to the left. In either context, recurrence results such as those given by Theorems 2 and 7 could be generalized to describe the eventual behavior of blocks of “previously sorted” integers; i.e., those that have already been thrown back at least once.

Second, for certain privileged sequences X, repeated application of τ constitutes a perfect mixing process, meaning that the first n terms x_{0}, …, x_{n} of X pass through every possible configuration before returning to their initial order. Theorem 9 establishes that sequences of consecutive positive integers satisfy this property. For example, for the sequence X = (3, 4, 5, …, n + 3, …), there are 4^{2} = 16 possible configurations of 3 and 4, equal to the maximum possible number of minimal complete blocks in the partial placement sequence P_{1}(X) of X given by Equation (3), since such blocks and configurations correspond bijectively by Lemma 8. Figure 2 demonstrates how all these configurations indeed result from repeated application of τ, where the symbol ∗ is used as shorthand for any term greater than 4, and where dots indicating continuation are suppressed for legibility.

Perfect mixing seems to be related to divisibility properties in an interesting way, which we illustrate by proving a special case. We first note that the family of minimal complete blocks that actually occur in the partial placement sequence P_{n}(X) of an increasing sequence of positive integers X must appear in some linear order, with each block overlapping one or more succeeding blocks for n > 0. No block may repeat before all the blocks have

τ^{0} : 3, 4, ∗, ∗, ∗  τ^{4} : 3, ∗, 4, ∗, ∗  τ^{8} : 3, ∗, ∗, 4, ∗  τ^{12} : 3, ∗, ∗, ∗, 4
τ^{1} : 4, ∗, ∗, 3, ∗  τ^{5} : ∗, 4, ∗, 3, ∗  τ^{9} : ∗, ∗, 4, 3, ∗  τ^{13} : ∗, ∗, ∗, 3, 4
τ^{2} : ∗, ∗, 3, ∗, 4  τ^{6} : 4, ∗, 3, ∗, ∗  τ^{10} : ∗, 4, 3, ∗, ∗  τ^{14} : ∗, ∗, 3, 4, ∗
τ^{3} : ∗, 3, ∗, 4, ∗  τ^{7} : ∗, 3, ∗, ∗, 4  τ^{11} : 4, 3, ∗, ∗, ∗  τ^{15} : ∗, 3, 4, ∗, ∗

Figure 2: Perfect mixing: every possible configuration of 3 and 4 occurs under repeated application of τ to X = (3, 4, 5, …, n + 3, …).

appeared, since repetition of a block implies the beginning of a new period. For example, in the partial placement sequence P_{1}(X) of the sequence X = (3, 4, 5, …, n + 3, …), the 16 minimal complete blocks appear in the overlapping order

(3, 4), (4, , , 3), ( , , 3, , 4), ( , 3, , 4), (3, , 4), …

where block n + 1 is constructed by deleting the first entry of block n and then adding the minimal number of positions to the right necessary to (re)complete the block. The leading elements of each of these blocks, are, of course, the terms of P_{n}(X). Since P_{n}(X) is periodic by Lemma 6, the limiting frequency with which each term x appears in P_{n}(X), and hence in the throwback sequence T (X), is just the ratio of the number of minimal complete blocks beginning with x to the total number of such blocks. However, this limiting frequency is also given by Theorem 4. Equating these two results for the sequence X = (3, 4, 5, …, n + 3, …) leads to the equation

\frac{minimal complete blocks starting with x}{total minimal complete blocks} = \frac{3^{x−3}}{4^{x−2}} ,  (4)

where the right hand side comes from Theorem 4, and the denominator is the upper bound for the maximum possible number of minimal complete blocks given by Equation (3). This denominator must equal the total number of minimal complete blocks because 3 and 4 are coprime. Therefore, every possible minimal complete block actually appears in this case, and since these blocks correspond bijectively with possible configurations of the terms x_{0}, …, x_{n} by Lemma 8, perfect mixing occurs. We can readily generalize this argument to apply to sequences of consecutive positive integers.

Theorem 9. Let X be a sequence of consecutive positive integers beginning with some positive integer m. Then repeated application of the throwback operation τ is a perfect mixing process in the sense that the first n + 1 terms m, m + 1, …, m + n of X pass through every possible configuration before returning to their original order with the (m + 1)^{n+1}th application of τ.

Proof. The ratio of the number of minimal complete blocks beginning with m + n to the total number of such blocks that actually appear in the partial placement sequence P_{n}(X) of X is \frac{m^{n}}{(m+1)^{n+1}} by Theorem 4. Since m and m + 1 are coprime, the total number of minimal complete blocks that actually appear is equal to the denominator (m + 1)^{n+1}, which is equal to the upper bound given by Equation (3). Since this number is also equal to the maximum possible number of configurations of the first n terms of X by Lemma 8, every possible configuration appears.

For example, 2^{n+1} applications of τ fix the first n + 1 terms of the ruler function, just as one would expect. Perfect mixing does not seem to be restricted to sequences of consecutive positive integers. For example, the maximum possible period size of 18 observed numerically for recurrence of the block (1, 3, 1, 4) in the throwback sequence of the sequence X = (1, 3, 4, 5, …, n + 2, …) in Section 6 suggests perfect mixing for the terms 1, 3, and 4 in this sequence. However, Theorem 4 does not seem to provide a straightforward argument for why every possible configuration should occur in this case; it allows for a period of either 9 or 18. Failure of perfect mixing sometimes seems to be related to the presence of common factors, as observed from the perspective of minimal complete blocks for sequences beginning with (2, 4, …) or (3, 6, …) or (4, 6, …) in the discussion following Equation (3). However, perfect mixing often fails even when common factors are absent; for example, the block (2, 3, 5) in the throwback sequence of the sequence of primes recurs every 9 positions, instead of the maximum possible of 36 given by Equation (3). Hence, characterizing which sequences exhibit perfect mixing remains mostly open, although further divisibility arguments involving Theorem 9 can likely provide useful constraints on the numbers of configurations in some cases.

Extending the placement sequence P (X) to include negative indices in the construction of the partial placement sequences P_{n}(X) naturally suggests the idea of inverting the throwback procedure. This then leads to consideration of which sequences could have been obtained by throwing back the initial term of another sequence. The answer is straightforward: a sequence X can be τ(W) for some sequence W if and only if the index of some term in X equals its value. For example, the sequence X = (3, 4, 5, …, n+3, …) cannot be obtained by applying τ to any sequence of positive integers because the value of every term in X exceeds its index. This offers another explanation for why the positions −3, −2, and −1 are never filled during the construction of the partial placement sequences for X illustrated in Table 4. Admitting transfinite ordinals to the picture could alter such considerations; for example, the sequence (3, 4, 5, …, n + 3, …, ω) could be regarded as τ(ω, 3, 4, 5, …, n + 3, …), where ω is the smallest transfinite ordinal. We also note that inverting τ is generally non-unique; for example, a sequence beginning (7, 5, 1, 3, 4, 8, …) could be the throwback sequence of a sequence beginning either (3, 7, 5, 1, 4, 8, …) or (4, 7, 5, 1, 3, 8, …). The extent of nonuniqueness is measured by how many terms have values equal to their indices.

The historical origin of the throwback operation remains somewhat obscure. The earliest mention we can find in the literature appears in a Popular Computing article from 1977 [1]. Photocopied images of this article appear on the OEIS page for \underline{A357081} [2]. There seem to have been several distinct publications named Popular Computing around this time [3]. The one of present interest was initiated in 1973 by Gruenberger [8, 9], who produced the magazine on a monthly basis until 1981, before selling it to McGraw Hill who produced it until 1985. No digital public copies of Popular Computing are known to exist, though physical copies of certain issues apparently remain. We could not find complete copies of the relevant 1977 issue, or otherwise determine if the throwback operation mentioned there might originate from some earlier source.

8 Acknowledgments

We thank Jeffrey Shallit for proposing the uniform recurrence problem for throwback sequences. We thank the referee for many helpful suggestions. We also thank our colleague Landon Adams for drawing our attention to some of the historical sources.

References

[1] F. Gruenberger, Coding fun: rearranging all the numbers, Popular Computing 5 (1977), 55.

[2] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2024.

[3] A. M. Kozar, Throwback all of your number sequences, 2022. Available at

   http://www.anthonykozar.net/posts/2022/09/05/.

[4] A. Erickson, A. Isgur, B. W. Jackson, F. Ruskey, and S. M. Tanny, Nested recurrence relations with Conolly-like solutions, SIAM J. Discrete Math. 26 (2012), 206–238.

[5] F. Gray, Pulse code communication, Bell Telephone Laboratories, Inc., U.S. patent 2,632,058, serial number 785697, 1947.

[6] F. Herter and G. Rote, Loopless Gray code enumeration and the Tower of Bucharest, Theor. Comput. Sci. 748 (2018), 40–54.

[7] K. Jacobs and M. Keane, 0-1-Sequences of Toeplitz type, Z. Wahrscheinlichkeitstheorie Verw. Gebiete 13 (1969) 123–131.

[8] Stanford Libraries SearchWorks, Popular Computing, 2024. Available at https://

   searchworks.stanford.edu/view/380699.

[9] Technical Archive, Fred Gruenberger and the “original” Popular Computing, 2024. Avail-

   able at https://www.techarc.com/gruenberger.

2020 Mathematics Subject Classification: Primary 11B99; Secondary 11B05, 11B85.

Keywords: throwback sequence, ruler function, limiting frequency, iteratively constructed sequence, uniform recurrence.

(Concerned with sequences \underline{A001511}, \underline{A004747}, \underline{A087165}, \underline{A155167}, \underline{A354223}, \underline{A355080}, and \underline{A357081}.)

Received July 16 2024; revised versions received September 5 2024; January 7 2025; January 10 2025; September 11 2025. Published in Journal of Integer Sequences, September 14 2025.

Return to Journal of Integer Sequences home page.