\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\tn}[1]{\textnormal{#1}}
\def\ZZ{\mathbb{Z}}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf Throwback Sequences of Positive Integers
}
\vskip 1cm
\large
Jesiah Darnell and Benjamin F. Dribus\\
Department of Mathematics\\
William Carey University\\
710 William Carey Parkway\\
Hattiesburg, MS 39401\\
USA\\
\href{mailto:JesiahTD@gmail.com}{\tt JesiahTD@gmail.com}\\
\href{mailto:bdribus@wmcarey.edu}{\tt bdribus@wmcarey.edu}, \href{mailto:bdribus@gmail.com}{\tt bdribus@gmail.com}\\
\end{center}

\vskip .2 in
\begin{abstract}
\noindent 
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.
\end{abstract}

\section{Introduction}
\label{sectionintro}

Sequence \seqnum{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,\ldots,n+3,\ldots)$ 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,\ldots)$, is a mere historical quirk \cite{PC}. The first few iterations in this case yield the sequences shown in Table \ref{tab_throw}, where bold font indicates the leader at each iteration, and parentheses indicate the term thrown back.  \seqnum{A357081} is defined to be the sequence $(3,4,5,6,3,7,\ldots)$ of ``leaders'' at each iteration, called the 
 {\it throwback sequence} $T(X)$ of $X$.  Kozar \cite{OEIS,KozarPage} conjectured that every integer $n\ge3$ 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. 

\begin{table}[htb]
\begin{center}
\begin{tabular}{c|ccccccccccccc}
index $n$   & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & $\cdots$ \\
\hline
sequence $X$: & $\mbf{3}$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ & $\cdots$ \\
$3$ thrown back: & $\mbf{4}$ & $5$ & $6$ & $(3)$ & $7$ & $8$ & $9$ & $10$ & $\cdots$ \\
$4$ thrown back: & $\mbf{5}$ & $6$ & $3$ & $7$ & $(4)$ & $8$ & $9$ & $10$ & $\cdots$ \\
$5$ thrown back: & $\mbf{6}$ & $3$ & $7$ & $4$ & $8$ & $(5)$ & $9$ & $10$ & $\cdots$ \\
$6$ thrown back: & $\mbf{3}$ & $7$ & $4$ & $8$ & $5$ & $9$ & $(6)$ & $10$ & $\cdots$ \\
$3$ thrown back: & $\mbf{7}$ & $4$ & $8$ & $(3)$ & $5$ & $9$ & $6$ & $10$ & $\cdots$ \\
\end{tabular}
\end{center}
\caption{Several iterations of the throwback operation on the beginning sequence $X=(3,4,5,\ldots,n+3,\ldots)$. \label{tab_throw}}
\end{table}

The rest of this paper is structured as follows.  In Section \ref{sectionmathbackground}, we give precise definitions of the throwback sequence $T(X)$ and related notions. In Section \ref{sectionthem}, we present two theorems.  Theorem \ref{thm_inf} establishes a generalized version of Kozar's conjecture for the throwback sequence $T(X)$ of any sequence $X$ of distinct positive integers.  Theorem \ref{thm_freq} provides a formula to compute the limiting frequency of each term $x$ in such $T(X)$.  In Section \ref{sectionplacementsequence}, we introduce the closely related {\it placement sequence} $P(X)$, which is useful for proving deeper results about throwback sequences.  In Section \ref{section_uniform}, we present Theorem \ref{thm_rec}, which establishes that $T(X)$ is {\it 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 \ref{section_code}, we illustrate examples with Python code.  In Section \ref{section_discussion}, we offer a thorough discussion and present an additional theorem.  We explain how throwback sequences relate to familiar notions such as the {\it ruler function} \seqnum{A001511} describing $2$-adic valuations of natural numbers \cite{OEIS,Erickson}, and the {\it Gray code} \cite{Gray,Herter} 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 \seqnum{A357081}.  Theorem \ref{thm_div} establishes that the throwback operation constitutes a {\it perfect mixing process} for certain types of sequences. 

\section{Throwback sequence and related definitions}
\label{sectionmathbackground}

