Eisenstein.tex

\documentclass[leqno,fleqn,12pt]{article}

\usepackage{euler,beton,concrete,url,a4wide}
\usepackage[T1]{fontenc}

%% ODER: format ==         = "\mathrel{==}"
%% ODER: format /=         = "\neq "
%
%
\makeatletter
\@ifundefined{lhs2tex.lhs2tex.sty.read}%
  {\@namedef{lhs2tex.lhs2tex.sty.read}{}%
   \newcommand\SkipToFmtEnd{}%
   \newcommand\EndFmtInput{}%
   \long\def\SkipToFmtEnd#1\EndFmtInput{}%
  }\SkipToFmtEnd

\newcommand\ReadOnlyOnce[1]{\@ifundefined{#1}{\@namedef{#1}{}}\SkipToFmtEnd}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{stmaryrd}
\DeclareFontFamily{OT1}{cmtex}{}
\DeclareFontShape{OT1}{cmtex}{m}{n}
  {<5><6><7><8>cmtex8
   <9>cmtex9
   <10><10.95><12><14.4><17.28><20.74><24.88>cmtex10}{}
\DeclareFontShape{OT1}{cmtex}{m}{it}
  {<-> ssub * cmtt/m/it}{}
\newcommand{\texfamily}{\fontfamily{cmtex}\selectfont}
\DeclareFontShape{OT1}{cmtt}{bx}{n}
  {<5><6><7><8>cmtt8
   <9>cmbtt9
   <10><10.95><12><14.4><17.28><20.74><24.88>cmbtt10}{}
\DeclareFontShape{OT1}{cmtex}{bx}{n}
  {<-> ssub * cmtt/bx/n}{}
\newcommand{\tex}[1]{\text{\texfamily#1}}	% NEU

\newcommand{\Sp}{\hskip.33334em\relax}


\newcommand{\Conid}[1]{\mathit{#1}}
\newcommand{\Varid}[1]{\mathit{#1}}
\newcommand{\anonymous}{\kern0.06em \vbox{\hrule\@width.5em}}
\newcommand{\plus}{\mathbin{+\!\!\!+}}
\newcommand{\bind}{\mathbin{>\!\!\!>\mkern-6.7mu=}}
\newcommand{\rbind}{\mathbin{=\mkern-6.7mu<\!\!\!<}}% suggested by Neil Mitchell
\newcommand{\sequ}{\mathbin{>\!\!\!>}}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\usepackage{polytable}

%mathindent has to be defined
\@ifundefined{mathindent}%
  {\newdimen\mathindent\mathindent\leftmargini}%
  {}%

\def\resethooks{%
  \global\let\SaveRestoreHook\empty
  \global\let\ColumnHook\empty}
\newcommand*{\savecolumns}[1][default]%
  {\g@addto@macro\SaveRestoreHook{\savecolumns[#1]}}
\newcommand*{\restorecolumns}[1][default]%
  {\g@addto@macro\SaveRestoreHook{\restorecolumns[#1]}}
\newcommand*{\aligncolumn}[2]%
  {\g@addto@macro\ColumnHook{\column{#1}{#2}}}

\resethooks

\newcommand{\onelinecommentchars}{\quad-{}- }
\newcommand{\commentbeginchars}{\enskip\{-}
\newcommand{\commentendchars}{-\}\enskip}

\newcommand{\visiblecomments}{%
  \let\onelinecomment=\onelinecommentchars
  \let\commentbegin=\commentbeginchars
  \let\commentend=\commentendchars}

\newcommand{\invisiblecomments}{%
  \let\onelinecomment=\empty
  \let\commentbegin=\empty
  \let\commentend=\empty}

\visiblecomments

\newlength{\blanklineskip}
\setlength{\blanklineskip}{1mm}

\newcommand{\hsindent}[1]{\quad}% default is fixed indentation
\let\hspre\empty
\let\hspost\empty
\newcommand{\NB}{\textbf{NB}}
\newcommand{\Todo}[1]{$\langle$\textbf{To do:}~#1$\rangle$}

\EndFmtInput
\makeatother
%
%
%
%
%
%
% This package provides two environments suitable to take the place
% of hscode, called "plainhscode" and "arrayhscode". 
%
% The plain environment surrounds each code block by vertical space,
% and it uses \abovedisplayskip and \belowdisplayskip to get spacing
% similar to formulas. Note that if these dimensions are changed,
% the spacing around displayed math formulas changes as well.
% All code is indented using \leftskip.
%
% Changed 19.08.2004 to reflect changes in colorcode. Should work with
% CodeGroup.sty.
%
\ReadOnlyOnce{polycode.fmt}%
\makeatletter

\newcommand{\hsnewpar}[1]%
  {{\parskip=0pt\parindent=0pt\par\vskip #1\noindent}}

% can be used, for instance, to redefine the code size, by setting the
% command to \small or something alike
\newcommand{\hscodestyle}{}

% The command \sethscode can be used to switch the code formatting
% behaviour by mapping the hscode environment in the subst directive
% to a new LaTeX environment.

\newcommand{\sethscode}[1]%
  {\expandafter\let\expandafter\hscode\csname #1\endcsname
   \expandafter\let\expandafter\endhscode\csname end#1\endcsname}

% "compatibility" mode restores the non-polycode.fmt layout.

\newenvironment{compathscode}%
  {\par\noindent
   \advance\leftskip\mathindent
   \hscodestyle
   \let\\=\@normalcr
   \(\pboxed}%
  {\endpboxed\)%
   \par\noindent
   \ignorespacesafterend}

\newcommand{\compaths}{\sethscode{compathscode}}

% "plain" mode is the proposed default.
% It should now work with \centering.
% This required some changes. The old version
% is still available for reference as oldplainhscode.

\newenvironment{plainhscode}%
  {\hsnewpar\abovedisplayskip
   \advance\leftskip\mathindent
   \hscodestyle
   \let\hspre\(\let\hspost\)%
   \pboxed}%
  {\endpboxed%
   \hsnewpar\belowdisplayskip
   \ignorespacesafterend}

\newenvironment{oldplainhscode}%
  {\hsnewpar\abovedisplayskip
   \advance\leftskip\mathindent
   \hscodestyle
   \let\\=\@normalcr
   \(\pboxed}%
  {\endpboxed\)%
   \hsnewpar\belowdisplayskip
   \ignorespacesafterend}

% Here, we make plainhscode the default environment.

\newcommand{\plainhs}{\sethscode{plainhscode}}
\newcommand{\oldplainhs}{\sethscode{oldplainhscode}}
\plainhs

% The arrayhscode is like plain, but makes use of polytable's
% parray environment which disallows page breaks in code blocks.

\newenvironment{arrayhscode}%
  {\hsnewpar\abovedisplayskip
   \advance\leftskip\mathindent
   \hscodestyle
   \let\\=\@normalcr
   \(\parray}%
  {\endparray\)%
   \hsnewpar\belowdisplayskip
   \ignorespacesafterend}

\newcommand{\arrayhs}{\sethscode{arrayhscode}}

% The mathhscode environment also makes use of polytable's parray 
% environment. It is supposed to be used only inside math mode 
% (I used it to typeset the type rules in my thesis).

\newenvironment{mathhscode}%
  {\parray}{\endparray}

\newcommand{\mathhs}{\sethscode{mathhscode}}

% texths is similar to mathhs, but works in text mode.

\newenvironment{texthscode}%
  {\(\parray}{\endparray\)}

\newcommand{\texths}{\sethscode{texthscode}}

% The framed environment places code in a framed box.

\def\codeframewidth{\arrayrulewidth}
\RequirePackage{calc}

\newenvironment{framedhscode}%
  {\parskip=\abovedisplayskip\par\noindent
   \hscodestyle
   \arrayrulewidth=\codeframewidth
   \tabular{@{}|p{\linewidth-2\arraycolsep-2\arrayrulewidth-2pt}|@{}}%
   \hline\framedhslinecorrect\\{-1.5ex}%
   \let\endoflinesave=\\
   \let\\=\@normalcr
   \(\pboxed}%
  {\endpboxed\)%
   \framedhslinecorrect\endoflinesave{.5ex}\hline
   \endtabular
   \parskip=\belowdisplayskip\par\noindent
   \ignorespacesafterend}

\newcommand{\framedhslinecorrect}[2]%
  {#1[#2]}

\newcommand{\framedhs}{\sethscode{framedhscode}}

% The inlinehscode environment is an experimental environment
% that can be used to typeset displayed code inline.

\newenvironment{inlinehscode}%
  {\(\def\column##1##2{}%
   \let\>\undefined\let\<\undefined\let\\\undefined
   \newcommand\>[1][]{}\newcommand\<[1][]{}\newcommand\\[1][]{}%
   \def\fromto##1##2##3{##3}%
   \def\nextline{}}{\) }%

\newcommand{\inlinehs}{\sethscode{inlinehscode}}

% The joincode environment is a separate environment that
% can be used to surround and thereby connect multiple code
% blocks.

\newenvironment{joincode}%
  {\let\orighscode=\hscode
   \let\origendhscode=\endhscode
   \def\endhscode{\def\hscode{\endgroup\def\@currenvir{hscode}\\}\begingroup}
   %\let\SaveRestoreHook=\empty
   %\let\ColumnHook=\empty
   %\let\resethooks=\empty
   \orighscode\def\hscode{\endgroup\def\@currenvir{hscode}}}%
  {\origendhscode
   \global\let\hscode=\orighscode
   \global\let\endhscode=\origendhscode}%

\makeatother
\EndFmtInput
%


\def\prompt#1{\noindent$\gg$ #1}

\title{Enumerating the Elements of the Eisenstein Array}
\author{
   Roland Backhouse \\{\tt\small rcb@cs.nott.ac.uk} 
   \and 
   Jo\~ao F. Ferreira \\{\tt\small joao@joaoff.com}
}
\date{\today}

\begin{document}
\maketitle

\begin{abstract} In 1858 \cite{stern1858:rationals}, A.M.\ Stern
published a detailed study of a process of constructing an infinite
sequence of numbers from a given pair of numbers.  Stern attributed
the process to Eisenstein, and the sequence of numbers is now known as
the Eisenstein array.

In \cite{jff*09:euclid-alg}, we review Stern's paper and briefly
discuss algorithms that enumerate the elements of the Eisenstein
Array. In this document we present  several Haskell
implementations of these algorithms.  \end{abstract}


\section{The Eisenstein Array} 
Stern \cite{stern1858:rationals} describes a process (which he
attributes to Eisenstein) of generating an infinite sequence of rows
of numbers from a pair of  natural numbers $m$ and $n$.  
The \emph{zeroth} row in the sequence (``nullte
Entwickelungsreihe'') is the given pair of numbers:

\begin{displaymath}
m\ \ \ \ \ n\mbox{\ \ \ .}
\end{displaymath}

Subsequent rows are obtained by inserting between every pair of numbers the sum of the numbers.  Thus
the \emph{first} row is

\begin{displaymath}
m\ \ \ \ \ \ m{+}n\ \ \ \ \ \ n 
\end{displaymath}
and the \emph{second} row is

\begin{displaymath}
m\ \ \ \ \ \ 2{\times}m + n\ \ \ \ \ \ m{+}n\ \ \ \ \ \ m + 2{\times}n\ \ \ \ \ \ n~~. 
\end{displaymath}

The process of constructing such rows is repeated indefinitely.  The
sequence of numbers obtained by concatenating the individual rows in
order is what is now called the \emph{Eisenstein array} and denoted by
 $\mathit{Ei\/}(m{,}n)$ (see, for example, \cite[sequence
A064881]{sloane-integers}) .  Stern refers to each occurrence of a
number in rows other than the zeroth row as either a \emph{sum
element} (``Summenglied'') or a \emph{source element}
(``Stammglied'').  The sum elements are the newly added numbers.  For
example, in the first row the number $m{+}n$ is a sum element; in the
second row the number $m{+}n$ is a source element.



\section{Newman's Algorithm} 
In his paper, Stern observes two ways in which the Eisenstein array 
$\mathit{Ei\/}(1{,}1)$ (now known as Stern's diatomic series)
 enumerates the set of positive rationals.  The simplest of the two,
and the first in Stern's paper, is the sequence obtained by
considering consecutive pairs of elements ("zweigliedrige Gruppen") in
each row of the array $\mathit{Ei\/}(1{,}1)$.  (The second is what has
now become known as the Stern-Brocot tree of rationals.)  Stern proved
that the set of such pairs of numbers is exactly the set of pairs
of coprime positive numbers.  In other words, the set of all
consecutive pairs of numbers in rows of $\mathit{Ei\/}(1{,}1)$ is the
set of rational numbers in lowest form.  

Renewed interest in Stern's work has been sparked by Calkin and Wilf
\cite{Calkin-Wilf2000}. They give a recurrence relation for the $k$th
element in $\mathit{Ei\/}(1{,}1)$, and prove that it equals the number of
hyperbinary representations of $k$.  

Moshe Newman is credited with an iterative algorithm for enumerating
the rationals.  Just as Stern's analysis of the sequence of rows of
$\mathit{Ei\/}(1{,}1)$ embodies an algorithm for enumerating the
rationals, Newman's algorithm for enumerating the rationals embodies
an algorithm for enumerating the elements of $\mathit{Ei\/}(1{,}1)$
and, indeed, of $\mathit{Ei\/}(m{,}n)$ for arbitrary positive numbers
$m$ and $n$.  The purpose of the current document is to discuss
several Haskell  implementations of Newman's algorithm adapted to this
purpose.  

Newman's algorithm, in the form derived in \cite{jff*08:rationals}, is
implemented in Haskell as follows.
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{3}{@{}>{\hspre}l<{\hspost}@{}}%
\column{4}{@{}>{\hspre}l<{\hspost}@{}}%
\column{11}{@{}>{\hspre}l<{\hspost}@{}}%
\column{21}{@{}>{\hspre}c<{\hspost}@{}}%
\column{21E}{@{}l@{}}%
\column{24}{@{}>{\hspre}l<{\hspost}@{}}%
\column{29}{@{}>{\hspre}l<{\hspost}@{}}%
\column{36}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[3]{}\Varid{cwnEnum}\mathbin{::}[\mskip1.5mu \Conid{Rational}\mskip1.5mu]{}\<[E]%
\\
\>[3]{}\Varid{cwnEnum}\mathrel{=}\Varid{iterate}\;\Varid{nextCW}\ \mathrm{1}/\mathrm{1}{}\<[E]%
\\
\>[3]{}\hsindent{1}{}\<[4]%
\>[4]{}\mathbf{where}\;{}\<[11]%
\>[11]{}\Varid{nextCW}\mathbin{::}\Conid{Rational}\to \Conid{Rational}{}\<[E]%
\\
\>[11]{}\Varid{nextCW}\;\Varid{r}{}\<[21]%
\>[21]{}\mathrel{=}{}\<[21E]%
\>[24]{}\mathbf{let}\;{}\<[29]%
\>[29]{}(\Varid{a},\Varid{b}){}\<[36]%
\>[36]{}\mathrel{=}(\Varid{numerator}\;\Varid{r},\Varid{denominator}\;\Varid{r}){}\<[E]%
\\
\>[29]{}\Varid{j}{}\<[36]%
\>[36]{}\mathrel{=}\lfloor\Varid{a}/\Varid{b}\rfloor{}\<[E]%
\\
\>[24]{}\mathbf{in}\;{}\<[29]%
\>[29]{}\Varid{b}/((\mathrm{2}\mskip-4mu\times\mskip-4mu\Varid{j}\mathbin{+}\mathrm{1})\mskip-4mu\times\mskip-4mu\Varid{b}\mathbin{-}\Varid{a}){}\<[E]%
\ColumnHook
\end{hscode}\resethooks
Since each rational in the sequence \ensuremath{\Varid{cwnEnum}} is a pair of
consecutive numbers in a row of $\mathit{Ei\/}(1{,}1)$,  Newman's 
algorithm predicts that
each triple of numbers in a given row of $\mathit{Ei\/}(1{,}1)$ has
the form

\begin{displaymath}
a\ \ \ \ \ \ \ b\ \ \ \ \ \ \ (2{}\left\lfloor{\displaystyle\frac{a}{b}}\right\rfloor + 1){\times}b - a\ \ \ \ .
\end{displaymath}
(See \cite[appendix A]{jff*08:rationals} for further discussion on the
extent to which Stern anticipated this algorithm.)  

In order to adapt Newman's algorithm to enumerate 
$\mathit{Ei\/}(1{,}1)$, it suffices to determine when one row is
complete and the next begins.  This is easy since each row begins and
ends with the number $1$.  Function  \ensuremath{\Varid{newman}} below combines this fact
with \ensuremath{\Varid{cwnEnum}} in order to enumerate the elements of $\mathit{Ei\/}(1{,}1)$; 
specifically, the row is completed when the
denominator of the rational is $1$.
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{3}{@{}>{\hspre}l<{\hspost}@{}}%
\column{5}{@{}>{\hspre}l<{\hspost}@{}}%
\column{21}{@{}>{\hspre}l<{\hspost}@{}}%
\column{45}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[3]{}\Varid{newman}\mathbin{::}[\mskip1.5mu \Conid{Integer}\mskip1.5mu]{}\<[E]%
\\
\>[3]{}\Varid{newman}\mathrel{=}\Varid{concatMap}\;\Varid{dlevel}\;\Varid{cwnEnum}{}\<[E]%
\\
\>[3]{}\hsindent{2}{}\<[5]%
\>[5]{}\mathbf{where}\;\Varid{dlevel}\;\Varid{r}{}\<[21]%
\>[21]{}\mid (\Varid{denominator}\;\Varid{r})==\mathrm{1}{}\<[45]%
\>[45]{}\mathrel{=}[\mskip1.5mu \Varid{numerator}\;\Varid{r},\mathrm{1}\mskip1.5mu]{}\<[E]%
\\
\>[21]{}\mid \Varid{otherwise}{}\<[45]%
\>[45]{}\mathrel{=}[\mskip1.5mu \Varid{numerator}\;\Varid{r}\mskip1.5mu]{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
\section{Enumerating the Elements of $\mathit{Ei\/}(m{,}n)$}
In order to enumerate the elements of the array
$\mathit{Ei\/}(m{,}n)$, the main problem we have to solve is the
detection of a change of level (i.e.\ when one row is complete and the
next begins).  There are several ways to do this.  One is to
simultaneously enumerate $\mathit{Ei\/}(1{,}1)$ and use this to
control the detection process.

In the following code, the parameters $a$ and $b$ in \ensuremath{\Varid{eiloop}} sequence
through the elements of a row of  $\mathit{Ei\/}(1{,}1)$.  The end of
the row is detected when $b=1$.  (The second clause is
executed only when $b\neq 1$.)
 \begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{3}{@{}>{\hspre}l<{\hspost}@{}}%
\column{4}{@{}>{\hspre}l<{\hspost}@{}}%
\column{11}{@{}>{\hspre}l<{\hspost}@{}}%
\column{23}{@{}>{\hspre}c<{\hspost}@{}}%
\column{23E}{@{}l@{}}%
\column{26}{@{}>{\hspre}l<{\hspost}@{}}%
\column{31}{@{}>{\hspre}l<{\hspost}@{}}%
\column{34}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[3]{}\Varid{ei11}\mathbin{::}[\mskip1.5mu \Conid{Integer}\mskip1.5mu]{}\<[E]%
\\
\>[3]{}\Varid{ei11}\mathrel{=}\mathrm{1}\mathbin{:}\Varid{eiloop}\;\mathrm{1}\;\mathrm{1}{}\<[E]%
\\
\>[3]{}\hsindent{1}{}\<[4]%
\>[4]{}\mathbf{where}\;{}\<[11]%
\>[11]{}\Varid{eiloop}\;\Varid{a}\;\mathrm{1}{}\<[23]%
\>[23]{}\mathrel{=}{}\<[23E]%
\>[26]{}\mathrm{1}\mathbin{:}\mathrm{1}\mathbin{:}\Varid{eiloop}\;\mathrm{1}\;(\Varid{a}\mathbin{+}\mathrm{1}){}\<[E]%
\\
\>[11]{}\Varid{eiloop}\;\Varid{a}\;\Varid{b}{}\<[23]%
\>[23]{}\mathrel{=}{}\<[23E]%
\>[26]{}\mathbf{let}\;{}\<[31]%
\>[31]{}\Varid{k}{}\<[34]%
\>[34]{}\mathrel{=}\mathrm{2}\mskip-4mu\times\mskip-4mu\lfloor\Varid{a}/\Varid{b}\rfloor\mathbin{+}\mathrm{1}{}\<[E]%
\\
\>[26]{}\mathbf{in}\;{}\<[31]%
\>[31]{}\Varid{b}\mathbin{:}\Varid{eiloop}\;\Varid{b}\;(\Varid{k}\mskip-4mu\times\mskip-4mu\Varid{b}\mathbin{-}\Varid{a}){}\<[E]%
\ColumnHook
\end{hscode}\resethooks
Generalising to $\mathit{Ei\/}(m{,}n)$, we get the following.  (Note
that the parameters \ensuremath{\Varid{cm}} and \ensuremath{\Varid{cn}} of \ensuremath{\Varid{eiloop}} play the same role as
global constants in an imperative program; they record the initial
values of $m$ and $n$.)  The property exploited by the algorithm is that
each element of $\mathit{Ei\/}(m{,}n)$ is a linear combination of $m$
and $n$ of which the coefficients are independent of $m$ and $n$.
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{3}{@{}>{\hspre}l<{\hspost}@{}}%
\column{4}{@{}>{\hspre}l<{\hspost}@{}}%
\column{11}{@{}>{\hspre}l<{\hspost}@{}}%
\column{35}{@{}>{\hspre}l<{\hspost}@{}}%
\column{40}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[3]{}\Varid{ei}\mathbin{::}\Conid{Integer}\to \Conid{Integer}\to [\mskip1.5mu \Conid{Integer}\mskip1.5mu]{}\<[E]%
\\
\>[3]{}\Varid{ei}\;\Varid{m}\;\Varid{n}\mathrel{=}\Varid{m}\mathbin{:}\Varid{eiloop}\;\mathrm{1}\;\mathrm{1}\;\Varid{m}\;\Varid{n}\;\Varid{m}\;\Varid{n}{}\<[E]%
\\
\>[3]{}\hsindent{1}{}\<[4]%
\>[4]{}\mathbf{where}\;{}\<[11]%
\>[11]{}\Varid{eiloop}\;\Varid{a}\;\mathrm{1}\;\Varid{m}\;\Varid{n}\;\Varid{cm}\;\Varid{cn}\mathrel{=}{}\<[35]%
\>[35]{}\Varid{n}\mathbin{:}\Varid{cm}\mathbin{:}\Varid{eiloop}\;\mathrm{1}\;(\Varid{a}\mathbin{+}\mathrm{1})\;\Varid{cm}\;(\Varid{a}\mskip-4mu\times\mskip-4mu\Varid{cm}\mathbin{+}\Varid{cn})\;\Varid{cm}\;\Varid{cn}{}\<[E]%
\\
\>[11]{}\Varid{eiloop}\;\Varid{a}\;\Varid{b}\;\Varid{m}\;\Varid{n}\;\Varid{cm}\;\Varid{cn}\mathrel{=}{}\<[35]%
\>[35]{}\mathbf{let}\;{}\<[40]%
\>[40]{}\Varid{k}\mathrel{=}\mathrm{2}\mskip-4mu\times\mskip-4mu\lfloor\Varid{a}/\Varid{b}\rfloor\mathbin{+}\mathrm{1}{}\<[E]%
\\
\>[35]{}\mathbf{in}\;{}\<[40]%
\>[40]{}\Varid{n}\mathbin{:}\Varid{eiloop}\;\Varid{b}\;(\Varid{k}\mskip-4mu\times\mskip-4mu\Varid{b}\mathbin{-}\Varid{a})\;\Varid{n}\;(\Varid{k}\mskip-4mu\times\mskip-4mu\Varid{n}\mathbin{-}\Varid{m})\;\Varid{cm}\;\Varid{cn}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
We can test if the function \ensuremath{\Varid{newman}} does in fact enumerate the
elements of $\mathit{Ei\/}(1{,}1)$.  Let's compare the first $1000$
elements of both enumerations:

\medskip
\prompt{(take 1000 newman) == (take 1000 (ei 1 1))}\\
\ensuremath{\Conid{True}}\\
\prompt{(take 1000 (map (2*) newman)) == (take 1000 (ei 2 2))}\\
\ensuremath{\Conid{True}}\\
%\prompt{(take 1000 (map ((-2)*) newman)) == (take 1000 (ei (-2) (-2)))}\\
%\eval{(take 1000 (map ((-2)*) newman)) == (take 1000 (ei (-2) (-2)))}\\

The part after the prompt, $\gg$, is the Haskell code that
\texttt{ghci} executes. The result is shown in the subsequent
line. The second command shows an instance of the property:

\[
\ensuremath{\Varid{map}\;(\Varid{k}\mskip-4mu\times\mskip-4mu)\;(\Varid{ei}\;\mathrm{1}\;\mathrm{1})==\Varid{ei}\;\Varid{k}\;\Varid{k}} ~~~~~.
\]


A simplification of \ensuremath{\Varid{ei}} is obtained by replacing
 \ensuremath{\Varid{a}} and \ensuremath{\Varid{b}} by \ensuremath{\Varid{m}} and \ensuremath{\Varid{n}} in the calculation of \ensuremath{\Varid{k}} (when 
\ensuremath{\Varid{n}} is strictly positive).  (The justification for this simplification
involves induction on rows.  The induction hypothesis is that if
\ensuremath{(\Varid{a},\Varid{b},\Varid{c})} is a triple (a "driegliedrige Gruppe" in Stern's
terminology) in a given row of $\mathit{Ei\/}(1{,}1)$ and \ensuremath{(\Varid{i},\Varid{j},\Varid{k})} is
a triple in the same position in the same row of
$\mathit{Ei\/}(m{,}n)$, then \ensuremath{\lfloor\Varid{a}/\Varid{b}\rfloor\mathrel{=}\lfloor\Varid{i}/\Varid{j}\rfloor}.  (The role
of variable \ensuremath{\Varid{c}} in this hypothesis is simply to exclude the last two
elements in a row.  Indeed, the equality does not hold for these two
elements. Symmetrically, of course, \ensuremath{\lfloor\Varid{b}/\Varid{c}\rfloor\mathrel{=}\lfloor\Varid{j}/\Varid{k}\rfloor}, provided
\ensuremath{\Varid{m}} is strictly positive.) 
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{3}{@{}>{\hspre}l<{\hspost}@{}}%
\column{4}{@{}>{\hspre}l<{\hspost}@{}}%
\column{8}{@{}>{\hspre}l<{\hspost}@{}}%
\column{11}{@{}>{\hspre}l<{\hspost}@{}}%
\column{21}{@{}>{\hspre}c<{\hspost}@{}}%
\column{21E}{@{}l@{}}%
\column{24}{@{}>{\hspre}l<{\hspost}@{}}%
\column{31}{@{}>{\hspre}l<{\hspost}@{}}%
\column{35}{@{}>{\hspre}l<{\hspost}@{}}%
\column{40}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[3]{}\Varid{ei'}\mathbin{::}\Conid{Integer}\to \Conid{Integer}\to [\mskip1.5mu \Conid{Integer}\mskip1.5mu]{}\<[E]%
\\
\>[3]{}\Varid{ei'}\;\Varid{m}\;\Varid{n}{}\<[E]%
\\
\>[3]{}\hsindent{5}{}\<[8]%
\>[8]{}\mid \Varid{n}\mathbin{>}\mathrm{0}{}\<[21]%
\>[21]{}\mathrel{=}{}\<[21E]%
\>[24]{}\Varid{m}\mathbin{:}\Varid{eiloop}\;\mathrm{1}\;\mathrm{1}\;\Varid{m}\;\Varid{n}\;\Varid{m}\;\Varid{n}{}\<[E]%
\\
\>[3]{}\hsindent{5}{}\<[8]%
\>[8]{}\mid \Varid{otherwise}{}\<[21]%
\>[21]{}\mathrel{=}{}\<[21E]%
\>[24]{}\Varid{error}\;{}\<[31]%
\>[31]{}\text{\tt \char34 The~second~argument~has~to~be~strictly~positive.\char34}{}\<[E]%
\\
\>[3]{}\hsindent{1}{}\<[4]%
\>[4]{}\mathbf{where}\;{}\<[11]%
\>[11]{}\Varid{eiloop}\;\Varid{a}\;\mathrm{1}\;\Varid{m}\;\Varid{n}\;\Varid{cm}\;\Varid{cn}\mathrel{=}{}\<[35]%
\>[35]{}\Varid{n}\mathbin{:}\Varid{cm}\mathbin{:}\Varid{eiloop}\;\mathrm{1}\;(\Varid{a}\mathbin{+}\mathrm{1})\;\Varid{cm}\;(\Varid{a}\mskip-4mu\times\mskip-4mu\Varid{cm}\mathbin{+}\Varid{cn})\;\Varid{cm}\;\Varid{cn}{}\<[E]%
\\
\>[11]{}\Varid{eiloop}\;\Varid{a}\;\Varid{b}\;\Varid{m}\;\Varid{n}\;\Varid{cm}\;\Varid{cn}\mathrel{=}{}\<[35]%
\>[35]{}\mathbf{let}\;{}\<[40]%
\>[40]{}\Varid{k}\mathrel{=}\mathrm{2}\mskip-4mu\times\mskip-4mu\lfloor\Varid{m}/\Varid{n}\rfloor\mathbin{+}\mathrm{1}{}\<[E]%
\\
\>[35]{}\mathbf{in}\;{}\<[40]%
\>[40]{}\Varid{n}\mathbin{:}\Varid{eiloop}\;\Varid{b}\;(\Varid{k}\mskip-4mu\times\mskip-4mu\Varid{b}\mathbin{-}\Varid{a})\;\Varid{n}\;(\Varid{k}\mskip-4mu\times\mskip-4mu\Varid{n}\mathbin{-}\Varid{m})\;\Varid{cm}\;\Varid{cn}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
We now define the function \ensuremath{\Varid{test}}, which compares the first $1000$
elements of two enumerations of $\mathit{Ei\/}(m{,}n)$, with
$0{\leq}m{\leq}x$ and $1{\leq}n{\leq}x$ :
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{3}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[3]{}\Varid{test}\;\Varid{f}\;\Varid{g}\;\Varid{x}\mathrel{=}\Varid{and}\;[\mskip1.5mu \Varid{take}\;\mathrm{1000}\;(\Varid{f}\;\Varid{m}\;\Varid{n})==\Varid{take}\;\mathrm{1000}\;(\Varid{g}\;\Varid{m}\;\Varid{n})\mid \Varid{m}\leftarrow [\mskip1.5mu \mathrm{0}\mathinner{\ldotp\ldotp}\Varid{x}\mskip1.5mu],\Varid{n}\leftarrow [\mskip1.5mu \mathrm{1}\mathinner{\ldotp\ldotp}\Varid{x}\mskip1.5mu]\mskip1.5mu]{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
We can use \ensuremath{\Varid{test}} to see if the first $1000$ elements of \ensuremath{\Varid{ei}\;\Varid{m}\;\Varid{n}} and \ensuremath{\Varid{ei'}\;\Varid{m}\;\Varid{n}},
for $0{\leq}m{\leq}100$ and $1{\leq}n{\leq}100$, are the same (we are testing $10100$ pairs).

\medskip
\prompt{test ei ei' 100}\\
\ensuremath{\Conid{True}}\\ %eval takes too long! But I've checked it (02/03/2009)
%\eval{test ei ei' 100}

Building on \ensuremath{\Varid{ei'}}, a further transformation is to replace the test for
the end of a row in the sequence.  This has been done in the
 function \ensuremath{\Varid{extnewman}}, defined below.  It is the same as \ensuremath{\Varid{ei}}, but it
replaces variables \ensuremath{\Varid{a}} and \ensuremath{\Varid{b}} by variable \ensuremath{\Varid{r}} which counts the rows.
The last two elements in row \ensuremath{\Varid{r}} of $\mathit{Ei\/}(cm{,}cn)$ are
\ensuremath{\Varid{cm}\mathbin{+}\Varid{r}\mskip-4mu\times\mskip-4mu\Varid{cn}} and \ensuremath{\Varid{cn}}, and the first two elements in row \ensuremath{\Varid{r}\mathbin{+}\mathrm{1}} are \ensuremath{\Varid{cm}}
and \ensuremath{(\Varid{r}\mathbin{+}\mathrm{1})\mskip-4mu\times\mskip-4mu\Varid{cm}\mathbin{+}\Varid{cn}}.
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{3}{@{}>{\hspre}l<{\hspost}@{}}%
\column{4}{@{}>{\hspre}l<{\hspost}@{}}%
\column{8}{@{}>{\hspre}l<{\hspost}@{}}%
\column{11}{@{}>{\hspre}l<{\hspost}@{}}%
\column{20}{@{}>{\hspre}c<{\hspost}@{}}%
\column{20E}{@{}l@{}}%
\column{23}{@{}>{\hspre}l<{\hspost}@{}}%
\column{29}{@{}>{\hspre}l<{\hspost}@{}}%
\column{41}{@{}>{\hspre}l<{\hspost}@{}}%
\column{44}{@{}>{\hspre}l<{\hspost}@{}}%
\column{49}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[3]{}\Varid{extnewman}\mathbin{::}\Conid{Integer}\to \Conid{Integer}\to [\mskip1.5mu \Conid{Integer}\mskip1.5mu]{}\<[E]%
\\
\>[3]{}\Varid{extnewman}\;\Varid{cm}\;\Varid{cn}{}\<[E]%
\\
\>[3]{}\hsindent{5}{}\<[8]%
\>[8]{}\mid \Varid{cn}\mathbin{>}\mathrm{0}{}\<[20]%
\>[20]{}\mathrel{=}{}\<[20E]%
\>[23]{}\Varid{cm}\mathbin{:}\Varid{loop}\;\mathrm{0}\;\Varid{cm}\;\Varid{cn}\;\Varid{cm}\;\Varid{cn}{}\<[E]%
\\
\>[3]{}\hsindent{5}{}\<[8]%
\>[8]{}\mid \Varid{otherwise}\mathrel{=}{}\<[23]%
\>[23]{}\Varid{error}\;\text{\tt \char34 The~second~argument~has~to~be~strictly~positive.\char34}{}\<[E]%
\\
\>[3]{}\hsindent{1}{}\<[4]%
\>[4]{}\mathbf{where}\;{}\<[11]%
\>[11]{}\Varid{loop}\;\Varid{r}\;\Varid{m}\;\Varid{n}\;\Varid{cm}\;\Varid{cn}{}\<[29]%
\>[29]{}\mid ((\Varid{m}==(\Varid{cm}\mathbin{+}\Varid{r}\mskip-4mu\times\mskip-4mu\Varid{cn}))\mathrel{\wedge}(\Varid{n}==\Varid{cn}))\mathrel{=}{}\<[E]%
\\
\>[29]{}\hsindent{12}{}\<[41]%
\>[41]{}\Varid{n}\mathbin{:}\Varid{cm}\mathbin{:}\Varid{loop}\;(\Varid{r}\mathbin{+}\mathrm{1})\;\Varid{cm}\;((\Varid{r}\mathbin{+}\mathrm{1})\mskip-4mu\times\mskip-4mu\Varid{cm}\mathbin{+}\Varid{cn})\;\Varid{cm}\;\Varid{cn}{}\<[E]%
\\
\>[29]{}\mid \Varid{otherwise}\mathrel{=}{}\<[44]%
\>[44]{}\mathbf{let}\;{}\<[49]%
\>[49]{}\Varid{k}\mathrel{=}\mathrm{2}\mskip-4mu\times\mskip-4mu\lfloor\Varid{m}/\Varid{n}\rfloor\mathbin{+}\mathrm{1}{}\<[E]%
\\
\>[44]{}\mathbf{in}\;{}\<[49]%
\>[49]{}\Varid{n}\mathbin{:}\Varid{loop}\;\Varid{r}\;\Varid{n}\;(\Varid{k}\mskip-4mu\times\mskip-4mu\Varid{n}\mathbin{-}\Varid{m})\;\Varid{cm}\;\Varid{cn}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
We can do a similar test for \ensuremath{\Varid{extnewman}} as we did for \ensuremath{\Varid{ei'}}:

\medskip
\prompt{test ei extnewman 100}\\
\ensuremath{\Conid{True}} %eval takes too long! But I've checked it (02/03/2009)
%\eval{test ei extnewman 100}

\section{The Online Encyclopedia of Integer Sequences} In this
section, we show how we can use the functions from the Haskell module
\ensuremath{\Conid{\Conid{Math}.OEIS}}\footnote{To run this literate Haskell file, you need to
have the module \ensuremath{\Conid{\Conid{Math}.OEIS}} installed. You can download it from
\url{http://hackage.haskell.org/cgi-bin/hackage-scripts/package/oeis}.}
to search for occurrences of the Eisenstein array in the Online
Encyclopedia of Integer Sequences (OEIS) \cite{sloane-integers}.

We start by defining the number of elements, \ensuremath{\Varid{numElems}}, that we want
to send to the OEIS, and a function that converts a list
$[\,x_1,\cdots,x_n\,]$ to the string $"\,x_1,\cdots,x_n\,"$:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{3}{@{}>{\hspre}l<{\hspost}@{}}%
\column{13}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[3]{}\Varid{numElems}{}\<[13]%
\>[13]{}\mathbin{::}\Conid{Int}{}\<[E]%
\\
\>[3]{}\Varid{numElems}{}\<[13]%
\>[13]{}\mathrel{=}\mathrm{20}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{3}{@{}>{\hspre}l<{\hspost}@{}}%
\column{16}{@{}>{\hspre}l<{\hspost}@{}}%
\column{19}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[3]{}\Varid{list2string}{}\<[16]%
\>[16]{}\mathbin{::}(\Conid{Show}\;\Varid{a})\Rightarrow [\mskip1.5mu \Varid{a}\mskip1.5mu]\to \Conid{String}{}\<[E]%
\\
\>[3]{}\Varid{list2string}{}\<[16]%
\>[16]{}\mathrel{=}{}\<[19]%
\>[19]{}\Varid{init}\mathbin{\circ}\Varid{tail}\mathbin{\circ}\Varid{show}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
The following function, \ensuremath{\Varid{oeis}}, inputs two integer
numbers, \ensuremath{\Varid{m}} and \ensuremath{\Varid{n}},  computes the list of the first \ensuremath{\Varid{numElems}} of \ensuremath{\Varid{ei}\;\Varid{m}\;\Varid{n}}, transforms the list  into a string and checks if it exists in the
OEIS. It prints the description of the sequence, together with its
reference.
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{3}{@{}>{\hspre}l<{\hspost}@{}}%
\column{5}{@{}>{\hspre}l<{\hspost}@{}}%
\column{12}{@{}>{\hspre}l<{\hspost}@{}}%
\column{13}{@{}>{\hspre}l<{\hspost}@{}}%
\column{16}{@{}>{\hspre}l<{\hspost}@{}}%
\column{20}{@{}>{\hspre}l<{\hspost}@{}}%
\column{35}{@{}>{\hspre}l<{\hspost}@{}}%
\column{38}{@{}>{\hspre}l<{\hspost}@{}}%
\column{47}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[3]{}\Varid{oeis}{}\<[13]%
\>[13]{}\mathbin{::}\Conid{Integer}\to \Conid{Integer}\to \Conid{IO}\;(){}\<[E]%
\\
\>[3]{}\Varid{oeis}\;\Varid{m}\;\Varid{n}{}\<[13]%
\>[13]{}\mathrel{=}{}\<[16]%
\>[16]{}\mathbf{do}\;{}\<[20]%
\>[20]{}\Varid{s}\leftarrow \Varid{searchSequence\char95 IO}\mathbin{\circ}\Varid{list2string}\mathbin{\circ}(\Varid{take}\;\Varid{numElems})\ \Varid{ei}\;\Varid{m}\;\Varid{n}{}\<[E]%
\\
\>[20]{}\Varid{r}\leftarrow \Varid{getDataSeq}\;\Varid{s}{}\<[E]%
\\
\>[20]{}\Varid{putStrLn}\ \text{\tt \char34 Ei(\char34}\plus \Varid{show}\;\Varid{m}\plus \text{\tt \char34 ,\char34}\plus \Varid{show}\;\Varid{n}\plus \text{\tt \char34 ):\char92 n\char92 t\char34}\plus \Varid{r}{}\<[E]%
\\
\>[3]{}\hsindent{2}{}\<[5]%
\>[5]{}\mathbf{where}\;{}\<[12]%
\>[12]{}\Varid{getDataSeq}{}\<[35]%
\>[35]{}\mathbin{::}\Conid{Maybe}\;\Conid{OEISSequence}\to \Conid{IO}\;\Conid{String}{}\<[E]%
\\
\>[12]{}\Varid{getDataSeq}\;\Conid{Nothing}{}\<[35]%
\>[35]{}\mathrel{=}{}\<[38]%
\>[38]{}\Varid{return}\;\text{\tt \char34 Sequence~not~found.\char34}{}\<[E]%
\\
\>[12]{}\Varid{getDataSeq}\;(\Conid{Just}\;\Varid{seq}){}\<[35]%
\>[35]{}\mathrel{=}{}\<[38]%
\>[38]{}\Varid{return}\ (\Varid{description}\;\Varid{seq}){}\<[E]%
\\
\>[38]{}\hsindent{9}{}\<[47]%
\>[47]{}\plus \text{\tt \char34 ~(~\char34}{}\<[E]%
\\
\>[38]{}\hsindent{9}{}\<[47]%
\>[47]{}\plus (\Varid{concatMap}\;(\plus \text{\tt \char34 ~\char34})\;(\Varid{catalogNums}\;\Varid{seq})){}\<[E]%
\\
\>[38]{}\hsindent{9}{}\<[47]%
\>[47]{}\plus \text{\tt \char34 )\char34}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
As an example, here is the output for the sequence \ensuremath{\Varid{ei}\;\mathrm{1}\;\mathrm{1}}:

\medskip
\prompt{oeis 1 1}
\noindent\begin{tabbing}\tt
~Ei\char40{}1\char44{}1\char41{}\char58{}\\
\tt ~~~~~~~~~Triangle~T\char40{}n\char44{}k\char41{}~\char61{}~denominator~of~fraction~in~k\char45{}th~term~of~n\char45{}th~row~of\\
\tt ~variant~of~Farey~series\char46{}~This~is~also~Stern\char39{}s~diatomic~array~read~by\\
\tt ~rows~\char40{}version~1\char41{}\char46{}~\char40{}~A049456~\char41{}
\end{tabbing}
%\eval{oeis 1 1}

Finally, using the function \ensuremath{\Varid{oeis}}, we have searched which instances of $\mathit{Ei\/}(m{,}n)$, with $0{\leq}m{<}100$ and $0{<}n{<}100$, are listed in the OEIS.  The occurrences found are listed below:

\begin{description}
\item{$\mathit{Ei\/}(0,1)$:}
        Triangle read by rows: T(n,k) = numerator of fraction in k-th term of n-th row of variant of Farey series. ( A049455 )
\item{$\mathit{Ei\/}(1,0)$:}
        Stern's diatomic array read by rows (version 2). ( A070878 )
\item{$\mathit{Ei\/}(1,1)$:}
        Triangle T(n,k) = denominator of fraction in k-th term of n-th row of variant of Farey series. This isalso Stern's diatomic array read by rows (version 1). ( A049456 )
\item{$\mathit{Ei\/}(1,2)$:}
        Eisenstein array $\mathit{Ei\/}(1,2)$. ( A064881 )
\item{$\mathit{Ei\/}(1,3)$:}
        Eisenstein array $\mathit{Ei\/}(1,3)$. ( A064883 )
\item{$\mathit{Ei\/}(2,1)$:}
        Eisenstein array $\mathit{Ei\/}(2,1)$. ( A064882 )
\item{$\mathit{Ei\/}(2,3)$:}
        Eisenstein array $\mathit{Ei\/}(2,3)$. ( A064886 )
\item{$\mathit{Ei\/}(3,1)$:}
        Eisenstein array $\mathit{Ei\/}(3,1)$. ( A064884 )
\item{$\mathit{Ei\/}(3,2)$:}
        Eisenstein array $\mathit{Ei\/}(3,2)$. ( A064885 ) 
\end{description}



\bibliographystyle{plain}
\bibliography{math,jff,bibliogr}
\end{document}