\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{fullpage} \usepackage{float} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \usepackage{url} \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}}} \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 An Analogue of Stern's Sequence for ${\mathbb Z}[\sqrt 2]$} \vskip 1cm \large Sam Northshield\\ Department of Mathematics\\ SUNY-Plattsburgh\\ Plattsburgh, NY 12901\\ USA \\ \href{mailto:northssw@plattsburgh.edu}{\tt northssw@plattsburgh.edu} \\ \end{center} \vskip .2 in \begin{abstract} We introduce a sequence $b(n)$ of algebraic integers that is an analogue of Stern's diatomic sequence, not only in definition, but also in many of its properties. Just as Stern's sequence arises from Ford circles, so too $b(n)$ arises from an array of circles. We study the generating function for $b(n)$ and derive several closed formulas for the sequence. Two second order recurrence formulas for $b(n)$ are found. It is shown that, for $t$ the square root of 2, the ratios $t\cdot b(n+1)/b(n)$ enumerate the positive rational numbers. Finally, we use $b(n)$ to create a function $f(x)$ that is an analogue of Conway's box function and that has inverse a singular function analogous to Minkowski's question-mark function. \end{abstract} \section{Introduction} \label{sec:introduction} Stern's diatomic sequence is a particularly well studied sequence; see the survey paper by Northshield \cite{Nsds}, sequence \seqnum{A002487} in \cite{Sl}, and the references therein. In this paper, we introduce a new sequence in ${\mathbb Z}[\sqrt 2]$ that is an analogue of Stern's sequence both in definition and also in most of the properties described by Northshield \cite{Nsds}. In Section~\ref{sec:sequence}, we introduce the sequence $(b_n)_{n\ge 0}$. We also describe a ``diatomic array" so, as for Stern's sequence, it earns the adjective ``diatomic". We also develop some basic properties of the sequence. In Section~\ref{sec:Ford circles}, we recall ``Ford circles" and their parameterization by rational numbers. Stern's sequence appears as numerators and denominators in various generations of these circles. A variant of the family of Ford circles is introduced, perhaps first studied by Guettler and Mallows \cite{GM}, and we show how our sequence $(b_n)$ arises from these circles. In Section~\ref{sec:GenFn}, we find a closed formula for the generating function for $(b_n)$. Just as Fibonacci numbers have a closed formula in terms of roots of a certain equation (Binet's formula), Northshield \cite{Nsds} showed that an analogous closed formula exists for Stern's sequence (involving $s_2(n)$, the number of ones in the binary representation of an $n$). Here we derive an analogous closed formula for $(b_n)$, this time involving $s_{3,1}(n)$, the number of ones in the ternary representation of $n$. Another closed formula is given in terms of generalized Lucas numbers. In Section~\ref{sec:recurrence}, we show that $(b_n)$ satisfies a three-term recurrence $$b_{n+1}=(2\nu_3(n)+1)\sqrt 2 b_n-b_{n-1}$$ where $\nu_3(n):=\max\{k: 3^k|n\}$. We show that a similar formula holds for Stern's sequence $(a_n)$ as well: $$a_{n+1}=(2\nu_2(n)+1) a_n-a_{n-1}$$ where $\nu_2(n):=\max\{k: 2^k|n\}$. We are also able to give a modified Fibonacci recurrence for $(b_n)$ as follows: $$b_{n+1}=\sqrt 2 b_n+b_{n-1}-2(b_{n-1}\bmod (\sqrt 2 b_n))$$ which is analogous to a result of Northshield \cite[Proposition 4.3]{Nsds}: $$a_{n+1}=a_n+a_{n-1}-2(a_{n-1}\bmod a_n).$$ In Section~\ref{sec:enumeration}, we define a function on the triadic rationals in $[0,1]$ by $$f\left(\dfrac k{3^n}\right)=\dfrac{b_k}{b_k+b_{3^n-k}}.$$ We determine the range of $f$ and consequently identify the set $\{[b_k,b_{k+1}]\}$ as the pairs of non-negative relatively prime integers (in the ring ${\mathbb Z}[\sqrt 2]$) such that $\sqrt 2 b_{k+1}/b_k\in{\mathbb Q}$. It follows that the map $n\mapsto R_n$ defined by $$R_1=2, R_n=4\nu_3(n)+2-\frac2{R_{n-1}}$$ is a bijection from ${\mathbb Z}^+$ to ${\mathbb Q}^+$. Alternatively, the iterates of $2+\frac2x-4\left\{\frac 1x\right\}$, starting at 2, span the entire set of positive rational numbers. In Section~\ref{sec:singular function}, the function $f$ introduced in Section~\ref{sec:enumeration} is shown to extend to a continuous strictly increasing function on $[0,1]$. Its inverse is an analogue of Minkowski's question-mark function $?(x)$ and, in fact, it shares the same formula in terms of the continued fraction expansion of $x$ as the original $?(x)$ except for the base of 2 is changed to 3. In Section~\ref{sec:future} we give some directions for future research and, in Section~\ref{sec:appendix}, we give Maple code for the sequence $(b_n)$ as well as the first 101 terms of $(b_n)$. \section{The sequence} \label{sec:sequence} Throughout this paper, for notational convenience, we let $\tau:=\sqrt 2$. Let $b_0:=0$, $b_1:=1$, and \begin{equation}\label{eq: 1}\begin{aligned} &b_{3n}:=b_n;\\ &b_{3n+1}:=\tau\cdot b_n+b_{n+1};\\ &b_{3n+2}:=b_n+\tau\cdot b_{n+1}.\end{aligned}\end{equation} Looking at the first few terms, we get $$0, 1,\tau, 1, 2\tau, 3, \tau, 3, 2\tau,1, 3\tau, 5,2\tau,7, 5\tau,3,4\tau,5, \tau, 5, 4\tau, 3, 5\tau,7, 2\tau,5,\ldots$$ Maple code for constructing this sequence, and a longer list of its elements, is in the Appendix (Section~\ref{sec:appendix}). Consider an (infinite) array of numbers with first three rows given as follows: $$\begin{array}{ccccccccccccccccccccccccccccccccccccccc}1&&&&&&&&&\tau\\1&&&2\tau&&&3&&&\tau \\1&3\tau&5&2\tau&7&5\tau&3&4\tau&5&\tau \\.&.&.&.&.&.&.&.&.&.\end{array}$$ This is similar to Pascal's triangle in that every entry in all but the top row is the weighted sum of certain entries above. Specifically, given the $n$th row, we get the next row by repeating the $n$th row but, between each two entries, we put the sums of those entries weighted by $[\tau, 1]$ and $[1,\tau]$, respectively. Any entry which is at the top of a column is the sum of two entries on the previous row while any other entry just repeats the entry directly above it. Any entry not in the first or last column contribute to five below and receive from either one or two above, so that its ``valence" (here meaning the number of bonds made with other entries) is 6 or 7. We say the array is ``diatomic": Conceivably, an alloy with two types of atoms, of chemical valence 6 or 7, could combine to make a kind of crystal described by the diatomic array. Of course, such a crystal could only exist in hyperbolic space since row size increases exponentially. The sequence $(b_n)$ arises from this array: the $n$th row is $b_{3^n},\ldots, b_{2\cdot 3^n}$ (and the reverse of the $n$th row is $b_{2\cdot 3^n},\ldots, b_{3^{n+1}}$). Just as it was for Stern's diatomic sequence, the adjective ``diatomic" is appropriate for $(b_n)$ as well. We observe that the $n$th row of the diatomic array contains $3^{n-1}+1$ elements while the sum of the elements in the $n$th row satisfies the recurrence $S_{n+1}=\eta^2(S_n-1)$ where $\eta:=1+\sqrt 2$ is the fundamental unit of ${\mathbb Z}[\sqrt 2]$ (i.e., all $a+b\sqrt 2$ with norm $a^2-2b^2=\pm 1$ are of the form $\pm\eta^n$ for some $n\in{\mathbb Z}$). Note that $S_n=x_n+y_n\sqrt 2$ where $(x_n)$ and $(y_n)$ are the integer sequences \seqnum{A046090} and \seqnum{A011900} in \cite{Sl}, respectively. Each segment $b_{3^n},\ldots, b_{3^{n+1}}$ of our original sequence $(b_n)$ is palindromic and we may express this symmetry as a formula: \begin{proposition}\label{prop:2.1} For all $n$ and all $k$ between $0$ and $2\cdot 3^{n}$, \begin{equation}\label{eq: 2} b_{3^n+k}=b_{3^{n+1}-k}.\end{equation}\end{proposition} \begin{proof}(Induction on $n$). The $n=0$ case follows from the fact that $b_1=1=b_3$. Suppose that the conclusion of the proposition is true for $n$ and that $k$ is between $0$ and $2\cdot 3^{n+1}$. There are three cases: $k=3j+i$ where $i=0,1$, or 2. In the case where $k=3j$, $$b_{3^{n+1}+k}=b_{3^n+j}=b_{3^{n+1}-j}=b_{3^{n+2}-k}.$$ For $k=3j+i$ where $j=1$ or 2, if $0\le 3k+j\le 2\cdot 3^{n+1}$ then $-j\le 3k\le 2\cdot 3^{n+1}-j$ and so $0\le k\le 2\cdot 3^n-1$. Hence, by the inductive hypothesis, $$b_{3^n+j+1}=b_{3^{n+1}-j-1} \text{ and } b_{3^n+j}=b_{3^{n+1}-j}.$$ When $k=3j+1$, $$\begin{aligned} b_{3^{n+1}+k}&=b_{3(3^n+j)+1}=\tau b_{3^n+j}+b_{3^n+j+1}\\&=\tau b_{3^{n+1}-j}+b_{3^{n+1}-j-1}=b_{3(3^{n+1}-j-1)+2}=b_{3^{n+2}-k}.\end{aligned}$$ When $k=3j+2$, $$\begin{aligned}b_{3^{n+1}+k}&=b_{3(3^n+j)+2}=b_{3^n+j}+\tau b_{3^n+j+1}\\&=b_{3^{n+1}-j}+\tau b_{3^{n+1}-j-1}=b_{3(3^{n+1}-j-1)+1}=b_{3^{n+2}-k}.\end{aligned}$$ \end{proof} Consider next the \emph{crushed array} formed by taking rows of $b_{3^n},\ldots,b_{3^{n+1}-1}$ with all the terms squeezed to the left as far as possible: $$\begin{array}{ccccccccccccccccccccccccccc} 1&\tau&&&&&&&&&&&&&&&&&&&&&\\ 1&2\tau&3&\tau&3&2\tau&&&&&&&&&&&&&&&&&\\ 1&3\tau&5&2\tau&7&5\tau&3&4\tau&5&\tau&5&4\tau&3&5\tau&7&2\tau&5&3\tau&&&&&\\ 1&4\tau&7&3\tau&11&8\tau&5&7\tau&9&2\tau&11&9\tau&7&12\tau&17&5\tau&13&8\tau&\ldots&&&&\\ \end{array}$$ Apparently, each column is an arithmetic sequence (i.e., successive differences are constant) and the sequence of these differences is $(\tau b_n)$. \begin{proposition}\label{prop:2.2} If $0\le k<3^n$, then $$b_{3^n+k}-b_{3^n-k}=\sqrt 2 b_k.$$ \end{proposition} \begin{proof} (Induction on $n$). Since $b_{1+0}-b_{1-0}=0=\tau b_0$ and $b_{1+1}-b_{1-1}=b_2-b_0=\tau =\tau b_1$, the proposition holds for $n=0$. Suppose the proposition is true for $n$ and let $k$ be between 0 and $3^{n+1}-1$ inclusive. There are three cases: $k=3j+i$ for $i=0,1$, or 2. If $k=3j$, then $$b_{3^{n+1}+k}-b_{3^{n+1}-k}=b_{3(3^{n}+j)}-b_{3(3^{n}-j)}=b_{3^{n}+j}-b_{3^{n}-j}=\tau b_j=\tau b_k.$$ If $k=3j+1$, then $$\begin{aligned} b_{3^{n+1}+k}-b_{3^{n+1}-k}&=b_{3(3^{n}+j)+1}-b_{3(3^{n}-j-1)+2}\\&=(\tau b_{3^{n}+j} +b_{3^{n}+j+1}) -(b_{3^{n}-j-1} +\tau b_{3^{n}-j})\\&=\tau(b_{3^{n}+j}-b_{3^{n}-j})+(b_{3^{n}+j+1}-b_{3^{n}-j-1})\\&=\tau^2 b_j +\tau b_{j+1}=\tau b_k.\end{aligned}$$ If $k=3j+2$, then $$\begin{aligned} b_{3^{n+1}+k}-b_{3^{n+1}-k}&=b_{3(3^{n}+j)+2}-b_{3(3^{n}-j-1)+1}\\&=(b_{3^{n}+j} +\tau b_{3^{n}+j+1}) -(\tau b_{3^{n}-j-1} + b_{3^{n}-j})\\&=(b_{3^{n}+j}-b_{3^{n}-j})+\tau(b_{3^{n}+j+1}-b_{3^{n}-j-1})\\&=\tau b_j +\tau^2 b_{j+1}=\tau b_k.\end{aligned}$$ \end{proof} \begin{proposition}\label{prop:det} For $0\le k<3^n$, $$b_{k+1}b_{3^n-k}-b_kb_{3^n-k-1}=1.$$ \end{proposition} Although it is possible to prove Proposition~\ref{prop:det} using induction and the two previous propositions, we will defer the proof to Section~\ref{sec:enumeration} (equation \eqref{prop2.3}). \begin{theorem} Let $j(n):=(3^n+1)/2$. Then $$\max\{b_k: 3^n\le k<3^{n+1}\}=b_{j(n)}=\frac{(\sqrt 2+1)^n+(\sqrt2-1)^n}2.$$ \end{theorem} \begin{proof} Let $x_n:=((\tau+1)^n+(\tau-1)^n)/2$. Since $\tau\pm1$ are zeros of $x^2-2\tau x+1$, it follows that $$x_0=1, x_1=\tau, x_{n+1}=2\tau x_n-x_{n-1}.$$ We show that $b_{j(n)}$ satisfies the same recurrence. Note $b_{j(0)}=b_1=1=x_0$ and $b_{j(1)}=b_2=\tau =x_1$. Since $$b_{3k-2}=b_{3(k-1)+1}=\tau b_{k-1}+b_k=\tau(b_{k-1}+\tau b_k)-b_k=\tau b_{3(k-1)+2}-b_k=\tau b_{3k-1}-b_k,$$ it follows that $$b_{9k-4}=b_{3k-2}+\tau b_{3k-1}=2\tau b_{3k-1}-b_k.$$ Replacing $k$ by $j(n-1)$ and using the facts that $j(n)=3j(n-1)-1$ and $j(n+1)=9j(n-1)-4$, $$b_{j(n+1)}=2\tau b_{j(n)}-b_{j(n-1)}$$ and therefore $b_{j(n)}=x_n$. A similar argument shows $b_{j'(n)}=((\tau+1)^n-(\tau-1)^n)/2$ where $j'(n)=j(n)-1=(3^n-1)/2$. Hence $b_{j(n)-1}^2=b_{j(n)}^2-1$ and so $b_{j(n)-1}$ is the second largest value in $n$th row. It follows that the largest value in the $(n+1)$st row is $b_{j(n)-1}+\tau b_{j(n)}=b_{3j(n)-1}=b_{j(n+1)}$. By induction, the theorem follows. \end{proof} \begin{corollary} $\displaystyle\limsup_{n\rightarrow\infty}\dfrac {2b_n}{(2n)^{\log_3(1+\sqrt 2)}}\ge 1$. \end{corollary} We conjecture that equality holds here. If true, then this is an analogue of a recent result by Coons and Tyler \cite{CT} on Stern's sequence. \section{Ford circles} \label{sec:Ford circles} We say a circle in the $x,y$-plane is \emph{normal} if it is above and tangent to the $x$-axis. For $t\in{\mathbb R}$ and $r>0$, let $C(t,r)$ be the circle with center $(t,r)$ and radius $r$. Hence, $C(t,r)$ is normal. We note that every normal circle can be uniquely represented as $C(t,r)$ for some $t,r$. By the Pythagorean theorem, two circles $C(t,r)$ and $C(t',r')$ are \emph{tangent} (we write $C(t,r)||C(t',r')$) if and only if $$(t-t')^2+(r-r')^2=(r+r')^2$$ or, equivalently, \begin{equation}\label{eq: 3}(t-t')^2=4rr'.\end{equation} Given $a,b\in{\mathbb R}$ with $b>0$, we define $$C_{a,b}:=C\left(\frac ab, \frac 1{2b^2}\right).$$ Then every circle above and tangent to the $x$-axis can be uniquely represented as $C_{a,b}$ for some real $a,b$ ($b>0$): $$C(t,r)=C_{t/\sqrt{2r}, 1/\sqrt{2r}}.$$ By \eqref{eq: 3}, two such circles are tangent, i.e., $C_{a,b}||C_{c,d}$, if and only if $|ad-bc|=1$. From this point on, we write $a\perp b$ for $a,b$ relatively prime. We define the set of Ford circles as follows: $${\cal F}:=\{C_{a,b}: a,b\in{\mathbb Z}, a\perp b\}.$$ Hence ${\cal F}$ is parameterized by the rationals via the map taking $a/b$ (in lowest terms) to $C_{a,b}$. \begin{figure}[htbp] \centering \includegraphics[width=3in]{Fig1.eps} \caption{Ford Circles} \label{fig. 1} \end{figure} Given two normal circles that are tangent to each other, there is a unique normal circle between and tangent to both. Further, it is easy to see that if these circles are $C_{a,b}, C_{c,d}$ (i.e., $|ad-bc|=1$) then $C_{a+c,b+d}$ is the unique circle between and tangent to both. The Ford circles are also constructed by a recursive geometric procedure: the family of Ford circles of level 0 is just $\{C_{0,1}, C_{1,1}\}$ and, given any two tangent circles of a family of level $n$, add the unique circle between and tangent to those two. The family of level $n$ together with all the circles arising as above creates the family of level $n+1$. ${\cal F}$ turns out to be the union of all the families of all levels \cite{Nfcs}. The family of Ford circles of level $n$ is parameterized by Stern's diatomic sequence $(a_n)_{n\ge 0}$ defined by $a_0=0, a_1=1, a_{2n}=a_n, a_{2n+1}=a_n+a_{n+1}$ \cite{Nsds}: $$\{C_{a_k, a_k+a_{2^n-k}}: k=0,..,2^n\}.$$ A variant of the family of Ford circles has been introduced and studied by Guettler and Mallows \cite{GM}. Given any two tangent normal circles, there exists a unique triple of mutually tangent circles between them, two of which are normal. If we iterate the process of taking these two (instead of taking the unique normal circle between, as for Ford circles) then the resulting array (see Figure 2) is that of Guettler and Mallows \cite{GM}. We shall now show that the circles of level $n$ are then of the form $C_{b_k, b_k+b_{3^n-k}}$. \begin{figure}[htbp] \centering \includegraphics[width=3 in]{Fig2v3.eps} \caption{Ford Circles variant} \label{fig. 2} \end{figure} We shall use the notation $$\begin{pmatrix} a&c\\b&d \end{pmatrix}(z):=\dfrac{az+c}{bz+d}$$ and thus express every M\"obius transformation in terms of a (non-singular) matrix. It is well known that M\"obius transformations take circles to circles (straight lines are considered circles too since, on the Riemann sphere, they are circles through $\infty$ \cite{Ne}). For real $a,b,c,d$ with $ad-bc=1$, the M\"obius transformation above preserves the $x$-axis and takes $x/y$ to $(ax+cy)/(bx+dy)$. Furthermore, since the imaginary part of $m(z)$ is $(ad-bc)/|cz+d|^2$ times the imaginary part of $z$, $m$ takes normal circles to normal circles. \begin{lemma}\label{lem:3.1} If $m$ is a M\"obius transformation $\begin{pmatrix} a&c\\b&d \end{pmatrix}$ with $ad-bc=1$, then $m'(z)=1/(bz+d)^2$, $$m: C(z,r) \mapsto C(m(z), |m'(z)|r),$$ and, consequently, $$\begin{pmatrix} a&c\\b&d \end{pmatrix}: C_{x,y}\mapsto C_{ax+cy, bx+dy}.$$\end{lemma} \begin{proof} Since $a,b,c,d$ are real, the M\"obius transformation $\begin{pmatrix} a&c\\b&d \end{pmatrix}$ takes the $x$-axis to itself and therefore $m(C(z,r))=C(m(z),r')$ for some $r'>0$. Let $w\neq z$ in ${\mathbb R}$. There exists a unique $s>0$ such that $C(z,r)||C(w,s)$. There is then some $s'$ such that $m(C(w,s))=C(m(w),s')$. Since $$4r's'=|m(z)-m(w)|^2=|m'(z)||m'(w)||z-w|^2=|m'(z)||m'(w)|4rs,$$ it follows that $s'/(|m'(w)|s)$ is a constant function of $w$ (equal to $k:=|m'(z)|r/r'$). Letting $w$ converge to $z$ shows that $\frac1k=k$ and so $r'=|m'(z)|r$. The second part follows. $$\begin{aligned} C_{ax+cy, bx+dy}&=C\left(\frac{ax+cy}{bx+dy},\frac1{2|bx+dy|^2}\right)=C\left(m\left(\frac xy\right),\frac1{2y^2\left(b(\frac xy)+d\right)^2}\right)\\ &=C\left(m\left(\frac xy\right), \left|m'\left(\frac xy\right)\right|\cdot\frac 1{2y^2}\right)=m\left(C\left(\frac xy,\frac 1{2y^2}\right)\right)=m(C_{x,y}).\end{aligned}$$ \end{proof} \begin{theorem}\label{thm:3.2} Given two tangent normal circles $C_{a,b}, C_{c,d}$, there exist a unique triple of three mutually tangent circles between them so that the six circles have octahedral contact graph and such that two of those circles are normal. The two normal circles are $C_{\tau a+c, \tau b+d}$ and $C_{a+\tau c, b+\tau d}$. \end{theorem} \begin{proof} Given $C_{0,1}$ and $C_{1,0}$ (which is the line $y=1$), it is easy to see that $C_{\tau, 1}$, $C_{1,\tau}$, and its reflection across $y=1/2$ are the unique (up to reflection around $x=0$) three mutually tangent circles so that the collection of all six has octahedral contact graph. By Lemma~\ref{lem:3.1}, $$\begin{pmatrix} a&c\\b&d \end{pmatrix}: C_{1,0},C_{0,1} , C_{\tau,1},C_{1,\tau}\mapsto C_{a,b},C_{c,d}, C_{\tau a+c, \tau b+d}, C_{a+\tau c, b+\tau d}.$$ \end{proof} For $0\le k\le 3^n$, let $C\left[ \frac k{3^n}\right]:=C_{b_k, b_k+b_{3^n-k}}$. \begin{corollary}\label{cor:3.3} For $0\le k< 3^n$, $C\left[ \frac k{3^n}\right]||C\left[ \frac {k+1}{3^n}\right]$ and the two normal circles as defined by Theorem~\ref{thm:3.2} are given by $C\left[ \frac {3k+1}{3^{n+1}}\right]$ and $C\left[ \frac {3k+2}{3^{n+1}}\right]$. \end{corollary} \begin{proof} Let $A=b_k$, $B=b_k+b_{3^n-k}$, $C=b_{k+1}$, and $D=b_{k+1}+b_{3^n-k-1}$. By Proposition~\ref{prop:det}, $C_{A,B}||C_{C,D}$ and so $C\left[ \frac k{3^n}\right]||C\left[ \frac {k+1}{3^n}\right]$. By Theorem~\ref{thm:3.2}, the two ``new circles" are $C_{\tau A+C, \tau B+D}$ and $C_{A+\tau C, B+\tau D}$. It is easy to check, by \eqref{eq: 1}, that $\tau A+C=b_{3k+1}$, $A+\tau C=b_{3k+2}$, $\tau B+D=b_{3k+1}+b_{3^{n+1}-(3k+1)}$, and $B+\tau D=b_{3k+2}+b_{3^{n+1}-(3k+2)}$. The result follows. \end{proof} \section{Generating function} \label{sec:GenFn} Let $B(x):=\displaystyle\sum_{n=0}^{\infty} b_{n+1} x^n$. \begin{proposition}\label{prop:9} $B(x):=(1+\sqrt 2 x +x^2+ \sqrt 2 x^3 +x^4)B(x^3)$. \end{proposition} \begin{proof} Since $b_0=0$, $\sum b_n x^n=x\sum b_{n+1}x^n$ and thus $$\begin{aligned} &B(x)=\sum b_{n+1}x^n=\sum b_{3n+1}x^{3n}+\sum b_{3n+2}x^{3n+1}+\sum b_{3n+3}x^{3n+2}\\ &=\sum (\tau b_n+b_{n+1})x^{3n}+\sum (b_n+\tau b_{n+1})x^{3n+1}+\sum b_{n+1}x^{3n+2}\\ &=\tau\sum b_n x^{3n} +\sum b_{n+1}x^{3n}+x\sum b_{n}x^{3n}+x\tau\sum b_{n+1}x^{3n}+x^2\sum b_{n+1}x^{3n}\\ &=(\tau x^3+1+x^4 +x\tau+x^2)\sum b_{n+1}x^{3n}\end{aligned}$$ and the proposition follows. \end{proof} We let $\langle N_1, N_2,\ldots, N_n\rangle_k$ be 1 or 0 according to whether the integers $N_i$ share no non-zero digits in their respective $k$-ary expansions or not. Northshield \cite[Theorem 4.1]{Nsds} expressed Stern's sequence $(a_n)$ thus: $$a_{n+1}=\displaystyle\sum_{a+2b=n} \langle a,b\rangle_2.$$ We have an analogue of this theorem for $(b_n)$: \begin{theorem}\label{thm:4.2} For $n\ge 0$, $b_{n+1}=\displaystyle\sum_{a+2b+3c+4d=n} \langle a,b,c,d\rangle_3 \cdot (\sqrt 2)^{a+c}$. \end{theorem} \begin{proof} By the preceding proposition, $$\begin{aligned}B(x)&=(1+\tau x +x^2+ \tau x^3 +x^4)\cdot(1+\tau x^3 +x^6+ \tau x^9 +x^{12})\\ &\cdot(1+\tau x^9 +x^{18}+ \tau x^{27} +x^{36})\cdots\end{aligned}$$ and so $B(x)$ can be written as a sum indexed by all choices of four integers with no ternary digits in common: $$B(x)=\sum_{\langle a,b,c,d\rangle_3=1} \tau^{a+c} x^{a+2b+3c+4d}.$$ The result follows by equating coefficients. \end{proof} Some immediate consequences are that, if $n$ is even, then $b_n$ is an integer multiple of $\tau$; if $n$ is odd then $b_n$ is an odd integer. The following leads to another closed formula for $(b_n)$. \begin{lemma} \label{lem:11} $1+\sqrt 2 x +x^2+ \sqrt 2 x^3 +x^4=(1+\frac{1+\sqrt 3}{\sqrt 2}x+x^2)(1+\frac{1-\sqrt 3}{\sqrt 2}x+x^2)$. \end{lemma} \begin{proof} Suppose $1+\tau x +x^2+ \tau x^3 +x^4=(1+ax+x^2)(1+bx+x^2)$. Multiplying the right side out and equating coefficients, $a+b=\tau$ and $2+ab=1$. Then $a,b$ are roots of $x^2-\tau x-1=0$ and the result follows.\end{proof} Note that the zeros of $1+\tau x +x^2+ \tau x^3 +x^4$ can easily be seen to be $\zeta\omega, \overline\zeta\omega,\zeta\overline\omega$, and $\overline\zeta\overline\omega$ where $\zeta=e^{i5\pi/12}$ and $\omega=e^{i2\pi/3}$. Recall Binet's formula for the $n$th Fibonacci number: for $\phi$ and $\overline\phi$ the zeros of $x^2-x-1$, $$F_n=\dfrac{\phi^n-\overline\phi^n}{\phi-\overline\phi}.$$ Alternatively, we may write $$F_{n+1}=\displaystyle\sum_{k=0}^n \phi^k\overline\phi^{n-k}.$$ Northshield \cite[Proposition 4.4]{Nsds} proved a Binet type formula for Stern's sequence: for $\sigma$ and $\overline\sigma$ the zeros of $x^2+x+1$ and $s_2(n)$ the number of ones in the binary expansion of $n$, $$a_{n+1}=\displaystyle\sum_{k=0}^n \sigma^{s_2(k)}\overline\sigma^{s_2(n-k)}.$$ The following is a Binet type formula for $(b_n)$. Let $s(n)$ denote the number of ones in the ternary representation of $n$ (\seqnum{A062756} in \cite{Sl}). \begin{theorem}\label{binet} For $\rho$ and $\overline\rho$ the zeros of $x^2-\sqrt 2 x-1$ and $s(n)$ the number of ones in the ternary representation of $n$, $$b_{n+1}=\displaystyle\sum_{k=0}^{n} \rho^{s(k)} \overline\rho^{s(n-k)}.$$ \end{theorem} \begin{proof} The zeros of $x^2-\tau x-1$ are $(1\pm\sqrt 3)/\tau$. By Proposition~\ref{prop:9} and Lemma~\ref{lem:11}, $$\begin{aligned} B(x)&=\displaystyle\prod_{n=0}^{\infty} (1+\tau x^{3^n} +x^{2\cdot 3^n}+ \tau x^{3\cdot 3^n} +x^{4\cdot 3^n}) \\&=\displaystyle\prod_{n=0}^{\infty} (1+ax^{3^n}+x^{2\cdot 3^n} )\cdot \displaystyle\prod_{n=0}^{\infty} (1+bx^{3^n}+x^{2\cdot 3^n})\end{aligned}$$ where $a=\dfrac{1+\sqrt 3}{\tau}$ and $b=\dfrac{1-\sqrt 3}{\tau}$. Since $$\displaystyle\prod_{n=0}^{\infty} (1+ax^{3^n}+x^{2\cdot 3^n} )=\displaystyle\sum_{k=0}^{\infty} a^{s(k)}x^k,$$ $$B(x)=\left(\displaystyle\sum_{k=0}^{\infty} a^{s(k)}x^k\right)\left(\displaystyle\sum_{k=0}^{\infty} b^{s(k)}x^k\right)=\displaystyle\sum_{n=0}^{\infty}\left(\displaystyle\sum_{k=0}^n a^{s(k)}b^{s(n-k)}\right) x^n.$$ \end{proof} Let $(l_n)_{n\ge 0}$ denote the generalized Lucas numbers $2,\tau, 4, 5\tau, 14, 19\tau, 52, 71\tau,\ldots$ defined by $$l_0=2, l_1=\tau, l_{n+1}=\tau l_n+l_{n-1}.$$ We note that $(l_{2n})_{n\ge 0}$ is sequence \seqnum{A003500} in \cite{Sl} and $(l_{2n+1}/\sqrt 2)_{n\ge 0}$ is sequence \seqnum{A001834} in \cite{Sl}. \begin{corollary} $b_{n+1}=\dfrac12\displaystyle\sum_{k=0}^n (-1)^{s(k)\wedge s(n-k)}l_{|s(k)-s(n-k)|}$. \end{corollary} \begin{proof} It is easy to see that $$\displaystyle\sum_{k=0}^n (ab)^{s(k)\wedge s(n-k)}(a^{|s(k)-s(n-k)|}+b^{|s(k)-s(n-k)|})=2\displaystyle\sum_{k=0}^n a^{s(k)}b^{s(n-k)}$$ holds generally for any $a,b$ and any natural numbers $s(k)$. For the choice $a=(1+\sqrt 3)/\sqrt 2$ and $b=(1-\sqrt 3)/\sqrt 2$, $ab=-1$ and the result follows from Theorem~\ref{binet}. \end{proof} \section{Recurrence formulas} \label{sec:recurrence} For a prime $p$, let $\nu_p(n)$ be the largest $k$ so that $p^k$ divides $n$. The sequences $(\nu_2(n))$ and $(\nu_3(n))$ appear as, respectively, \seqnum{A007814} and \seqnum{A007949} in \cite{Sl}. \begin{theorem}\label{thm:5.1} The sequence $(b_n)$ satisfies, for $n>0$, $$b_{n+1}=(2\nu_3(n)+1)\tau b_n-b_{n-1}.$$ \end{theorem} \begin{proof} Let $r_n:= b_{n+1}+b_{n-1}-\tau b_n$. Then $$\begin{aligned} r_{3n+1}&=b_{3n+2}+b_{3n}-\tau b_{3n+1}=b_n+\tau b_{n+1}+b_n-\tau(\tau b_n+b_{n+1})\\ &=b_n+\tau b_{n+1}+b_n-2b_n-\tau b_{n+1}=0, \end{aligned}$$ $$\begin{aligned} r_{3n+2}&=b_{3n+3}+b_{3n+1}-\tau b_{3n+2}=b_{n+1}+\tau b_{n}+b_{n+1}-\tau(b_n+\tau b_{n+1})\\ &=2b_{n+1}+\tau b_n-\tau b_n-2b_{n+1}=0, \end{aligned}$$ and $$\begin{aligned} r_{3n}&=b_{3n+1}+b_{3n-1}-\tau b_{3n}=\tau b_n+b_{n+1}+b_{n-1}+\tau b_{n}-\tau b_n\\ &=b_{n+1}+b_{n-1}+\tau b_n=r_n+2\tau b_n. \end{aligned}$$ By induction, $r_n=2\tau\nu_3(n) b_n$ and the result follows.\end{proof} \begin{corollary}\label{cor:5.2} Let $R_n:=\tau\frac{b_{n+1}}{b_n}$. Then $R_1=2$ and $$R_{n}=4\nu_3(n)+2-\frac2{R_{n-1}}.$$ \end{corollary} \begin{remark} An analogue of this result works for Stern's diatomic sequence (proof, using $\nu_2(n)=\lfloor a_{n-1}/a_n\rfloor$, is left to the reader): if $r_n:=a_{n+1}/{a_n}$, then $$r_n=2\nu_2(n)+1-\frac1{r_{n-1}}.$$ \end{remark} \begin{lemma}\label{lem:5.3} For $n>0$, $\left\lfloor\dfrac1{R_{n-1}}\right\rfloor=\nu_3(n).$\end{lemma} \begin{proof} For $n>0$, let $Y_n:=\dfrac{b_{n-1}}{\tau b_n}=\dfrac1{R_{n-1}}$. Then $$Y_{3n}=1+Y_n\text{, } Y_{3n+1}=\dfrac{b_n}{2b_n+\tau b_{n+1}}\text{, and } Y_{3n+2}=\dfrac{\tau b_n+b_{n+1}}{\tau b_n+2b_{n+1}}.$$ Hence $\lfloor Y_{3n}\rfloor=1+\lfloor Y_{n}\rfloor$, $\lfloor Y_{3n+1}\rfloor =0$, and $\lfloor Y_{3n+2}\rfloor =0$. Since $Y_1=0$, the result follows by induction. \end{proof} We may then get recurrences new for $(R_n)$ and $(b_n)$. \begin{theorem} \label{thm:18} For $n>0$, $$R_{n+1}=2+\dfrac 2{R_n}-4\left\{\dfrac1{R_n}\right\}$$ and $$b_{n+1}=\sqrt 2 b_n+b_{n-1}-2(b_{n-1} \bmod (\sqrt 2 b_n)).$$ \end{theorem} \begin{proof} By Corollary~\ref{cor:5.2} and Lemma~\ref{lem:5.3}, $$\begin{aligned} R_n&=4\nu_3(n)+2-\dfrac2{R_{n-1}}=4\left\lfloor\dfrac 1{R_{n-1}}\right\rfloor+2-\dfrac 2{R_{n-1}}\\ &=2+\dfrac 2{R_{n-1}}+4\left(\left\lfloor\dfrac 1{R_{n-1}}\right\rfloor-\dfrac 1{R_{n-1}}\right) =2+\dfrac 2{R_{n-1}}-4\left\{\dfrac 1{R_{n-1}}\right\}\end{aligned}$$ which shows the first part. Using Corollary~\ref{cor:5.2} again, $$\dfrac{\tau b_{n+1}}{b_n}=4\nu_3(n)+2-\dfrac{2 b_{n-1}}{\tau b_n}.$$ Multiplying by $b_n/\tau$, we find $$\begin{aligned} b_{n+1}&=2\tau b_n\nu_3(n)+\tau b_n-b_{n-1}\\ &=\tau b_n+b_{n-1}-2(b_{n-1}-\tau b_n\nu_3(n)) \end{aligned}$$ and the result follows from Lemma~\ref{lem:5.3} and the fact that $$b_{n-1}\bmod (\tau b_n)=b_{n-1}-\tau b_n\left\lfloor\frac{b_{n-1}}{\tau b_n}\right\rfloor=b_{n-1}-\tau b_n\nu_3(n).$$ \end{proof} \section{Enumerating the rationals} \label{sec:enumeration} Let $\cal{D}$ denote the set $\{ k/3^n: k,n\in\mathbb{N}^+, k\le 3^n \}$ of triadic rationals in the unit interval and consider the function $f:\cal{D}\rightarrow{\mathbb Q}(\tau)$ defined by $$f(k/3^n):=\dfrac{b_k}{b_k+b_{3^n-k}}.$$ This function is well-defined since $$f(3k/3^{n+1})=\dfrac{b_{3k}}{b_{3k}+b_{3^{n+1}-3k}}=\dfrac{b_k}{b_k+b_{3^n-k}}=f(k/3^n).$$ In this section, we find the image of the triadic rationals under the map $f$. Let $$B_0:=\begin{pmatrix} 1&\tau\\0&1\end{pmatrix}, B_1:=\begin{pmatrix} \tau&1\\1&\tau\end{pmatrix}, B_2:=\begin{pmatrix} 1&0\\ \tau&1\end{pmatrix} \text{ and, for $n\in{\mathbb Z}^+$, } v_n:=\begin{pmatrix} b_{n+1}\\b_n\end{pmatrix}.$$ Then, for $i=0,1$, and $2$, $$B_i v_n=v_{3n+i}.$$ If $m=\displaystyle\sum_{k=0}^n i_k3^k$ then \begin{equation}\label{new eqn}\begin{aligned} &B_{i_0}B_{i_1}\cdots B_{i_n}v_0=v_m;\\ &B_{i_0}B_{i_1}\cdots B_{i_n}v_1=v_{3^{n+1}+m}. \end{aligned}\end{equation} Hence, \begin{equation}\label{eq: mat1} B_{i_0}B_{i_1}\cdots B_{i_n}B_0=\begin{pmatrix}b_{m+1}&b_{3^{n+1}+m+1}\\b_{m}&b_{3^{n+1}+m}\end{pmatrix}\end{equation} and so, since $^tB_i=B_{2-i}$ and $^t(A\cdot B)=^t\hspace{-4 pt}B\cdot ^t\hspace{-4 pt}A$, \begin{equation}\label{eq: mat2} B_2B_{2-i_n}B_{2-i_{n-1}}\cdots B_{2-i_0}=\begin{pmatrix}b_{3^{n+1}+m}&b_{3^{n+1}+m+1}\\b_m&b_{m+1} \end{pmatrix}. \end{equation} Since the determinant of each $B_i$ is 1, by \eqref{eq: mat1}, \begin{equation}\label{prop2.3} b_{k+1}b_{3^n-k}-b_kb_{3^n-k-1}=1\end{equation} which thus proves Proposition~\ref{prop:det}. The following is an immediate consequence of \eqref{eq: mat1} and \eqref{eq: mat2}. \begin{proposition}\label{prop:6.1} For natural numbers $m,n$ satisfying $m<3^{n+1}$, there exists $k$ such that $$\begin{pmatrix}b_{3^{n+1}+m}\\b_m\end{pmatrix}=\begin{pmatrix}b_{k+1}\\b_k\end{pmatrix}.$$ \end{proposition} We define the \emph{slow Euclidean algorithm} on ordered pairs of real numbers: $${\cal E}: [x,y]\mapsto \begin{cases} [x-\tau y, y], & \text{ if } \frac yx\le \frac1{\tau};\\ [\tau x-y, \tau y-x], & \text{ if } \frac1{\tau}<\frac yx\le \tau;\\ [x, y-\tau x], & \text{ if } \frac yx>\tau;\\ \text{ stop}, & \text{if } xy=0. \end{cases} $$ \begin{proposition} For $x,y\in{\mathbb Z}[\sqrt 2]$, ${\cal E}$ preserves greatest common divisor. \end{proposition} \begin{proof} The determinant of each $B_i$ is 1 and so $B_i$ is invertible over ${\mathbb Z}[\sqrt 2]$. Hence, for $p$ a prime in ${\mathbb Z}[\sqrt 2]$, $p|\gcd(x,y)$ iff $p|\gcd(x-\tau y, y)$ iff $p|\gcd(x-\tau y,y-\tau x)$ iff $p|\gcd(x, y-\tau x)$. \end{proof} Let ${\cal L}:=\{[x, y]\in{\mathbb Z}[\sqrt 2]^2: x\perp y, \tau x/y\in{\mathbb Q}, x,y\ge 0\}$ where $x\perp y$ means $x$ and $y$ are relatively prime in ${\mathbb Z}[\sqrt 2]$. \begin{theorem} The set ${\cal L}$ satisfies ${\cal L}=\{[b_k,b_{k+1}]: k\in{\mathbb Z}^+\}$. \end{theorem} \begin{proof} Let $[x,y]\in {\cal L}$. Note that ${\cal E}([x,y])\in {\cal L}$. By induction on the length of the ternary expansion of $k$, since $[b_0,b_1]=[0,1]\in{\cal L}$, every $[b_k,b_{k+1}]\in{\cal L}$. Suppose $[x,y]\in{\cal L}$ but is not equal to any $[b_k,b_{k+1}]$. Without loss of generality, we may assume that $x+y$ is as small as possible. Let $[u,v]={\cal E}([x,y])$. Then $[u,v]\in{\cal L}$ and $u+v0, m\ge 0\right\}.$$\end{corollary} \begin{proof} Since $b_{3^N+k}/b_k=\tau n/m$ for some $n,m$, Proposition~\ref{prop:2.2} implies $b_{3^N-k}/b_k= \tau(n-m)/m$ and so $f(k/3^N)=m/(m+(n-m)\tau)$. \end{proof} Recall the sequence $(R_n)_{n\ge 1}$ defined by $R_n:=\sqrt 2\frac{b_{n+1}}{b_n}$. By Corollary~\ref{cor:5.2}, the sequence $(R_n)$ is rational. The first few terms are, starting with $n=1$, $$2, 1, 4, 3/2, 2/3, 3, 4/3, 1/2, 6, 5/3, 4/5, 7/2, 10/7, 3/5, 8/3, 5/4, 2/5, 5, 8/5, 3/4,\ldots$$ By Proposition~\ref{prop:6.1} and Corollary~\ref{cor:6.4}, the range of $R_n$ is all of the positive rationals and therefore, by Corollary~\ref{cor:5.2}, \begin{theorem}\label{thm:6.6} With $R_n$ defined by $$R_1=2, R_{n}=4\nu_3(n)+2-\frac2{R_{n-1}},$$ the map $n\mapsto R_n$ is a bijection from ${\mathbb Z}^+$ to ${\mathbb Q}^+$.\end{theorem} \begin{remark} A version of Theorem~\ref{thm:6.6} appeared as a problem in the American Mathematical Monthly \cite{prob}.\end{remark} The following is a consequence of Theorems~\ref{thm:18} and \ref{thm:6.6}. \begin{corollary} The iterates of $2+\frac 2x-4\left\{\frac1x\right\}$, starting at 2, span the entire set of positive rational numbers. \end{corollary} This is similar, but not equivalent to, the fact \cite[Theorem 5.2]{Nsds} that the iterates of $1+\frac 1x-2\left\{\frac1x\right\}$, starting at 1, span the entire set of positive rational numbers. \vskip .2 in ``Negative continued fractions" have been studied by Eustis (\cite{E}) and others, but to significantly lesser extent than regular continued fractions. They are of the form $$(c_0,c_1,c_2,\ldots):=c_0-\frac 1 {c_1-\frac 1{ c_2-\frac 1{c_3-\ldots}}}$$ where $c_i\in{\mathbb Z}$. Theorem~\ref{thm:6.6} shows that every positive rational is a (finite) negative continued fraction of the form $$R_n=2u_n-\frac 2 {2u_{n-1}-\frac 2{ 2u_{n-2}-\frac 2{2u_{n-3}-\ldots}}}=(2u_n, u_{n-1}, 2u_{n-2}, u_{n-3}, \ldots )$$ where $u_n=2\nu_3(n)+1$. \vskip .2 in Allouche and Shallit \cite{AS} introduced $k$-regular sequences; recall that a sequence $(x_n)_{n\ge 0}$ (in a ring) is 3-regular if there are finitely many sequences such that $(x_{3^in+j})_{n\ge 0}$ is a ${\mathbb Z}$-linear combination of those sequences. \begin{proposition} The sequence $(b_n)$ is 3-regular. \end{proposition} \begin{proof} If $n=\displaystyle\sum_{l=0}^k i_l3^l$ and $j=\displaystyle\sum_{l=0}^{i-1} j_l3^l$ for some $i\ge 1$, then $$3^i n+j=\displaystyle\sum_{l=0}^k i_l3^{l+i}+\displaystyle\sum_{l=0}^{i-1} j_l3^l.$$ In terms of the matrices $B_j$ and vectors $v_j$ defined at the beginning of this section, and by equation \eqref{new eqn}, $$v_{3^in+j}=B_{j_0}B_{j_1}\cdots B_{j_{i-1}}v_n$$ and so $$b_{3^in+j}=\begin{pmatrix} 0&1\end{pmatrix}\cdot B_{j_0}B_{j_1}\cdots B_{j_{i-1}}v_n.$$ That is, $b_{3^in+j}$ is ${\mathbb Z}$-linear combination of $b_n$ and $b_{n+1}$, the entries of $v_n$. \end{proof} The sequence of rationals $R_n:=\dfrac{\tau b_{n+1}}{b_n}$ can be written in lowest terms as $$\frac21,\frac11,\frac41,\frac32,\frac23,\frac31,\frac43,\frac12,\frac61,\frac53, \frac45,\frac72, \frac{10}7, \frac35, \frac83, \frac54,\frac25,\frac51,\frac85, \frac34,\ldots$$ The integer sequences that form the numerators and denominators are $$2,1,4,3,2,3,4,1,6,5,4,7,10, 3,8,5,2,5,8,3,\ldots$$ and $$1,1,1,2,3,1,3,2,1,3,5,2,7,5,3,4,5,1,5,4,\ldots,$$ respectively. We show that these sequences are 3-regular. First we shall define two integer sequences in terms of $(b_n)$ and show that they are term-wise relatively prime and that their term-wise ratios correspond to $R_n$ (and thus we will have formulas for the numerator and denominator sequences). From this, we show that these two sequences are also 3-regular since each is a product of $(b_n)$ with another 3-regular sequence. Recall that two numbers $x,y$ in a Euclidean domain $E={\mathbb Z}$ or ${\mathbb Z}[\sqrt 2]$ are relatively prime (we write $x\perp y$) if and only if there exist $u,v\in E$ such that $ux+vy=1$. If $x\perp y$ and $|ad-bc|=1$ then $ax+by\perp cx+dy$ (since the matrix $\left(\begin{smallmatrix} a&b\\c&d\end{smallmatrix}\right)$ is invertible over $E$). By the recurrence~\eqref{eq: 1}, if $b_n\perp b_{n+1}$ then $b_{3n}\perp b_{3n+1}$, $b_{3n+1}\perp b_{3n+2}$, and $b_{3n+2}\perp b_{3n+3}$. An induction argument shows that $b_n\perp b_{n+1}$ over ${\mathbb Z}[\sqrt 2]$ for all $n$. Recall that, by Theorem~\ref{thm:4.2}, $b_{2n+1}$ is an odd integer for each $n$ and that $b_{2n}$ is an integer multiple of $\tau$ for each $n$. Let $$\gamma(n)=\begin{cases} 1, &\text{ if $n$ is odd;}\\ \tau, &\text{ if $n$ is even.} \end{cases}$$ We then define $D(n):=b_n/\gamma(n)$, and $N(n):=\gamma(n+1)b_{n+1}$. Then $(D(n))_{n\ge 0}$ and $(N(n))_{n\ge 0}$ are integer sequences and, for all $n$, $D(n)\perp N(n)$. Note that $N(n)/D(n)=\tau b_{n+1}/b_n$ and, therefore, $(N(n))$ and $(D(n))$ are the numerator and denominator sequences of $(R_n)$. Since $\gamma(3^in+j)=\gamma(n)$ or $\gamma(n+1)$ according to whether $j$ is even or odd, respectively, the sequence $(\gamma(n))_{n \geq 0}$ is 3-regular. Since the product of 3-regular sequences is 3-regular, the sequences $(N(n))_{n \geq 0}$ and $(D(n))_{n \geq 0}$ are 3-regular. \section{A singular function} \label{sec:singular function} Let $d_{n,k}:= b_k+b_{3^n-k}$ so that $f\left(\frac k{3^n}\right)=\frac{b_k}{d_{n,k}}.$ \begin{lemma}\label{lem:7.1} For $0\le k<3^n$, $d_{n,k}d_{n,k+1}\ge n+1$. \end{lemma} \begin{proof} Note that $$\begin{aligned} &d_{n+1,3k}=d_{n,k}\\ &d_{n+1,3k+1}=\tau d_{n,k}+d_{n,k+1}\\ &d_{n+1,3k+2}= d_{n,k}+\tau d_{n,k+1}. \end{aligned}$$ Then $$d_{n+1,3k}d_{n+1,3k+1}=\tau d_{n,k}^2+d_{n,k}d_{n,k+1}\ge d_{n,k}d_{n,k+1}+1,$$ $$\begin{aligned} d_{n+1,3k+1}d_{n+1,3k+2}&=(\tau d_{n,k}+d_{n,k+1})(d_{n,k}+\tau d_{n,k+1})\\ &=3d_{n,k}d_{n,k+1}+\tau (d_{n,k}^2+d_{n,k+1}^2)\ge d_{n,k}d_{n,k+1}+1,\end{aligned}$$ and $$\begin{aligned} d_{n+1,3k+2}d_{n+1,3k+3}&=(d_{n,k}+\tau d_{n,k+1})d_{n,k+1}\\ &=d_{n,k}d_{n,k+1}+\tau d_{n,k+1}^2\ge d_{n,k}d_{n,k+1}+1.\end{aligned}$$ Hence, for $0\le j<3^{n+1}$, $d_{n+1,j}d_{n+1, j+1}\ge d_{n,\lfloor j/3\rfloor}d_{n,\lfloor j/3\rfloor +1}+1$ and so the lemma follows by induction. \end{proof} \begin{theorem} The function $f\left(\frac k{3^n}\right):=\frac{b_k}{b_k+b_{3^n-k}}$ on the triadic rationals in $[0,1]$ extends to a continuous and strictly increasing function on $[0,1]$. \end{theorem} \begin{proof}\label{thm:27} By Lemma~\ref{lem:7.1} and Proposition~\ref{prop:det} (equation \eqref{prop2.3}), $$\begin{aligned} f\left(\frac {k+1}{3^n}\right)&- f\left(\frac k{3^n}\right)=\dfrac{b_{k+1}}{d_{n,k+1}}-\dfrac{b_{k}}{d_{n,k}} \\&=\dfrac{b_{k+1}b_{3^n-k}-b_kb_{3^n-k-1}}{d_{n,k}d_{n,k+1}}=\dfrac1{d_{n,k}d_{n,k+1}}\in\left(0,\frac1{n}\right).\end{aligned}$$ The result follows. \end{proof} Recall the notation for continued fractions \cite{HW}: for positive integers $c_1, c_2, c_3, \ldots$, $$[0; c_1, c_2, c_3, \ldots]:=1/(c_1+1/(c_2+1/(c_3+ \cdots))).$$ Every irrational positive number between 0 and 1 can be written uniquely in that form (rational numbers have non-unique \emph{finite} expansions). In 1904, Minkowski introduced a singular function (continuous and strictly increasing with derivative existing and 0 almost everywhere) $?:[0,1]\rightarrow [0,1]$. Its value at $x$ is defined in terms of the continued fraction expansion of $x$: If $x=[0,c_1,c_2,\ldots]$ then \begin{equation}\label{?(x)} ?(x):=\sum_{k\ge 1}\dfrac{(-1)^{k+1}}{2^{c_1+\cdots+c_k-1}}.\end{equation} One of the question mark function's most interesting properties is that it maps quadratic surds to rational numbers (since the sequence $c_1,c_2,\ldots$ is eventually periodic precisely when $x$ is a quadratic surd). The inverse of $?(x)$ is known as Conway's box function \cite[p.\ 82]{PVB} and it is known by, for example, Northshield \cite[Theorem 6.2]{Nsds}, that Stern's sequence is related to it: $$?^{-1}\left(\frac k{2^n}\right)=\dfrac{a_k}{a_k+a_{2^n-k}}.$$ \begin{figure}[htbp] \centering \includegraphics[width=2in]{fplot.eps} \includegraphics[width=2in]{finvplot.eps} \caption{The graphs of $f(x)$ and its inverse.} \label{fig. 3} \end{figure} For convenience, we define a function on the triadic rationals ${\cal D}$: $$g\left(\frac k{3^n}\right):=\dfrac{b_k}{b_{3^n+k}}.$$ The functions $f$ and $g$ are closely related: by Proposition~\ref{prop:2.2}, $$\frac{b_{3^n+k}}{b_k}=\frac{b_{3^n-k}+\sqrt 2 b_k}{b_k}= \frac{b_{3^n-k}+ b_k}{b_k}+\sqrt 2-1$$ and therefore \begin{equation}\label{8} g\left(\frac k{3^n}\right)=\dfrac 1{\frac 1{f(k/3^n)}+\sqrt 2-1} \text{ and } f\left(\frac k{3^n}\right)=\dfrac 1{\frac 1{g(k/3^n)}+1-\sqrt 2}.\end{equation} By Theorem~\ref{thm:27} and equation \eqref{8}, $g$ extends to a continuous, strictly increasing function on $[0,1]$. \begin{lemma}\label{lem:7.3} For $0\le x<3$, $g\left(\dfrac{3-x}{3^n}\right)=\dfrac1{n\sqrt 2+g(x)}$. \end{lemma} \begin{proof} Let $k<3^{m+1}$. By Propositions~\ref{prop:2.1} and~\ref{prop:2.2}, $$b_{3^{m+2}-k}=b_{3^{m+1}-k}+\tau b_k.$$ By an induction argument, $$b_{3^{n+m+1}-k}=b_{3^{m+1}-k}+n\tau b_k.$$ Replacing $k$ by $3^{m+1}-k$, and using Proposition~\ref{prop:2.1}, $$b_{3^{n+m}+3^{m+1}-k}=b_k+n\tau b_{3^{m+1}-k}.$$ Hence, $$g\left(\frac{3^{m+1}-k}{3^{n+m}}\right)=\dfrac{b_{3^{m+1}-k}}{b_{3^{m+n}+3^{m+1}-k}}=\dfrac{b_{3^{m}+k}}{b_k+n\tau b_{3^m+k}}=\dfrac 1{n\tau +g(k/3^m)}.$$ Letting $k/3^m\rightarrow x$, the result follows. \end{proof} Consider now continued fractions $[0; c_1\sqrt 2, c_2\sqrt 2, c_3\sqrt 2,\ldots]$. By Lemma~\ref{lem:7.3}, $$g^{-1}\left(\dfrac 1{n\sqrt 2+x}\right)=\dfrac{3-g^{-1}(x)}{3^n}$$ and thus $$g^{-1}([0,c_1\sqrt 2, c_2\sqrt 2, c_3\sqrt 2,\ldots])=\dfrac {3-g^{-1}([0,c_2\sqrt 2, c_3\sqrt 2, c_4\sqrt 2,\ldots])}{3^{c_1}}.$$ An induction argument shows the following. \begin{theorem} For $c_1, c_2, \ldots \in {\mathbb Z}^+$, $$g^{-1}([0,c_1\sqrt 2, c_2\sqrt 2, c_3\sqrt 2,\ldots])=\displaystyle\sum_{k} \dfrac{(-1)^{k+1}}{3^{c_1+\ldots+c_k-1}}.$$\end{theorem} \begin{figure}[htbp] \centering \includegraphics[width=1.8in]{Fig4.eps} \includegraphics[width=2in]{Fig2v3.eps} \caption{Homeomorphic fractals} \label{fig. 4} \end{figure} Figure~\ref{fig. 4} gives a geometric way of viewing our analogue of Minkowski's $?$--function. We consider each of the two objects to be lying in the complex plane with bottom edge coinciding with the unit interval. Clearly they are homeomorphic and there is a unique homeomorphism from the figure on the left to that on the right which takes the unit interval to itself and fixes its endpoints. The restriction of this homeomorphism to the unit interval can be shown to be $f(x)$. \section{Future directions} \label{sec:future} The contact graph of a set of circles (with non-intersecting interiors) is the graph with that vertex set such that we place an edge between two vertices if and only if the circles are tangent. Ford circles are formed by iteratively completing triangles in a contact graph by adding a new vertex (so as to form a graph tetrahedron out of the triangle). If we consider this process ``tetrahedral", then the process generating the variant Ford circles of Section~\ref{sec:Ford circles} is ``octahedral". It then seems that any polyhedron with triangular faces could be used to generate a new set of circles and, thus, a new sequence of (presumably) algebraic integers. At the end of Section~\ref{sec:GenFn}, generalized Lucas numbers $(a^n+b^n)$ were defined. This sequence displayed a type of {\it combinatorial reciprocity} \cite{BS}: the even terms and the odd terms (divided by $\tau$) are sequences of positive integers (\seqnum{A003500} and \seqnum{A001834} in \cite{Sl} respectively) that are known to count various sets of objects. One can consider generalized Fibonacci numbers $(a^n-b^n)/(a-b)$ as well and investigate its even and odd terms. At the end of Section~\ref{sec:enumeration}, the sequences of numerators and denominators of $R_n$ were considered. What do these sequences count? Further, is there some kind of combinatorial reciprocity \cite{BS} occurring here? The three term recurrence of Theorem~\ref{thm:5.1} is reminiscent of the type of recurrence that defines orthogonal polynomials. What are the polynomials generated by that recurrence (with $\tau$ as variable)? What measure makes them orthogonal? In Section~\ref{sec:enumeration}, we have seen sequences satisfying $$r_1=1, r_n=2\nu_2(n)+1-\frac1{r_{n-1}}$$ and $$R_1=2, R_n=4\nu_3(n)+2-\frac2{r_{n-1}}.$$ How does this generalize? \section{Appendix} \label{sec:appendix} The following is Maple code for a function $b$ where $b_n=b(n)$. \vskip .1 in {\tt \begin{verbatim} b := proc (n); if $n\le 1$ then n elif n mod 3 = 0 then b(n/3) elif n mod 3 = 1 then sqrt(2)*b((n-1)/3)+b((n+2)/3) else b((n-2)/3)+sqrt(2)*b((n+1)/3); fi; end proc; \end{verbatim} } \vskip .1 in Output for $n=0..100$: $$\begin{aligned} &0, 1, \sqrt 2, 1, 2\sqrt 2, 3, \sqrt 2, 3, 2\sqrt 2, 1, 3\sqrt 2, 5, 2\sqrt 2, 7, 5\sqrt 2, 3, 4\sqrt 2, 5, \sqrt 2, 5, 4\sqrt 2, 3, 5\sqrt 2, \\& 7, 2\sqrt 2, 5, 3\sqrt 2, 1, 4\sqrt 2, 7, 3\sqrt 2, 11, 8\sqrt 2, 5, 7\sqrt 2, 9, 2\sqrt 2, 11, 9\sqrt 2, 7, 12\sqrt 2, 17, 5\sqrt 2, 13, \\& 8\sqrt 2, 3, 7\sqrt 2, 11, 4\sqrt 2, 13, 9\sqrt 2, 5, 6\sqrt 2, 7, \sqrt 2, 7, 6\sqrt 2, 5, 9\sqrt 2, 13, 4\sqrt 2, 11, 7\sqrt 2, 3, 8\sqrt 2, \\&13, 5\sqrt 2, 17, 12\sqrt 2, 7, 9\sqrt 2, 11, 2\sqrt 2, 9, 7\sqrt 2, 5, 8\sqrt 2, 11, 3\sqrt 2, 7, 4\sqrt 2, 1, 5\sqrt 2, 9, 4\sqrt 2, \\&15, 11\sqrt 2, 7, 10\sqrt 2, 13, 3\sqrt 2, 17, 14\sqrt 2, 11, 19\sqrt 2, 27, 8\sqrt 2, 21, 13\sqrt 2, 5, 12\sqrt 2.\end{aligned}$$ \begin{thebibliography}{99} \bibitem{AS} J.-P. Allouche and J. Shallit, The ring of $k$-regular sequences, \emph{Theoret. Comput. Sci.} \textbf{98} (1992), 163--197. \bibitem{BS} M. Beck, Combinatorial reciprocity theorems, \emph{Jahresber. Dtsch. Math.-Ver.} \textbf{114} (2012), 3--22. \bibitem{CT} M. Coons and J. Tyler, The maximal order of Stern's diatomic sequence, \emph{Mosc. J. Comb. Number Theory} \textbf{4} (2014), 3--14. \bibitem{E} A. Eustis, The negs and regs of continued fractions, senior thesis, Harvey Mudd College, 2006. Available at \\ {\footnotesize\url{https://www.math.hmc.edu/seniorthesis/archives/2006/aeustis/aeustis-2006-thesis.pdf}}. \bibitem{GM} G. Guettler and C. Mallows, A generalization of Apollonian packing of circles, \emph{J. Comb.} \textbf{1} (2010), 1--27. \bibitem{HW} G. H. Hardy and E. M. Wright, \emph{An Introduction to the Theory of Numbers}, fifth edition. Oxford University Press, 1979. \bibitem{Ne} T. Needham, \emph{Visual Complex Analysis}, Oxford University Press, 2000. \bibitem{Nfcs} S. Northshield, Ford circles and spheres, preprint, 2015. Available at \url{http://arxiv.org/abs/1503.00813}. \bibitem{Nsds} S. Northshield, Stern's diatomic sequence $0,1,1,2,1,3,2,3,2,1,4,\ldots$, \emph{Amer. Math. Monthly} \textbf{117} (2010), 581--598. \bibitem{prob} S. Northshield, Problem 11852, \emph{Amer. Math. Monthly} \textbf{122} (2015), 700. \bibitem{PVB} J. Paradis, P. Viader, and L. Bibiloni, The derivative of Minkowski's $?(x)$ Function, \emph{J. Math. Anal. Appl.} \textbf{253} (2001) 107--125. \bibitem{Sl} N. J. A. Sloane, ed., \emph{The On-Line Encyclopedia of Integer Sequences}, \url{http://oeis.org}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11B83; Secondary 05A15, 05B40, 11A55, 11B37, 11B39, 40A15, 52C26. \noindent \emph{Keywords:} continued fraction, recurrence, generating function, circle packing, Fibonacci number. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A001834}, \seqnum{A002487}, \seqnum{A003500}, \seqnum{A007814}, \seqnum{A007949}, \seqnum{A011900}, \seqnum{A046090}, and \seqnum{A062756}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received March 17 2015; revised versions received December 7 2015; December 13 2015. Published in {\it Journal of Integer Sequences}, December 15 2015. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}