Let $X=(x_n)_{n=0}^\infty$ be a sequence of positive integers, and construct a modified sequence $\tau(X)$ via the {\it throwback operation} $\tau$ 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, $\tau(X):=(x_1,x_2,\ldots,x_{x_0},x_0,x_{x_0+1},x_{x_0+2},\ldots)$.  Now construct the associated {\it throwback sequence} $T=(t_n)_{n=0}^\infty$ by taking $t_n$ to be the initial term (``leader'') of the sequence $\tau^{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 {\it position} of a given term $x$ after iteration $n$ to be its index in $\tau^n(X)$.   In the same case, define the associated {\it sorted sequence} $S(X)$ to be the sequence whose terms are the terms of $X$ in increasing order, and denote by $\sigma(x)$ the index of $x$ in $S(X)$.  Table \ref{tab_seq} 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 $\sigma(x_n)$ of its terms in $S(X)$, and its throwback sequence $T(X)$ with terms $t_n$.

\begin{table}[htb]
\begin{center}
\begin{tabular}{c|ccccccccccccc}
$n$   & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & $\cdots$ \\
\hline
$x_n$ & 5 & 7 & 3 & 4 & 6 & 9 & 8 & 10 & $\cdots$ \\
$s_n$ & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & $\cdots$\\
$\sigma(x_n)$ & 2 & 4 & 0 & 1 & 3 & 6 & 5 & 7 & $\cdots$\\
$t_n$ & 5 & 7 & 3 & 4 & 6 & 9 & 3 & 5 & $\cdots$\\
\end{tabular}
\end{center}
\caption{A sequence, sorted sequence, indices in the sorted sequence, and throwback sequence. \label{tab_seq}}
\end{table}

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 {\it limiting frequency} $f_X(a)$ of $a$ in $X$ to be $\lim_{n\to\infty}F_X(n,a)/n$, if this limit exists. It is evident that if $f_X(a)$ exists for all $a\ge1$, then $\sum_{a=1}^{\infty}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$. 

\section{Recurrence and limiting frequency of individual terms}
\label{sectionthem}

We begin with the following simple lemma:

\begin{lemma}\label{lem_final_position} Let $X=(x_n)_{n=0}^\infty$ 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 $\tau$, or else becomes leader infinitely often.
\end{lemma}
\begin{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. 
\end{proof}

We now prove a generalization of Kozar's conjecture. 

\begin{theorem}\label{thm_inf} 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)$.
\end{theorem}

\begin{proof}  Suppose that a term $x=\bar{x}_0$ in $X$ reaches a final nonleader position $n_0>0$.   The overbar on $\bar{x}_0$ is used to clarify that this term is generally {\it not} the term $x_0$ of index $0$ in $X$. Because the terms of $X$ are distinct, the terms to the left of $\bar{x}_0$ must include a term $\bar{x}_1$ of size at least $n_0$.  Throwing back $\bar{x}_1$ would move $\bar{x}_0$ left, so $\bar{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>\ldots$ whose terms all exceed $0$, a contradiction.  Therefore $x$ cannot reach a final nonleader position, and must become leader infinitely often by Lemma \ref{lem_final_position}.
\end{proof}

The hypothesis of distinct terms cannot be removed in general; for example, a sequence beginning with $(1,1,\ldots)$ yields a throwback sequence with constant value $1$.  Fully characterizing the precise conditions under which repetition negates the conclusion of Theorem \ref{thm_inf} 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 \ref{section_discussion}.

The proof of Theorem \ref{thm_inf} 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\ge0$, 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 $\tau$ required for the term at position $n$ in any of the sequences $\tau^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:

\begin{lemma}\label{lem_upper_bound} Let $X$ be a sequence of distinct positive integers. Then
\begin{equation}\label{equ_bound} 
M(n)\le M(n-1)+M(N(n))+1.
\end{equation}
\end{lemma}
\begin{proof}  Let $x$ be a term in $X$, and apply the throwback operation $\tau$ 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 \eqref{equ_bound}.
\end{proof}

Besides its intrinsic interest, the existence of such a bound contributes to the proof of Theorem \ref{thm_rec}.  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 \seqnum{A001511} via Theorem \ref{thm_div}. Table \ref{tab_first} compares the predictions of Equation \eqref{equ_bound} to the actual number of iterations required for the first few terms initially at position $n$ in the sequence $X=(3,4,5,\ldots,n+3,\ldots)$ to reach the leader position. The latter numbers seem to equal the terms of the sequence \seqnum{A155167}, which is the {\it (L)-sieve transform} of the sequence \seqnum{A004747} $ =(3,7,11,\ldots,4n-1,\ldots)$. This apparent connection was pointed out by Sloane \cite{OEIS}.

\begin{table}[htb]
\begin{center}
\begin{tabular}{c|cccccccccccccccc}
$n$   & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9& 10& $\cdots$ \\
\hline
$x_n$ & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & $\cdots$ \\
bound & 0 & 1 & 2 & 3 & 5 & 8 & 12 & 18 & 27 & 40 & 59 & $\cdots$\\
actual & 0 & 1 & 2 & 3 & 5 & 7 & 10 & 14 & 19 & 26 & 35 &$\cdots$\\

\end{tabular}
\end{center}
\caption{Upper bound versus actual number of iterations before first leader appearance for the sequence $X=(3,4,5,\ldots,n+3,\ldots)$. \label{tab_first}}
\end{table}

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

\begin{theorem}\label{thm_freq} 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 
\begin{equation}\label{equ_freq}
f_{T(X)}(x)=\frac{1}{x-\sigma(x)+1}\prod_{w<x}\frac{w-\sigma(w)}{w-\sigma(w)+1},
\end{equation}
where $\sigma(x)$ is the index of $x$ in the associated sorted sequence $S(X)$.
\end{theorem}

\begin{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-\sigma(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-\sigma(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-\displaystyle\sum_{w<x}f_{T(X)}(w)}{x-\sigma(x)+1}.\]
Equation \eqref{equ_freq} then follows by induction, since $x_0$ moves at every iteration, and therefore $f_{T(X)}(x_0)=1/(x_0+1)$. 
\end{proof}

The following easy corollary enhances Theorem \ref{thm_inf} by establishing that appearances of a given term $x$ in $T(X)$ do not become arbitrarily rare:

\begin{corollary}\label{cor_nonzero} 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.
\end{corollary}
\begin{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-\sigma(w)$ in each factor in Equation \eqref{equ_freq} is strictly positive. Hence, all the factors of  $f_{T(X)}(x)$ are nonzero. 
\end{proof}

Theorem \ref{thm_freq} may be used to infer interesting mixing properties of the iterated throwback operation, as seen in the proof of Theorem \ref{thm_div}.  

\section{Placement sequence} 
\label{sectionplacementsequence}

The proof of Theorem \ref{thm_freq}  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 \seqnum{A001511} involving the ruler function, and similar constructions leading to special sequences of zeros and ones called {\it Toeplitz sequences} have previously appeared in the literature \cite{JacobsKeane}.    If $X=(x_n)_{n=0}^\infty$ is an increasing sequence of positive integers, then we define the associated {\it placement sequence} $P(X)=(p_n)_{n=0}^\infty$ iteratively by beginning with a sequence of empty positions $(\underline{\hspace*{.3cm}},\underline{\hspace*{.3cm}},\underline{\hspace*{.3cm}},\ldots)$, 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 \ref{thm_freq}, 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 \ref{thm_rec} 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}^{\infty}$ of partially defined doubly infinite sequences, called {\it partial placement sequences,} where $P_0(X)$ is defined by placing copies of $x_0$ at positions $0$, $\pm(x_0+1)$, $\pm2(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 \ref{tab_pps} shows the sequence $X=(3,4,5,\ldots,n+3,\ldots)$, its associated placement sequence $P(X)$, in this case equal to its throwback sequence \seqnum{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. 

\begin{table}[htb]
\begin{center}
\begin{pgfpicture}{0cm}{0cm}{14cm}{3.6cm}
\begin{pgftranslate}{\pgfpoint{0cm}{-.3cm}}
\pgfxyline(0,3.3)(13.65,3.3)
\pgfxyline(1,3.8)(1,0)
\pgfputat{\pgfxy(.5,3.55)}{\pgfbox[center,center]{$n$}}
\pgfputat{\pgfxy(.5,2.9)}{\pgfbox[center,center]{$x_n$}}
\pgfputat{\pgfxy(.5,2.25)}{\pgfbox[center,center]{$p_n$}}
\pgfputat{\pgfxy(.5,1.6)}{\pgfbox[center,center]{$p_{0n}$}}
\pgfputat{\pgfxy(.5,.95)}{\pgfbox[center,center]{$p_{1n}$}}
\pgfputat{\pgfxy(.5,.3)}{\pgfbox[center,center]{$p_{2n}$}}
\pgfputat{\pgfxy(1.5,3.55)}{\pgfbox[center,center]{$\cdots$}}
\pgfputat{\pgfxy(2.25,3.55)}{\pgfbox[center,center]{$-7$}}
\pgfputat{\pgfxy(3,3.55)}{\pgfbox[center,center]{$-6$}}
\pgfputat{\pgfxy(3.75,3.55)}{\pgfbox[center,center]{$-5$}}
\pgfputat{\pgfxy(4.5,3.55)}{\pgfbox[center,center]{$-4$}}
\pgfputat{\pgfxy(5.25,3.55)}{\pgfbox[center,center]{$-3$}}
\pgfputat{\pgfxy(6,3.55)}{\pgfbox[center,center]{$-2$}}
\pgfputat{\pgfxy(6.75,3.55)}{\pgfbox[center,center]{$-1$}}
\pgfputat{\pgfxy(7.5,3.55)}{\pgfbox[center,center]{$0$}}
\pgfputat{\pgfxy(8.25,3.55)}{\pgfbox[center,center]{$1$}}
\pgfputat{\pgfxy(9,3.55)}{\pgfbox[center,center]{$2$}}
\pgfputat{\pgfxy(9.75,3.55)}{\pgfbox[center,center]{$3$}}
\pgfputat{\pgfxy(10.5,3.55)}{\pgfbox[center,center]{$4$}}
\pgfputat{\pgfxy(11.25,3.55)}{\pgfbox[center,center]{$5$}}
\pgfputat{\pgfxy(12,3.55)}{\pgfbox[center,center]{$6$}}
\pgfputat{\pgfxy(12.75,3.55)}{\pgfbox[center,center]{$7$}}
\pgfputat{\pgfxy(13.5,3.55)}{\pgfbox[center,center]{$\cdots$}}
\pgfputat{\pgfxy(4.25,2.9)}{\pgfbox[center,center]{(undefined for $n<0$)}}
\pgfputat{\pgfxy(7.5,2.9)}{\pgfbox[center,center]{$3$}}
\pgfputat{\pgfxy(8.25,2.9)}{\pgfbox[center,center]{$4$}}
\pgfputat{\pgfxy(9,2.9)}{\pgfbox[center,center]{$5$}}
\pgfputat{\pgfxy(9.75,2.9)}{\pgfbox[center,center]{$6$}}
\pgfputat{\pgfxy(10.5,2.9)}{\pgfbox[center,center]{$7$}}
\pgfputat{\pgfxy(11.25,2.9)}{\pgfbox[center,center]{$8$}}
\pgfputat{\pgfxy(12,2.9)}{\pgfbox[center,center]{$9$}}
\pgfputat{\pgfxy(12.75,2.9)}{\pgfbox[center,center]{$10$}}
\pgfputat{\pgfxy(13.5,2.9)}{\pgfbox[center,center]{$\cdots$}}
\pgfputat{\pgfxy(4.25,2.25)}{\pgfbox[center,center]{(undefined for $n<0$)}}
\pgfputat{\pgfxy(7.5,2.25)}{\pgfbox[center,center]{$3$}}
\pgfputat{\pgfxy(8.25,2.25)}{\pgfbox[center,center]{$4$}}
\pgfputat{\pgfxy(9,2.25)}{\pgfbox[center,center]{$5$}}
\pgfputat{\pgfxy(9.75,2.25)}{\pgfbox[center,center]{$6$}}
\pgfputat{\pgfxy(10.5,2.25)}{\pgfbox[center,center]{$3$}}
\pgfputat{\pgfxy(11.25,2.25)}{\pgfbox[center,center]{$7$}}
\pgfputat{\pgfxy(12,2.25)}{\pgfbox[center,center]{$4$}}
\pgfputat{\pgfxy(12.75,2.25)}{\pgfbox[center,center]{$8$}}
\pgfputat{\pgfxy(13.5,2.25)}{\pgfbox[center,center]{$\cdots$}}
\pgfputat{\pgfxy(1.5,1.6)}{\pgfbox[center,center]{$\cdots$}}
\pgfputat{\pgfxy(4.5,1.6)}{\pgfbox[center,center]{$3$}}
\pgfputat{\pgfxy(7.5,1.6)}{\pgfbox[center,center]{$3$}}
\pgfputat{\pgfxy(10.5,1.6)}{\pgfbox[center,center]{$3$}}
\pgfputat{\pgfxy(13.5,1.6)}{\pgfbox[center,center]{$\cdots$}}
\pgfxyline(2.1,1.5)(2.4,1.5)
\pgfxyline(2.85,1.5)(3.15,1.5)
\pgfxyline(3.6,1.5)(3.9,1.5)
\pgfxyline(5.1,1.5)(5.4,1.5)
\pgfxyline(5.85,1.5)(6.15,1.5)
\pgfxyline(6.6,1.5)(6.9,1.5)
\pgfxyline(8.1,1.5)(8.4,1.5)
\pgfxyline(8.85,1.5)(9.15,1.5)
\pgfxyline(9.6,1.5)(9.9,1.5)
\pgfxyline(11.1,1.5)(11.4,1.5)
\pgfxyline(11.85,1.5)(12.15,1.5)
\pgfxyline(12.6,1.5)(12.9,1.5)
\pgfputat{\pgfxy(1.5,.95)}{\pgfbox[center,center]{$\cdots$}}
\pgfputat{\pgfxy(3.75,.95)}{\pgfbox[center,center]{$4$}}
\pgfputat{\pgfxy(4.5,.95)}{\pgfbox[center,center]{$3$}}
\pgfputat{\pgfxy(7.5,.95)}{\pgfbox[center,center]{$3$}}
\pgfputat{\pgfxy(8.25,.95)}{\pgfbox[center,center]{$4$}}
\pgfputat{\pgfxy(10.5,.95)}{\pgfbox[center,center]{$3$}}
\pgfputat{\pgfxy(12,.95)}{\pgfbox[center,center]{$4$}}
\pgfputat{\pgfxy(13.5,.95)}{\pgfbox[center,center]{$\cdots$}}
\pgfxyline(2.1,.85)(2.4,.85)
\pgfxyline(2.85,.85)(3.15,.85)
\pgfxyline(5.1,.85)(5.4,.85)
\pgfxyline(5.85,.85)(6.15,.85)
\pgfxyline(6.6,.85)(6.9,.85)
\pgfxyline(8.85,.85)(9.15,.85)
\pgfxyline(9.6,.85)(9.9,.85)
\pgfxyline(11.1,.85)(11.4,.85)
\pgfxyline(12.6,.85)(12.9,.85)
\pgfputat{\pgfxy(1.5,.3)}{\pgfbox[center,center]{$\cdots$}}
\pgfputat{\pgfxy(3,.3)}{\pgfbox[center,center]{$5$}}
\pgfputat{\pgfxy(3.75,.3)}{\pgfbox[center,center]{$4$}}
\pgfputat{\pgfxy(4.5,.3)}{\pgfbox[center,center]{$3$}}
\pgfputat{\pgfxy(7.5,.3)}{\pgfbox[center,center]{$3$}}
\pgfputat{\pgfxy(8.25,.3)}{\pgfbox[center,center]{$4$}}
\pgfputat{\pgfxy(9,.3)}{\pgfbox[center,center]{$5$}}
\pgfputat{\pgfxy(10.5,.3)}{\pgfbox[center,center]{$3$}}
\pgfputat{\pgfxy(12,.3)}{\pgfbox[center,center]{$4$}}
\pgfputat{\pgfxy(13.5,.3)}{\pgfbox[center,center]{$\cdots$}}
\pgfxyline(2.1,.2)(2.4,.2)
\pgfxyline(5.1,.2)(5.4,.2)
\pgfxyline(5.85,.2)(6.15,.2)
\pgfxyline(6.6,.2)(6.9,.2)
\pgfxyline(9.6,.2)(9.9,.2)
\pgfxyline(11.1,.2)(11.4,.2)
\pgfxyline(12.6,.2)(12.9,.2)
\end{pgftranslate}
\end{pgfpicture}
\end{center}
\caption{Sequence, placement sequence, and partial placement sequences.\label{tab_pps}}
\end{table}

Periodicity of partial placement sequences plays an important role in our discussion of uniform recurrence in Section \ref{section_uniform}.  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 $\ZZ$.  The empty doubly infinite sequence $P_{-1}(X)=(\ldots,\underline{\hspace*{.3cm}},\underline{\hspace*{.3cm}},\underline{\hspace*{.3cm}},\ldots)$ 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,\ldots,n+3,\ldots)$, 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}\supset G_0\supset G_1\supset\ldots$ of subgroups.  The intersection $\bigcap_{m=-1}^\infty G_m$ is isomorphic to $\ZZ_2$, generated by the reflection across $-2$ noted above.

\section{Uniform recurrence}
\label{section_uniform}

A sequence is called {\it  recurrent} if every block $B$ of consecutive terms in the sequence recurs infinitely often.  Theorem \ref{thm_inf} establishes a restricted form of recurrence that applies to blocks of size $1$ in certain throwback sequences.  A stronger property is {\it 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 \ref{cor_nonzero}.  Theorem \ref{thm_rec} below establishes uniform recurrence for throwback sequences of increasing sequences of positive integers in general.  

To set up the proof of Theorem \ref{thm_rec}, 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 {\it block} $B$ in such a partially defined sequence to be the ordered contents of a finite number of consecutive index positions, where the {\it 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 {\it 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,\underline{\hspace*{.3cm}},$ and $\underline{\hspace*{.3cm}}$ beginning at position $0$ in the partial placement sequence $P_1(X)$ of the sequence $X=(3,4,5,\ldots,n+3,\ldots)$ is equal to the block with the same ordered contents beginning at position $16$.  We denote this block by $(3,4,\underline{\hspace*{.3cm}},\underline{\hspace*{.3cm}})$ regardless of its starting position, and similarly for other blocks.

We define the {\it past} $B^-$ of a block $B$ to be the ordered contents of all index positions preceding the initial position of $B$.  We define the {\it future} $B^+$ of $B$ to be the ordered contents of all index positions succeeding the terminal position of $B$.  A {\it complete block} in the $n$th 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,\ldots,x_n$ from $X$ whose copies are used to construct $P_n(X)$.  For a block $B$ in $P_n(X)$, the {\it 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 {\it direct future} $B_1^+$ of $B$ is defined to be the minimal complete block whose initial position directly succeeds the terminal position $B$.  Figure \ref{fig_blocks} shows an incomplete block $B=(3,5,\underline{\hspace*{.3cm}})$ in the partial placement sequence $P_2(X)$ of the sequence $X=(3,4,5,\ldots,n+3,\ldots)$,  together with its direct past $B_1^-$ and direct future $B_1^+$. 

\begin{figure}[h]
\begin{center}
\begin{pgfpicture}{0cm}{0cm}{14cm}{1.5cm}
\begin{pgftranslate}{\pgfpoint{0cm}{-.2cm}}
\pgfputat{\pgfxy(0,.3)}{\pgfbox[center,center]{$\cdots$}}
\pgfxyline(.35,.2)(.65,.2)
\pgfputat{\pgfxy(1,.3)}{\pgfbox[center,center]{$5$}}
\pgfputat{\pgfxy(1.5,.3)}{\pgfbox[center,center]{$4$}}
\pgfputat{\pgfxy(2,.3)}{\pgfbox[center,center]{$3$}}
\pgfxyline(2.35,.2)(2.65,.2)
\pgfxyline(2.85,.2)(3.15,.2)
\pgfxyline(3.35,.2)(3.65,.2)
\pgfputat{\pgfxy(4,.3)}{\pgfbox[center,center]{$3$}}
\pgfputat{\pgfxy(4.5,.3)}{\pgfbox[center,center]{$4$}}
\pgfputat{\pgfxy(5,.3)}{\pgfbox[center,center]{$5$}}
\pgfxyline(5.35,.2)(5.65,.2)
\pgfputat{\pgfxy(6,.3)}{\pgfbox[center,center]{$3$}}
\pgfxyline(6.35,.2)(6.65,.2)
\pgfputat{\pgfxy(7,.3)}{\pgfbox[center,center]{$4$}}
\pgfxyline(7.35,.2)(7.65,.2)
\pgfputat{\pgfxy(8,.3)}{\pgfbox[center,center]{$3$}}
\pgfputat{\pgfxy(8.5,.3)}{\pgfbox[center,center]{$5$}}
\pgfxyline(8.85,.2)(9.15,.2)
\pgfputat{\pgfxy(9.5,.3)}{\pgfbox[center,center]{$4$}}
\pgfputat{\pgfxy(10,.3)}{\pgfbox[center,center]{$3$}}
\pgfxyline(10.35,.2)(10.65,.2)
\pgfxyline(10.85,.2)(11.15,.2)
\pgfputat{\pgfxy(11.5,.3)}{\pgfbox[center,center]{$5$}}
\pgfputat{\pgfxy(12,.3)}{\pgfbox[center,center]{$3$}}
\pgfputat{\pgfxy(12.5,.3)}{\pgfbox[center,center]{$4$}}
\pgfxyline(12.85,.2)(13.15,.2)
\pgfputat{\pgfxy(13.5,.3)}{\pgfbox[center,center]{$\cdots$}}
\pgfxyline(4.8,0)(7.7,0)
\pgfxyline(7.7,0)(7.7,.6)
\pgfxyline(7.7,.6)(4.8,.6)
\pgfxyline(4.8,.6)(4.8,0)
\pgfxyline(7.8,0)(9.2,0)
\pgfxyline(9.2,0)(9.2,.6)
\pgfxyline(9.2,.6)(7.8,.6)
\pgfxyline(7.8,.6)(7.8,0)
\pgfxyline(9.3,0)(11.7,0)
\pgfxyline(11.7,0)(11.7,.6)
\pgfxyline(11.7,.6)(9.3,.6)
\pgfxyline(9.3,.6)(9.3,0)
\pgfputat{\pgfxy(4,1.25)}{\pgfbox[center,center]{$n=0$}}
\begin{pgfscope}
\pgfsetarrowsend{Triangle[scale=1.5pt]}
\pgfxyline(4,1.05)(4,.6)
\end{pgfscope}
\pgfputat{\pgfxy(6.25,1.25)}{\pgfbox[center,center]{$B_1^-$}}
\pgfputat{\pgfxy(8.5,1.25)}{\pgfbox[center,center]{$B$}}
\pgfputat{\pgfxy(10.75,1.25)}{\pgfbox[center,center]{$B_1^+$}}
\end{pgftranslate}
\end{pgfpicture}
\end{center}
\caption{A block $B$ in the partial placement sequence $P_2(X)$ of the sequence $X=(3,4,5,\ldots,n+3,\ldots)$, together with its direct past $B_1^-$ and direct future $B_1^+$.\label{fig_blocks}}
\label{block_past_future}
\end{figure}

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 \ref{block_past_future} 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 {\it 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\in\ZZ$ 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 \eqref{equ_bound}, so only a finite number of minimal complete blocks exist, since the number of possible configurations of copies of $x_0,\ldots,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 
\begin{equation}\label{equ_min_blocks}\prod_{k=0}^n(x_k-k+1).
\end{equation}
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,\ldots,n+3,\ldots)$, 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 \eqref{equ_min_blocks} can be sharp in some cases.  Theorem \ref{thm_div} 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,\ldots)$ or $(3,6,\ldots)$ or $(4,6,\ldots)$ produce partial placement sequences with fewer than the maximum possible number of minimal complete blocks given by Equation \eqref{equ_min_blocks}. However, the mere fact that the number of such blocks is finite is sufficient for the proof of the following lemma:

\begin{lemma}\label{lem_period} The partial placement sequence $P_n(X)$ of an increasing sequence of positive integers $X$ is periodic. 
\end{lemma}
\begin{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 \eqref{equ_bound}. Next, construct a sequence of disjoint minimal complete blocks $(B_m)_{m=1}^\infty$, 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. 
\end{proof}

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 {\it eventual} periodicity of blocks.  Theorem \ref{thm_rec} 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. 
 
\begin{theorem}\label{thm_rec} The throwback sequence $T(X)$ of an increasing sequence of positive integers $X$ is uniformly recurrent.  
\end{theorem}

\begin{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 \ref{lem_period}, $B$ appears periodically in $P_n(X)$, and hence also in $T(X)$.  
\end{proof}

While the period arising from Lemma \ref{lem_period} 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,\ldots,n+3,\ldots)$ illustrated in Figure \ref{block_past_future} occurs at position $8$ with direct future  $(\underline{\hspace*{.3cm}},4,3,\underline{\hspace*{.3cm}},\underline{\hspace*{.3cm}},5)$, at position $36$ with direct future  $(4,\underline{\hspace*{.3cm}},3,\underline{\hspace*{.3cm}},\underline{\hspace*{.3cm}},4,3,5)$, and at position $44$ with direct future  $(\underline{\hspace*{.3cm}},\underline{\hspace*{.3cm}},3,4,\underline{\hspace*{.3cm}},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,\ldots,x_n$ that result from repeated application of the throwback operation $\tau$ to $X$.  This relationship is expected because the same counting argument leading to Equation \eqref{equ_min_blocks} 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 $\tau$ {\it sorts} and/or {\it mixes} the terms of $X$, the subject of Theorem \ref{thm_div} below.   For example, the minimal complete block $(4,3,\underline{\hspace*{.3cm}},\underline{\hspace*{.3cm}},5)$ beginning at index position $11$ in the partial placement sequence $P_2(X)$ of $X=(3,4,5,\ldots,n+3,\ldots)$ illustrated in Figure \ref{block_past_future}, indicates that the sequence $\tau^{11}(X)$ begins $(4,3,*,*,5,\ldots)$, 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 $\tau^{11}(X)$ are therefore $1$, $0$, and $4$, respectively.  Generalizing this example, we define a {\it configuration} $C$ of the terms $x_0,\ldots,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 $\tau^{k}(X)$.  Note that $\tau$ may be applied unambiguously to such a configuration since throwing back a term larger than $x_n$ moves all the terms $x_0,\ldots,x_n$ one place to the left. We now have the following lemma:

\begin{lemma}\label{lem_bij} 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,\ldots,x_n$ appearing in the sequences $\tau^{k
}(X)$ for nonnegative integers $k$. 
\end{lemma}

\begin{proof} Given a configuration of $x_0,\ldots,x_n$ in $\tau^k(X)$ for some $k\ge0$, it is clear that additional applications of $\tau$ 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,\ldots,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 $\tau$ 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$.
\end{proof}

\section{Examples with code}\label{section_code}

We now illustrate how some of these ideas may be explored numerically, using for illustration the increasing sequence $X=(1,3,4,5,\dots,n+3,\ldots)$, 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:\\

\noindent\texttt{X=[1]\\
for i in range(0,100):\\
\hspace*{.5cm}X.append(i+3)\\
Y=X; T=[]; loops=10000\\
for l in range(0,loops):\\
\hspace*{.5cm}leader=Y[0]\\
\hspace*{.5cm}T.append(leader)\\
\hspace*{.5cm}Y.pop(0)\\
\hspace*{.5cm}Y.insert(leader,leader)\\
print(T[0:20])}\\

The output is\\

\texttt{[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)$:\\

\noindent\texttt{M=max(T)\\
counter\_vector=np.zeros(M); freq\_vector=np.zeros(M)\\
for i in range(0,M):\\
\hspace*{.5cm}for j in range(0,len(T)):\\
\hspace*{1cm}if T[j]==i:\\
\hspace*{1.5cm}counter\_vector[i]+=1\\
for i in range(0,M):\\
\hspace*{.5cm}freq\_vector[i]=counter\_vector[i]/loops\\
for i in range(0,10):\\
\hspace*{.5cm}print(round(freq\_vector[i],5),end=", ")}\\

The output is\\

\texttt{0.0, 0.5, 0.0, 0.1667, 0.1111, 0.0741, 0.0494, 0.0329, 0.0220, 0.0146,}\\

\noindent 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\ge1$  from Equation \eqref{equ_freq}.  The following Python code generates the first few terms of the corresponding placement sequence $P(X)$:\\

\noindent\texttt{places=100\\
P=np.zeros(places,dtype=int)\\
max\_fill=11\\
for i in range(0,max\_fill):\\
\hspace*{.5cm}counter=0\\
\hspace*{.5cm}for j in range(0,places):\\
\hspace*{1cm}if P[j]==0:\\
\hspace*{1.5cm}if counter\%(X[i]-i+1)==0:\\
\hspace*{2cm}P[j]=X[i]\\
 \hspace*{1.5cm}counter+=1\\
print(P[0:20])}\\

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

\texttt{[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)$:\\

\noindent\texttt{recur\_list=[]\\
gaps\_list=[]\\
for i in range(0,300):\\
\hspace*{.5cm}if T[i]==1:\\
\hspace*{1cm}if T[i+1]==3:\\
\hspace*{1.5cm}if T[i+2]==1:\\
\hspace*{2cm}if T[i+3]==4:\\
\hspace*{2.5cm}recur\_list.append(i)\\
for k in range(0,len(recur\_list)-1):\\
\hspace*{.5cm}gaps\_list.append(recur\_list[k+1]-recur\_list[k])\\
print(gaps\_list)}\\

The output is\\

\texttt{[18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18],}\\

\noindent which suggests that this block recurs periodically with gaps of size $18$, the largest possible size in view of Equation \eqref{equ_min_blocks}.

\section{Discussion and historical notes}\label{section_discussion}

The throwback sequence of the sequence $\ZZ^+=(1,2,3,\ldots)$ of all positive integers is the familiar ruler function \seqnum{A001511} \cite{OEIS,Erickson}, 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 \cite{Gray,Herter}, 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 \cite{KozarPage} 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 \seqnum{A087165}, \seqnum{A155167}, \seqnum{A354223}, and \seqnum{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 \seqnum{A357081} (the throwback sequence of $X=(3,4,5,\ldots,n+3,\ldots)$) and \seqnum{A001511} (the ruler function, or throwback sequence of $\ZZ^+$) are uniformly recurrent by Theorem \ref{thm_rec}, but the precise behavior of blocks seems to be much simpler in the latter sequence. Each block $B$ in \seqnum{A001511} seems to recur with gaps of size $2^n$, where $n$ is the largest element in the block.  An easy application of Theorem \ref{thm_div} below shows that this is indeed the case.  By contrast, blocks in \seqnum{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 \eqref{equ_min_blocks}. More generally, it appears to be true that $\tau^{4^n}$ fixes the first $n$ terms of the sequence $(3,4,5,\ldots,n+3,\ldots)$.  This observation, also established by Theorem \ref{thm_div}, 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 $\tau$ to an arbitrary sequence of distinct positive integers $X$ may be regarded as an {\it 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 {\it limiting average positions} of terms, analogous to the limiting frequencies established by Theorem \ref{thm_freq}.  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 $\tau$. 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 \ref{thm_inf} and \ref{thm_rec} could be generalized to describe the {\it 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 $\tau$ constitutes a {\it perfect mixing process,} meaning that the first $n$ terms $x_0,\ldots,x_n$ of $X$ pass through every possible configuration before returning to their initial order.  Theorem \ref{thm_div} establishes that sequences of consecutive positive integers satisfy this property.  For example, for the sequence $X=(3,4,5,\ldots,n+3,\ldots)$, 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 \eqref{equ_min_blocks}, since such blocks and configurations correspond bijectively by Lemma \ref{lem_bij}.  Figure \ref{fig_perfect_mixing} demonstrates how all these configurations indeed result from repeated application of $\tau$, where the symbol $*$ is used as shorthand for any term greater than $4$, and where dots indicating continuation are suppressed for legibility. 

\begin{figure}[h]
\begin{center}
\begin{align*}
 \tau^0: 3,4,*,*,* && \tau^4: 3,*,4,*,* && \tau^8: 3,*,*,4,* && \tau^{12}: 3,*,*,*,4\\        
 \tau^1: 4,*,*,3,* && \tau^5: *,4,*,3,* && \tau^9: *,*,4,3,* && \tau^{13}: *,*,*,3,4\\
 \tau^2: *,*,3,*,4 && \tau^6: 4,*,3,*,* && \tau^{10}: *,4,3,*,* && \tau^{14}:  *,*,3,4,*\\
 \tau^3: *,3,*,4,* && \tau^7: *,3,*,*,4 && \tau^{11}: 4,3,*,*,* && \tau^{15}:*,3,4,*,*
\end{align*}
\end{center}
\caption{Perfect mixing: every possible configuration of $3$ and $4$ occurs under repeated application of $\tau$ to  $X=(3,4,5,\ldots,n+3,\ldots)$.}
\label{fig_perfect_mixing}
\end{figure}


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 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,\ldots,n+3,\ldots)$, the $16$ minimal complete blocks appear in the overlapping order 
\[(3,4),(4,\underline{\hspace*{.3cm}},\underline{\hspace*{.3cm}},3),(\underline{\hspace*{.3cm}},\underline{\hspace*{.3cm}},3,\underline{\hspace*{.3cm}},4),(\underline{\hspace*{.3cm}},3,\underline{\hspace*{.3cm}},4),(3,\underline{\hspace*{.3cm}},4),\dots\]
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 \ref{lem_period}, 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 \ref{thm_freq}.  Equating these two results for the  sequence $X=(3,4,5,\ldots,n+3,\ldots)$ leads to the equation 
\begin{equation}\label{equ_div}
\frac{\tn{minimal complete blocks starting with $x$}}{\tn{total minimal complete blocks}}=\frac{3^{x-3}}{4^{x-2}},
\end{equation}
where the right hand side comes from Theorem \ref{thm_freq}, and the denominator is the upper bound for the maximum possible number of minimal complete blocks given by Equation \eqref{equ_min_blocks}. 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,\ldots,x_n$ by Lemma \ref{lem_bij}, perfect mixing occurs.  We can readily generalize this argument to apply to sequences of consecutive positive integers. 

\begin{theorem}\label{thm_div}
Let $X$ be a sequence of consecutive positive integers beginning with some positive integer $m$.  Then repeated application of the throwback operation $\tau$ is a perfect mixing process in the sense that the first $n+1$ terms $m,m+1,\ldots,m+n$ of $X$ pass through every possible configuration before returning to their original order with the $(m+1)^{n+1}$th application of $\tau$.
\end{theorem}
\begin{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 \ref{thm_freq}. 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 \eqref{equ_min_blocks}.  Since this number is also equal to the maximum possible number of configurations of the first $n$ terms of $X$ by Lemma \ref{lem_bij}, every possible configuration appears. 
\end{proof}

For example, $2^{n+1}$ applications of $\tau$ 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,\ldots,n+2,\ldots)$ in Section \ref{section_code} suggests perfect mixing for the terms $1,3,$ and $4$ in this sequence.  However, Theorem \ref{thm_freq} does not seem to provide a straightforward argument for why every possible configuration should occur in this case; it allows for a period of {\it 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,\ldots)$ or $(3,6,\ldots)$ or $(4,6,\ldots)$ in the discussion following Equation \eqref{equ_min_blocks}.  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 \eqref{equ_min_blocks}. Hence, characterizing which sequences exhibit perfect mixing remains mostly open, although further divisibility arguments involving Theorem \ref{thm_div} 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 {\it could have been obtained} by throwing back the initial term of another sequence. The answer is straightforward: a sequence $X$ can be $\tau(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,\ldots,n+3,\ldots)$ cannot be obtained by applying $\tau$ 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 \ref{tab_pps}.  Admitting transfinite ordinals to the picture could alter such considerations; for example, the sequence $(3,4,5,\ldots,n+3,\ldots,\omega)$ could be regarded as $\tau(\omega,3,4,5,\ldots,n+3,\ldots)$, where $\omega$ is the smallest transfinite ordinal.  We also note that inverting $\tau$ is generally non-unique; for example, a sequence beginning $(7,5,1,3,4,8,\ldots)$ could be the throwback sequence of a sequence beginning either $(3,7,5,1,4,8,\ldots)$ or $(4,7,5,1,3,8,\ldots)$. The extent of non-uniqueness 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 {\it Popular Computing} article from 1977 \cite{PC}. Photocopied images of this article appear on the OEIS page for \seqnum{A357081} \cite{OEIS}.  There seem to have been several distinct publications named {\it Popular Computing} around this time \cite{KozarPage}.  The one of present interest was initiated in 1973 by Gruenberger \cite{Standford,TechArch}, 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 {\it 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.

\section{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.

\begin{thebibliography}{9}

\bibitem{PC}  F. Gruenberger, Coding fun: rearranging all the numbers, {\it Popular Computing} {\bf 5} (1977), 55.

\bibitem{OEIS} N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2024. 

\bibitem{KozarPage}  A. M. Kozar, Throwback all of your number sequences, 2022. Available at\\ \url{http://www.anthonykozar.net/posts/2022/09/05/}.
 
\bibitem{Erickson} 
 A. Erickson, A. Isgur, B. W. Jackson, F. Ruskey,  and S. M. Tanny,
Nested recurrence relations with Conolly-like solutions, {\it SIAM J. Discrete Math.} {\bf 26} (2012), 206--238. 

\bibitem{Gray} F. Gray, Pulse code communication, Bell Telephone Laboratories, Inc., U.S. patent 2,632,058, serial number 785697, 1947. 

\bibitem{Herter} F. Herter and G. Rote, Loopless Gray code enumeration and the Tower of Bucharest, {\it Theor. Comput. Sci.} {\bf 748} (2018), 40--54. 

\bibitem{JacobsKeane} K. Jacobs and M. Keane, $0$-$1$-Sequences of Toeplitz type, {\it Z. Wahrscheinlichkeitstheorie Verw. Gebiete} {\bf 13} (1969) 123--131. 

\bibitem{Standford} Stanford Libraries SearchWorks, Popular Computing, 2024. Available at
\url{https://searchworks.stanford.edu/view/380699}.

\bibitem{TechArch}  Technical Archive, Fred Gruenberger and the ``original'' Popular Computing, 2024. Available at \url{https://www.techarc.com/gruenberger}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification:} Primary 11B99; Secondary 11B05, 11B85. 

\noindent \emph{Keywords: } throwback sequence, ruler function, limiting frequency, iteratively constructed sequence, uniform recurrence. 

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received July 16 2024;
revised versions received  September 5 2024;
January 7 2025; January 10 2025; September 11 2025.
Published in {\it Journal of Integer Sequences},
September 14 2025.

\bigskip
\hrule
\bigskip

\noindent
Return to \href{https://cs.uwaterloo.ca/journals/JIS/}{Journal of Integer Sequences home page}.
\vskip .1in

\end{document}
