\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage{amsthm} \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{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Generalizing the Conway-Hofstadter \$10,000 Sequence} \vskip 1cm \large John A.\ Pelesko\\ Department of Mathematical Sciences\\ University of Delaware \\ Newark, DE 19716\\ USA \\ \href{mailto:pelesko@math.udel.edu}{\tt pelesko@math.udel.edu} \\ \end{center} \vskip .2 in \begin{abstract} We introduce a generalization of the Conway-Hofstadter \$10,000 sequence. The sequences introduced, called \emph{k-sequences}, preserve the Conway-Hofstadter-Fibonacci-like structure of forming terms in the sequence by adding together two previous terms, equidistant from the start and end of the sequence. We examine some particular $k$-sequences, investigate relationships to known integer sequences, establish some properties which hold for all $k$, and show how to solve many of the defining nonlinear recursions by examining related underlying sequences termed \emph{clock} sequences. \end{abstract} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}{Proposition}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{lemma}{Lemma}[section] %\documentclass[12pt]{article} %\usepackage{amssymb,amsthm,amssymb} %\usepackage[first,bottomafter]{draftcopy} %\usepackage{epsfig} %\renewcommand{\baselinestretch}{1.2} %This is the command that spaces the manuscript for easy reading %These are abbreviations of J.A. Pelesko \newcommand{\eqnref}[1]{\ref{eq:#1}} \newcommand{\secref}[1]{section~\ref{sec:#1}} \newcommand{\figref}[1]{Figure~\ref{fig:#1}} \newcommand{\tabref}[1]{Table~\ref{tab:#1}} \newcommand{\be}{\begin{equation}} \newcommand{\ee}{\end{equation}} \newcommand{\ra}{\rightarrow} \newcommand{\bea}{\begin{eqnarray}} \newcommand{\eea}{\end{eqnarray}} \newcommand{\dt}{\delta t} \newcommand{\beas}{\begin{eqnarray*}} \newcommand{\eeas}{\end{eqnarray*}} \newcommand{\xh}{\hat{x}} \newcommand{\expand}[2]{#1(#2) \sim #1_0(#2) + \epsilon #1_1(#2) + \epsilon^2 #1_2(#2) + \cdots} \newcommand{\R}{\mathbf{R}} \newcommand{\norm}[1]{|| #1 ||_{\infty}} %\newtheorem{theorem}{Theorem} \newtheorem{definition}{Definition} \newtheorem{prop}{Proposition} \newcommand\around[1]{\ensuremath{\mathbin{\settowidth{\dimen7}{\mbox{$\bigcirc$}}% \makebox[0pt][l]{$\bigcirc$}\makebox[\dimen7]{#1}}}} %\begin{document} %\thispagestyle{empty} \section{Introduction} In a talk at AT\&T Bell Labs \cite{conwaytalk} in 1988, J.H.\ Conway introduced the sequence (A004001 in the On-Line Encyclopedia of Integer Sequences) \beas 1,1,2,2,3,4,4,4,5,6,7,7,8,8,8,8,9,\ldots \eeas defined by the recursion \be c(n)=c(c(n-1))+c(n-c(n-1)), \label{eq:c1} \ee with initial conditions $c(1)=c(2)=1$. Conway had proven that $c(n)/n \rightarrow 1/2$, but was unable to establish the rate of convergence. Somewhat overestimating the difficulty of the question he offered a prize of \$10,000 to the first person who could. The challenge was answered by C.L.\ Mallows \cite{Mallows} shortly thereafter. Mallows not only established the rate of convergence, but uncovered additional structure in the sequence as well. The exchange caught the attention of the popular press inspiring an entertaining article in the {\it New York Times} \cite{NYT}. The popularization of A004001 generated by this exchange also led to the study of Kubo and Vakil \cite{Kubo} where much of the combinatorial structure of the sequence was unveiled. The use of a \emph{compression operation} to characterize the sequence allowed for simple proofs of many of A004001's interesting properties. We also note that unbeknownst to Conway and Mallows the sequence had previously been introduced by Hofstadter \cite{Hofstadter} and had also appeared in the problems section of the American Mathematical Monthly \cite{Newman}. Today A004001 is known either as the ``Conway-Hofstadter \$10,000 sequence'' or as the ``Conway-Newman'' sequence. We will refer to it as the ``Conway-Hofstadter'' sequence. Many of the properties that inspired interest in (\ref{eq:c1}) are nicely enumerated by Kubo and Vakil \cite{Kubo}. For convenience of the reader we list those relevant to this paper here: \begin{enumerate} \item $c(n) \leq n$. \item $c(n)-c(n-1) = 0$ or $1$, for all $n \geq 1$. \item $c(n) \geq n/2$, with equality iff $n$ is a power of $2$ and $n \neq 1$. \item $c(n)/n \longrightarrow 1/2$ as $n \longrightarrow \infty$. \item $c(2n) \leq 2 c(n)$ for all $n$. \end{enumerate} In this paper we generalize the Conway-Hofstadter sequence. Our generalized class of sequences shows much of the structure of (\ref{eq:c1}), but also exhibits interesting new behavior. The generalization leads to new representations of old sequences and to new solvable nonlinear recursions. \section{The Generalization: \emph{k-Sequences}} In reading the work of Mallows \cite{Mallows} or Kubo and Vakil \cite{Kubo} one is immediately struck by the statements following the presentation of the first property listed above of the Conway-Hofstadter sequence. Both authors note that $c(n) \leq n$ and then go on to say ``so that $c(n)$ is well-defined by the recurrence.'' To understand this comment and to appreciate the motivation for our generalization it is worth visualizing how terms in the Conway-Hofstadter sequence are formed. Consider the first five terms of the Conway-Hofstadter sequence: \beas 1,1,2,2,3. \eeas To form the sixth term, we note that the fifth term is equal to $3$, count forward from the beginning of the sequence three terms, backwards from the end of the sequence three terms, and add the results to find $c(6)=2+2=4$. This procedure generates all terms in the sequence. Note that there is a beautiful symmetry in this construction process; in forming the $n$th term, one term from the first half of the sequence is added to a term from the second half of the sequence. These terms are always equidistant from the start and end of the sequence. The observation of Mallows or Kubo and Vakil is equivalent to noting that $c(n) \leq n$ assures that we never count past the end (or the beginning) of the sequence. Of course, if we consider clock or modular arithmetic, counting beyond the start or end of the sequence is no longer a problem. This immediately suggests our generalization. \begin{definition} We say that $\{c_k(n)\}$ is a Conway-Hofstadter-like sequence of order $k$ when defined by the recursion \be c_k(n) = c_k( k c_k(n-1) \bmod (n-1)) + c_k(n-k c_k(n-1) \bmod (n-1)) \ee with $c_k(1)=c_k(2)=1$. We also call such sequences, k-sequences, and denote them $c_k$. \end{definition} Note that this generalization preserves the symmetry of the Conway-Hofstadter sequence. That is, the only modifications to the construction process above are that the last term in the sequence in multiplied by $k$, and the count from the start and end of the sequence is done using modular arithmetic. However, in forming the $n$th term, one term from the first half of the sequence is still added to one term from the second half of the sequence; these terms are again equidistant from the start and end of the sequence. Throughout this paper, we observe the convention that a zero in modular arithmetic mod $n$ is replaced by $n$. \subsection{A Glance at Some $k$-Sequences} \label{sec:obs} Computing the first few terms of $k$-sequences for various $k$ reveals some familiar sequences hiding among the $k$'s as well as some new surprises. The observed behavior of the first fifteen $k$-sequences is summarized in the following table: \begin{table}[H] \begin{center} \begin{tabular}{|c|l|} \hline $k$-sequence & First twenty terms \\ \hline \hline $c_1$ & 1,1,2,2,3,4,4,4,5,6,7,7,8,8,8,8,9,10,11,12 \ldots \\ \hline $c_2$ & 1,1,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11 \ldots \\ \hline $c_3$ & 1,1,2,3,4,4,5,6,6,7,8,8,9,10,10,11,12,12,13,14 \ldots \\ \hline $c_4$ & 1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10 \ldots \\ \hline $c_5$ & 1,1,2,3,3,4,4,5,6,6,7,7,8,9,9,10,10,11,12,12 \ldots \\ \hline $c_6$ & 1,1,2,3,3,4,5,5,6,7,7,8,9,9,10,11,11,12,13,13 \ldots \\ \hline $c_7$ & 1,1,2,2,3,4,4,5,6,6,7,7,8,8,9,10,11,12,11,12 \ldots \\ \hline $c_8$ & 1,1,2,3,4,4,5,6,7,7,8,9,10,10,11,12,13,13,14,15 \ldots \\ \hline $c_9$ & 1,1,2,3,3,4,5,5,6,7,7,8,9,9,10,11,11,12,13,13 \ldots \\ \hline $c_{10}$ & 1,1,2,2,3,4,4,5,5,6,7,7,8,8,9,10,10,11,11,12 \ldots \\ \hline $c_{11}$ & 1,1,2,3,4,4,5,5,6,7,8,9,9,9,10,12,12,13,13,14 \ldots \\ \hline $c_{12}$ & 1,1,2,3,4,4,5,6,7,7,8,9,10,10,11,12,13,13,14,15 \ldots \\ \hline $c_{13}$ & 1,1,2,2,3,3,4,5,6,5,6,7,7,8,9,9,10,10,11,10 \ldots \\ \hline $c_{14}$ & 1,1,2,3,3,4,4,5,6,6,7,7,8,9,10,10,10,12,12,13 \ldots \\ \hline $c_{15}$ & 1,1,2,3,4,5,5,6,6,7,9,8,9,10,11,12,12,13,14,15 \ldots \\ \hline \end{tabular} \end{center} \end{table} The sequence $c_1$ is, of course, the Conway-Hofstadter sequence. Other familiar sequences are lurking in this list. The sequence $c_4$ is the nice sequence $\lfloor (n+1)/2 \rfloor$ which is equivalent to A004526. Both $c_6$ and $c_9$ appear to follow the pattern ``one even followed by two odd'' and hence appear equivalent to A004396. The sequences $c_8$ and $c_{12}$ appear equivalent to A037915, or more simply $\lfloor (3n+4)/4 \rfloor$. These suggested equivalences require proof. We do not present such proof at this point. Rather, we will first establish some general results about the $c_k$'s, then, demonstrate a method for uncovering the hidden structure of many $c_k$'s, and finally show how to prove an equivalence suggested by the table above. We do at this point note that direct computation of various $k$-sequences highlights interesting similarities and differences between $c_1$ and other $c_k$'s. Properties (1) and (3) of $c_1$ appear to be satisfied for all $k$. Property (2) however is violated for most $c_k$'s. This is seen both through failure of monotonicity and in the ``skipping'' of integers in sequences such as $c_{11}$ and $c_{13}$. Of course, the other striking feature of the $c_k$ is the apparent new representation of some familiar sequences such as A004526 or A004396. \section{Properties of the $c_k$} Observations suggest that all $c_k$ satisfy upper and lower bounds on growth similar to the bounds on $c_1$. This is indeed true and we have \begin{prop} $c_k(n) \leq n$ for all $n \geq 1$, $k \geq 1$. \end{prop} \begin{proof} For any fixed $k$, we proceed by induction on $n$. Note that $c_k(1)=c_k(2)=1$ and $c_k(3)=2$ and hence $c_k(n) \leq n$ for $1 \leq n \leq 3$. Now, assume $c_k(j) \leq j$ for all $j$ satisfying $1 \leq j \leq n$ and consider $c_k(n+1)$. We have \beas c_k(n+1) = c_k(k c_k(n) \bmod n) + c_k(n+1 - k c_k(n) \bmod n).\eeas Let $j=k c_k(n) \bmod n$ and observe that $1 \leq j \leq n$. Hence \beas c_k(n+1) = c_k(j) + c_k(n+1-j) \leq j+n+1-j = n+1 \eeas and \beas c_k(n+1) \leq n+1 \eeas as desired.\end{proof} A similar argument yields the lower bound \begin{prop} $c_k(n) \geq n/2$ for all $n \geq 1$, $k \geq 1$. \end{prop} A key difference between $c_1$ and a general $c_k$ is that property (2) need not hold. This allows a particular $c_k$ to be non-monotone and to ``skip'' integers. For example, $c_7(19)-c_7(18)=-1$ demonstrating the non-monotone property while $c_{11}$ does not contain the number $11$, as we shall soon see. The bounds above immediately provide a means to prove that integers can indeed be skipped. We have \begin{prop} Let $m>0$ and suppose $m$ does not appear in the first $N$ terms of $c_k(n)$ where $N > 2m$, then $m$ never appears in $c_k(n)$. \end{prop} \begin{proof} $ c_k(N) \geq \frac{N}{2} > m. $ \end{proof} Notice that this proposition, along with computation of the first $23$ terms of $c_{11}$ establishes that $c_{11}$ is indeed ``missing'' $11$. We can also easily bound the maximum number of occurrences of a particular integer in the sequence $c_k$. \begin{prop} Let $f_k(m)$ denote the total number of occurrences of $m$ in the sequence $c_k$. Then, $f_k(m) \leq m+1$ for all $k$ and $m$. \end{prop} \begin{proof} By our lower bound on $c_k$ we have $c_k(2m) \geq m$. By our upper bound we have $c_k(m) \leq m$. Hence $m$ can only appear amongst the $m+1$ terms $c_m, c_{m+1},\ldots c_{2m}$. \end{proof} Another natural question is whether or not $c_k$ and $c_j$ can be ``equivalent.'' We consider two notions of equivalence. \begin{definition} We say that $c_k$ and $c_j$ are numerically equivalent to order $N$ iff $c_k(n)=c_j(n)$ for all $n$ satisfying $1 \leq n \leq N$. We say that $c_k$ and $c_j$ are structurally equivalent to order $N$ iff $k c_k(n) \bmod n = j c_j(n) \bmod n$ for all $n$ satisfying $3 \leq n \leq N$. \end{definition} Structural equivalence tracks the process of forming a $k$-sequence. It decides whether or not two $k$-sequences were formed by adding together terms located at the same point in each sequence. Structural equivalence clearly implies numerical equivalence. The converse is not true. It is possible for two sequences to be numerically equivalent, but not structurally equivalent. Of the two types of equivalence, we consider structural equivalence to be fundamental. We can compute the set of all $k$-sequences structurally equivalent to a given sequence, $c_j$, by solving a system of linear congruences. For example, consider $c_2$, which begins $\{1,1\}$. Since $2 \equiv 0$ (mod $2$) we may find all $k$-sequences structurally equivalent to order $2$ by solving the congruence $k \equiv 0$ (mod $2$). The set of even integers satisfies this congruence. At the next step, $c_2$ is $\{1,1,2\}$, and since $4 \equiv 1$ (mod $3$) we must solve the congruence $2k \equiv 1$ (mod $3$). The solutions to this are numbers in the arithmetic progression $2,5,8,\ldots$. Hence the $k$-sequences structurally equivalent to $c_2$ at order $3$ are those in the progression with steps of length $2 \times 3$, i.e., $k = 2,8,14,\ldots$. Replacing $2$ with $j$ and generalizing the argument above we may show \begin{prop} Given any $k,N$, there exists a $j \neq k$, such that $c_k$ and $c_j$ are structurally equivalent to order $N$. Further, if $j$ is the smallest such integer, $j \rightarrow \infty$ as $N \rightarrow \infty$. \end{prop} Notice that this proposition implies that no two $k$-sequences are structurally equivalent of infinite order. In this sense, the $k$-sequences are distinct. As mentioned above, two $k$-sequences may be numerically equivalent, but not structurally equivalent. Numerical investigation suggests that numerical equivalence is infrequent. \section{The Beat of the $c_k$'s} The structure implicit in the notion of structural equivalence can also shed light on the behavior of particular $k$-sequences. The underlying structure of a given $k$-sequence, that is the sequence of terms used to create $c_k$, is tracked by the associated \emph{clock} sequence. \begin{definition} Associated with each $k$-sequence, $c_k$, we define a clock sequence, denoted $t_k$, as the sequence satisfying \beas t_k(n) = \min (kc_k(n-1) \bmod (n-1), n-k c_k(n-1) \bmod(n-1)) \eeas for $n \geq 3$ with $t_k(1)=t_k(2)=1$. \end{definition} Note that the clock, $t_k(n)$, starting at $n=3$, tracks the term from the \emph{lower} half of the sequence of length $n-1$ that is used to compute the $n$th term. In terms of its clock, a $k$-sequence can be written \beas c_k(n) = c_k(t_k(n-1)) + c_k(n-t_k(n-1)), \eeas again where $n \geq 3$. A clock sequence becomes particularly useful when it become \emph{periodic}. For example, consider the growth of $c_2$. We circle the terms at level $n-1$ used to create the new term at level $n$: \begin{center} \begin{tabular}{|c|} \hline \around{$1$}, \around{$1$} \\ \around{$1$},$1$,\around{$2$} \\ $1$,\around{$1$},\around{$2$},$3$ \\ \around{$1$},$1$,$2$,$3$,\around{$3$} \\ $1$,\around{$1$},$2$,$3$,\around{$3$},$4$ \\ \around{$1$},$1$,$2$,$3$,$3$,$4$,\around{$4$} \\ $1$,\around{$1$},$2$,$3$,$3$,$4$,\around{$4$},$5$ \\ \hline \end{tabular} \end{center} The regular visual pattern translates into periodic behavior of $t_2$. In particular, $t_2 = 1,1,1,1,2,1,2,1,2,1,2,\ldots$. If we conjecture that this pattern continues, we may extract from $t_2$ the simpler set of \emph{linear} recursions satisfied by $c_2$ \be c_2(2n) = 1 + c_2(2n-1), \ee \be c_2(2n+1) = 1 + c_2(2n-1), \ee from which the description of $c_2$ in our table and properties such as (4) and (5) of $c_1$ may easily be established. One might conjecture (wishfully) that a clock sequence that repeats itself continues to do so. Unfortunately, the clock of $c_7$ already furnishes a counterexample, repeating a portion of itself, and then wandering off into apparent aperiodic behavior. However, when a $c_k$ does behavior in a regular, if perhaps complicated, fashion, clock sequences allow us to uncover this hidden structure. To search for this structure in a given $c_k$, we can plot the phase portrait of the associated clock sequence. Some sequences can yield visually appealing lengthy periodic behavior. The phase portraits showing the ``beat'' (the clock) of $c_{16}$, $c_{260}$, and $c_{138}$ appear in Figures \ref{fig:beat16}-\ref{fig:beat138}. \begin{figure}[th] \begin{center} \epsfxsize=100mm \epsfbox{beat16.eps} \end{center} \caption{The `beat' of $c_{16}$.} \label{fig:beat16} \end{figure} \begin{figure}[th] \begin{center} \epsfxsize=100mm \epsfbox{beat260.eps} \end{center} \caption{The `beat' of $c_{260}$.} \label{fig:beat260} \end{figure} \begin{figure}[th] \begin{center} \epsfxsize=100mm \epsfbox{beat138.eps} \end{center} \caption{The `beat' of $c_{138}$.} \label{fig:beat138} \end{figure} Each of these phase portraits was drawn by computing the first ten thousand terms of the sequence and the associated clock sequence. Then, the next ten thousand terms of the associated clock sequence were plotted as points $(t_k(n),t_k(n+1))$. If the clock has become periodic by this point, revealing the underlying structure of the sequence, the phase portrait then reveals a closed orbit such as those in Figures \ref{fig:beat16}-\ref{fig:beat138}. On the other hand, if the ``beat'' is still irregular, no apparent order is discernable in the phase portrait. Once the underlying structure is revealed, we may make conjectures concerning equivalences with known sequences or conjectures about the behavior of unknown sequences. These conjectures are then often easily proved (although when the period is long, the proof is tedious). As an easy example we have \begin{prop} $c_4(n) = \lfloor \frac{n+1}{2} \rfloor$. \end{prop} \begin{proof} It is sufficient to prove that \beas c_4(n) = \lfloor \frac{n+1}{2} \rfloor. \eeas We may easily verify that this is true for $n=1$ to $n=6$. Now, assume it is true for $k = 1 \ldots n$. Consider $c_4(n+1)$. We must show \beas c_4(n+1) = \lfloor \frac{n+2}{2} \rfloor. \eeas But, \beas c_4(n+1) = c_4(4 c_4(n) \bmod n) + c_4(n+1 - 4 c_4(n) \bmod n). \eeas By hypothesis \beas c_4(n) = \lfloor \frac{n+1}{2} \rfloor, \eeas and hence \beas c_4(n+1) = c_4( 4 \lfloor \frac{n+1}{2} \rfloor \bmod n) + c_4(n+1 - 4 \lfloor \frac{n+1}{2} \rfloor \bmod n). \eeas But, $4 \lfloor \frac{n+1}{2} \rfloor \bmod n$ is $0$ if $n$ is even and $2$ if $n$ is odd. So, \beas c_4(n+1) = c_4(1) + c_4(n) = 1+ \lfloor \frac{n+1}{2} \rfloor, \eeas for $n$ even and \beas c_4(n+1) = c_4(2) + c_4(n-1) = 1 + \lfloor \frac{n}{2} \rfloor, \eeas for $n$ odd. From which it follows directly that \beas c_4(n+1) = \lfloor \frac{n+2}{2} \rfloor \eeas as desired. \end{proof} Note that we implicitly used the clock sequence in this proof. In fact, the result can be restated as a result on the periodicity of $t_4$. Randomly searching for $k$-sequences with the nice behavior of $c_2$, $c_4$ or $c_{260}$, we develop the feeling that many $k$-sequences are in fact irregular. To get a broader picture, we compute a ``bifurcation diagram'' for the $c_k$. For each $k$, we compute the first $5000$ terms, of both $c_k$ and $t_k$. Then, we compute the density of $t_k$ in the interval $[0,2500]$. Finally, we plot the negative log of this density versus $k$. Those sequences with highly ordered clocks, and hence a clear underlying structure, appear as peaks in this plot. Those with an irregular ``beat'' map roughly to zero. The bifurcation diagram for $k$ ranging from one to one-thousand appears in Figure \ref{fig:bifurc}. \begin{figure} \begin{center} \epsfxsize=100mm \epsfbox{bifurc.eps} \end{center} \caption{The bifurcation diagram for the $c_k$'s. Those $c_k$'s whose order is apparent by examining $t_k$ appear as peaks.} \label{fig:bifurc} \end{figure} Order appears to decrease with increasing $k$. Also the frequency of highly-ordered sequences appears to decrease with increasing $k$. \section{Open Questions and More Generalizations} We have just scratched the surface of $k$-sequences. Many open questions and further generalizations remain. One particularly intriguing puzzle concerns irregular sequences such as $c_7$ and $c_{13}$. Do the clocks of sequences such as $c_7$ or $c_{13}$ ever become periodic or do they always beat irregularly? Does $c_k(n)/n$ tend to a limit for these sequences? Another question concerns sequences with ``missing'' numbers such as $c_{11}$. Computation reveals that $c_{11}$ misses $11$, $29$, $33$, $37$, and $39$. Does $c_{11}$ miss infinitely many integers? What is the sequence of integers missed? Yet another less precise question concerns order. Is there a $k$-sequence that becomes irregular after a long period of regularity? (The reader may wish to examine $c_{204}$ which exhibits the opposite behavior.) We may also ask: What other known sequences are lurking among the $k$'s? Finally, we note that several authors have generalized the Conway-Hofstadter sequence in directions other than the one presented here. The generalization presented here however can be applied to those offered by Mallows \cite{Mallows}, Newman \cite{Newman}, or Pinn \cite{Pinn}. For example, Mallows \cite{Mallows}, introduces the sequence \be c(n)=c(c(n-2))+c(n-c(n-2)) \ee as a generalization of the Conway-Hofstadter sequence. This generalization bases the next term of the sequence on the second to last term of the sequence. Multiplying the $c(n-2)$ terms by $k$ and computing modulo $n-1$, is a natural generalization in the spirit of the $k$-sequences introduced here. We hope the reader will be intrigued by the preliminary results presented in this paper and will be inspired to uncover new facts about the $c_k$'s or generalize the work of Mallows, Newman, and Pinn, in the direction suggested here. \paragraph*{Acknowledgment} Thanks to Julia Pelesko whose interest in Logo led to this work and to M.\ Tempel whose article \cite{Tempel} first introduced us to the Conway-Hofstadter sequence. Thanks also to the anonymous referee for many useful comments and suggestions. \begin{thebibliography}{20} \bibitem{conwaytalk} J.H.\ Conway, Some Crazy Sequences, videotaped talk at AT\&T Bell Labs, July 15, 1988. \bibitem{Mallows} C.L.\ Mallows, Conway's Challenge Sequence, \textit{Amer. Math. Monthly} \textbf{98} (1991), 5--20. \bibitem{NYT} M.W.\ Browne, Intellectual Duel: Brash Challenge, Swift Response, \textit{The New York Times} Section C August 30 (1988), 1. \bibitem{Kubo} T.\ Kubo and R.\ Vakil, On Conway's recursive sequence, \textit{Disc. Math.} \textbf{152} (1996), 225--252. \bibitem{Hofstadter} D.R.\ Hofstadter, Godel, Esher,Bach, Vintage Books, New York, 1980, 137. \bibitem{Newman} D.\ Newman, Problem E3274, \textit{Amer. Math. Monthly} \textbf{95} (1988), 555. \bibitem{Pinn} K.\ Pinn, A Chaotic Cousin of Conway's Recursive Sequence, \textit{Exp. Math.} \textbf{9} (2000), 55--66. \bibitem{Tempel} M.\ Tempel, Easy as $1 1 2 2 3$, \textit{Online publications of the Logo Foundation}, el.media.mit.edu/logo-foundation/pubs/papers. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 11B37; Secondary 11B50. \noindent \emph{Keywords:} Conway-Hofstadter, Fibonacci sequence, nonlinear recursion. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A004001}, \seqnum{A004526}, \seqnum{A004396}, and \seqnum{A037915}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received January 19 2004; revised version received August 16 2004. Published in {\it Journal of Integer Sequences}, October 1 2004. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}. \vskip .1in \end{document} \end{document}