\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\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{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\newcommand{\p}[1]{(#1)}
\newcommand{\st}[1]{\left\{#1\right\}}
\newcommand{\fl}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\quot}[1]{``#1''}
\newcommand{\pb}[1]{\left(#1\right)}
\DeclareMathOperator{\modd}{mod}
\newcommand{\seq}{\pb}
\newcommand{\Mf}{M}
\newcommand{\Rh}{B}
\newcommand{\fwd}{\p{\Longrightarrow}}
\newcommand{\bwd}{\p{\Longleftarrow}}
\newcommand{\iffpf}[2]{
\begin{description}
\item[$\fwd$] #1
\item[$\bwd$] #2
\end{description}
}
\newcommand{\limf}[3]{\lim_{#1\rightarrow#2}{#3}}
\newcommand{\limi}[2]{\limf{#1}{\infty}{#2}}
\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
A Slow Relative of Hofstadter's $Q$-Sequence
}
\vskip 1cm
\large
Nathan Fox\\
Department of Mathematics\\
Rutgers University\\
110 Frelinghuysen Rd.\\
Piscataway, NJ 08854\\
USA\\
\href{mailto:fox@math.rutgers.edu}{\tt fox@math.rutgers.edu}
\end{center}
\vskip .2 in
\begin{abstract}
Hofstadter's $Q$-sequence remains an enigma fifty years after its
introduction. Initially, the terms of the sequence increase
monotonically by $0$ or $1$ at a time. But the $12$th term exceeds
the $11$th by two, and monotonicity fails shortly thereafter. In
this paper, we add a third term to Hofstadter's recurrence in the most
natural way. We show that this new recurrence, along with a suitable
initial condition that naturally generalizes Hofstadter's initial
condition, generates a sequence whose terms all increase monotonically
by $0$ or $1$ at a time. Furthermore, we give a complete description
of the resulting frequency sequence, which allows the $n$th term of
our sequence to be efficiently computed. We conclude by showing that
our sequence cannot be easily generalized.
\end{abstract}
\section{Introduction}
The Hofstadter $Q$-sequence~\cite{geb} is defined by the nested recurrence $Q\p{n}=Q\p{n-Q\p{n-1}}+Q\p{n-Q\p{n-2}}$ with the initial conditions $Q\p{1}=Q\p{2}=1$. The first $11$ terms of this sequence, \seqnum{A005185} in the OEIS~\cite{oeis}, are
\[
1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6,\ldots
\]
These terms increase monotonically with successive differences either $0$ or $1$. But, $Q\p{12}=8$, ending the successive difference property. Not long thereafter, $Q\p{15}=10$ and $Q\p{16}=9$, ending the monotonicity. Calculating more terms leads one to the resignation that the Hofstadter $Q$-sequence is anything but well-behaved. While there appear to be some patterns in the sequence, all such observation are as-yet purely emprical. Essentially nothing has been rigorously proven about this sequence. Most critically, nobody has been able to prove that $Q\p{n}$ even exists for all $n$. If $Q\p{n-1}\geq n$ for some $n$, then evaluating $Q\p{n}$ would require knowing $Q\p{k}$ for some $k\leq0$. Since $Q$ is only defined for positive indices, $Q\p{n}$ (and all subsequent terms) would fail to exist in this case. If a sequence is finite because of behavior like this, we say that the sequence \emph{dies}.
Hofstadter and Huber~\cite{hofsem,hofv} investigated the following familiy of recurrences, which generalize the Hofstadter $Q$-recurrence. For integers $00,k\in\mathbb{Z}}$, and let
\[
S=\bigcup_{i\geq1}S_i.
\]
We have the following theorem.
\begin{theorem}\label{thm:struct}
Let $m$ be a positive integer.
If $m\in S$, then $m$ appears in the $\Rh$-sequence twice. Otherwise, $m$ appears once. Furthermore, the $\Rh$-sequence is monotone increasing.
\end{theorem}
Theorem~\ref{thm:struct} implies Theorem~\ref{thm:slow}, since Theorem~\ref{thm:struct} asserts both that the sequence is monotone and that each positive integer appears in the sequence. Throughout the rest of this section, we will end up proving Theorem~\ref{thm:struct}, and consequently Theorem~\ref{thm:slow}, by induction. In doing so, we frequently assume that Theorem~\ref{thm:struct} holds up to some point. To make this clear, we define the following indexed families of propositions (where $m$ and $n$ are positive integers):
\begin{itemize}
\item Let $P_m$ denote the proposition \quot{For all integers $1\leq m'\leq m$, if $m'\in S$, then $m'$ appears in the $\Rh$-sequence twice. Otherwise, $m'$ appears once. Furthermore, the $
\Rh$-sequence is monotone increasing as long as its terms are at most $m$.} In this way, $P_m$ is essentially the statement \quot{Theorem~\ref{thm:struct} holds through \emph{value} $m$.}
\item Let $T_n$ denote the proposition \quot{The first $n$ terms of the $\Rh$-sequence are monotone increasing. Furthermore, for all $m$ appearing as one of these first $n$ terms, if $m\in S$, then $m$ appears in these first $n$ terms twice (unless this second occurrence would be in position $n+1$). Otherwise, $m$ appears once.} In this way, $T_n$ is essentially the statement \quot{Theorem~\ref{thm:struct} holds through \emph{index} $n$.}
\end{itemize}
It should be clear from these definitions that the following three statements
are equivalent:
\begin{itemize}
\item Theorem~\ref{thm:struct} is true.
\item $P_m$ holds for all $m\geq1$.
\item $T_n$ holds for all $n\geq1$.
\end{itemize}
We first show that the sets $S_i$ are pairwise disjoint.
\begin{lemma}\label{lem:onei}
Let $i$ and $j$ be positive integers. If $i\neq j$, then $S_i\cap S_j=\emptyset$.
\end{lemma}
\begin{proof}
Suppose for a contradiction that, for some integers $i,j\geq1$ with $i\neq j$, $k_1\cdot 3^i+a_i=k_2\cdot 3^{i+j}+a_{i+j}$. Then
\[
a_{i+j}-a_i=k_1\cdot 3^i-k_2\cdot 3^{i+j}=3^i\p{k_1+k_2\cdot 3^j}.
\]
In particular, $a_{i+j}-a_i$ must be divisible by $3^i$.
But, using the closed form,
\begin{align*}
a_{i+j}-a_i&=\pb{\frac{5}{2}\cdot3^{i+j-1}+\frac{1}{2}}-\pb{\frac{5}{2}\cdot3^{i-1}+\frac{1}{2}}=\frac{5}{2}\pb{3^{i+j-1}-3^{i-1}}\\&=\frac{5}{2}\cdot3^{i-1}\pb{3^j-1}.
\end{align*}
This is clearly not divisible by $3^i$, a contradiction. Therefore, no such $i$ and $j$ can exist, so there is at most one $i\geq1$ such that $m\equiv a_i\pb{\modd 3^i}$, as required.
\end{proof}
For a value $m$, we examine the number of values less than $m$ that are repeated.
Define $R\p{m,i}=\max\pb{0, \fl{\frac{m-a_i-1}{3^i}}}$. This floored quantity counts the pairs $\p{k,i}$ such that $k\cdot3^i+a_i0$ and suppose inductively that
\[
\Rh_k\p{N+q'\p{k+1}+r'}=N+q'k+r'-1
\]
for all $-k\leq q'\p{k+1}+r'