\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}
\usepackage{colortbl}
\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}
\newtheorem{innercustomthm}{Theorem}
\newenvironment{customthm}[1]
{\renewcommand\theinnercustomthm{#1}\innercustomthm}
{\endinnercustomthm}
\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
Iterations of the Words-to-Numbers Function
}
\vskip 1cm
\large
Matthew E. Coppenbarger \\
School of Mathematical Sciences \\
85 Lomb Memorial Drive \\
Rochester Institute of Technology \\
Rochester, NY 14623-5603 \\
USA \\
\href{mailto:mecsma@rit.edu}{\tt mecsma@rit.edu}
\end{center}
\vskip .2in
\begin{abstract}
The {\em Words-to-Numbers} function takes a nonnegative integer and maps it to the number of characters required to spell the number in English.
For each $k=0,1,\dots,8$, we determine the minimal nonnegative integer $n$ such that the iterates of $n$ converge to the fixed point (through the {\em Words-to-Numbers} function) in exactly
$k$ iterations.
Our travels take us from some simple answers, to an etymology of the names of large numbers, to Conway/Guy's established system representing the name of any integer, and finally use generating functions to arrive at a very large number.
\end{abstract}
\section{Introduction and initial definitions} \label{section:intro}
The idea for the problem originates in a 1965 book \cite[p.\ 243]{borgmann65} by recreational linguistics icon Dmitri Borgmann (1927--85) and in a 1966 article \cite{gardner66} by another icon, recreational mathematician Martin Gardner (1914--2010).
Gardner's article appears again in a book \cite[pp.\ 71--72, 265--267]{gardner90} containing reprinted Gardner articles from Scientific American along with his comments on his reader's responses.
Both Borgmann and Gardner identify the only English number that requires exactly the same number of characters to spell the number as the number represents.
Borgmann goes further by identifying numbers in 16 other languages with this property.
Borgmann calling such numbers {\em truthful} and Gardner calling them {\em honest}.
The concept was expanded in 1972 by IBM computer scientists Gosper and Schroeppel in the unpublished HAKMEM (short for ``hacker's memo'') report \cite[item 134]{bgs} by defining a function that counts the number of
characters in the English name of any representation of a number and iterating through the function until a cycle is reached.
The fixed points of such a function would be truthful/honest numbers.
In 1974, Kravitz \cite{kravitz} generalized the function and applied it to 17 other languages, identifying the fixed points and cycles generated by the iterates of elements of the domain.
For purposes of this paper, we will only focus on the English version.
The name of this function, {\em Words-to-Numbers}, was coined by Ecker in 1986 or 1987.
As cited by Zerger \cite{zerger}, the name is given in newsletters published by Ecker (\cite{ecker86} or \cite{ecker87}), but are no longer available.
Some of the material in the newsletters, which includes the {\em Words-to-Numbers} function, is summarized by Ecker in an article for a tribute book to Gardner \cite{ecker99}.
The {\em Words-to-Numbers} function, $\mathcal{W}:\mathbb{N} \to \mathbb{Z}^+$, is the very simple process of
taking a nonnegative integer $n$ and mapping it to the positive integer representing the number of characters required to spell $n$ in English with the conventions ($a$) use only a space to separate each word (no commas, hyphens, nor $``\verb"and""$s) and ($b$) include each space in the character count.
In contrast, Sloane \cite{sloan} lists sequences \seqnum{A005589} and \seqnum{A227290} that have similar definitions but do not count the space.
Since it was Ecker's article \cite{ecker99} that motivated this paper, we use Ecker's initial intent to include the space in the count.
For example, $\mathcal{W}(126) = 22$ since $``\verb"one hundred twenty six""$ requires a string of 22 characters to spell.
The {\em iteration sequence} of $n$ is the sequence of the iterates of $\mathcal{W}$ generated by $n$ (the {\em seed}).
To illustrate, the iteration sequence of 126 is
\begin{equation} \label{eq:iterates}
126 \to 22 \to 10 \to 3 \to 5 \to 4 \to 4 \to \cdots,
\end{equation}
indicating that 4 is the answer to Borgmann/Gardner's initial question.
Moreover, the {\em height} of the iteration sequence generated by $n$, denoted $\mathcal{W}^\#(n)$, is the number of iterations of $\mathcal{W}$ that must be applied to $n$ until the iteration sequence reaches either a fixed point or a cycle.
We can see from \eqref{eq:iterates} that $\mathcal{W}^\#(126) = 5$ since 126 requires five iterations of $\mathcal{W}$ until arriving at the fixed point.
One template for analyzing the iteration dynamics of discrete functions is given by Guy \cite[problem E34]{guy}.
The function used takes any positive integer and maps it to the sum of the squares of its decimal digits.
Guy considers only the subset of the domain whose elements iterate to 1 (defined as the set of {\em happy numbers}).
Among the deluge of questions proposed, he asks, for a nonnegative integer $k$, to determine the least nonnegative integer that converges to 1 in exactly $k$ iterations.
Solutions to problem E34 are partially answered by Grundman and Teeple \cite{grundman} and Cai and Zhaou \cite{cai} and are summarized as \seqnum{A001273} by Sloane \cite{sloan}.
The main purpose of this paper is to do the same for $\mathcal{W}$, but we need to know that the fixed point of $\mathcal{W}$ identified in (\ref{eq:iterates}) is the only one and that there are not any cycles of
length greater than one.
We summarize this as
\begin{theorem} \label{convergence}
All iteration sequences through $\mathcal{W}$ converge to 4.
\end{theorem}
A partial proof of the theorem is given in $\S$\ref{section:zerotosix} and completed in $\S$\ref{section:completion} after choosing a numeration scheme valid for all integers.
Using $\mathcal{W}$, we can naturally partition the domain by defining, for each nonnegative integer $k$, the $k$-th {\em iterated set} of $\mathcal{W}$, denoted $I_k$, to be the subset of the domain consisting of those elements that map the fixed point in exactly $k$ iterations.
Using our previous example again, $126 \in I_5$.
We let $$\tau_k := \min(I_k)$$ denote the minimum value that maps to the fixed point in exactly $k$ iterations.
Hence the definition implies that $\tau_5 \le 126$.
Taking inspiration from Guy, we establish the values of $\tau_k$ through $\mathcal{W}$ for as many values of $k$ that are possible.
(This iteration sequence is given as \seqnum{A301408} by Sloane \cite{sloan}.)
We will see that $\tau_0$ through $\tau_6$ are fairly simple, $\tau_7$ is a little more difficult, and the material needed to ascertain $\tau_8$ encompasses over half of this article.
In addition to the sets $\mathbb{N}$ for the nonnegative integers and $\mathbb{Z}^+$ for the positive integers, we use $\mathbb{N}_b := \{0,1,2,\dots, b-1 \}$, where $b \in \mathbb{Z}^+$, to represent the first $b$ nonnegative integers.
Most uses of $\mathbb{N}_b$ will be to construct the base-$b$ expansion of an integer.
\section{Zero through six iterations} \label{section:zerotosix}
There are 29 words that are needed to name any nonnegative integer less than 1000 and are listed in Table \ref{table:words}.
We use them to derive the first seven integers of minimal height.
\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|}
\hline
\rowcolor[gray]{0.85} \bf Strings &\bf Length \\
\hline
``\verb"one"'',
``\verb"two"'',
``\verb"six"'',
``\verb"ten"'' & 3 \\
\hline
``\verb"zero"'',
``\verb"four"'',
``\verb"five"'',
``\verb"nine"'' & 4 \\
\hline
``\verb"three"'',
``\verb"seven"'',
``\verb"eight"'',
``\verb"forty"'',
``\verb"fifty"'',
``\verb"sixty"'' & 5 \\
\hline
``\verb"eleven"'',
``\verb"twelve"'',
``\verb"twenty"'',
``\verb"thirty"'',
``\verb"eighty"'',
``\verb"ninety"'' & 6 \\
\hline
``\verb"fifteen"'',
``\verb"sixteen"'',
``\verb"seventy"'',
``\verb"hundred"'' & 7 \\
\hline
``\verb"thirteen"'',
``\verb"fourteen"'',
``\verb"eighteen"'',
``\verb"nineteen"'' & 8 \\
\hline
``\verb"seventeen"'' & 9 \\
\hline
\end{tabular}
\caption{The words needed for naming all nonnegative integers
less than 1000 grouped by length.} \label{table:words}
\end{center}
\end{table}
For small values in the domain, the iteration structure of $\mathcal{W}$ is chaotic and finding the number that is of minimal height does not become predictable until height 6.
So our analysis begins by drawing Figure \ref{fi:graph}, a digraph representation of $\mathcal{W}$ for a particular sampling of elements in the first six iterated sets.
\begin{figure}[ht]
\begin{centering}
\includegraphics[width=4.5in]{WTN_figure.eps}
\caption{A partial digraph representation of the first six
iterated sets of $\mathcal{W}$.} \label{fi:graph}
\end{centering}
\end{figure}
Since all nonnegative integers less than 29 are included in Figure \ref{fi:graph} or listed in Table \ref{table:words}, then we can easily see that
\begin{lemma}
The least nonnegative integers of heights 0 through 5 through $\mathcal{W}$ are, respectively,
$\tau_0 = 4, \tau_1 = 0, \tau_2 = 3, \tau_3 = 1, \tau_4 = 11$, and $\tau_5 = 23$.
\end{lemma}
The determination of $\tau_6$ will require a number of preliminary calculations.
Given an integer $n$ in the $k$-th iterated set $I_k$, the set of preimages of $n$, denoted $\mathcal{W}^{-1}(n)$, must be a subset of $I_{k+1}$.
So we need to find the smallest integer in each of the preimage sets of elements in $I_5 = \{ 23, 24, 25, 27, \dots \}$, but only an exhaustive search using Table \ref{table:words} will produce these numbers.
We will see that similar computations must be performed for each iteration above six, so all minimal preimages less than 1000 are provided here.
Formally, for $n \in \mathbb{N}$, define $T_n := \min(\mathcal{W}^{-1}(n))$ to be the minimum of all nonnegative integers that map to $n$ through $\mathcal{W}$.
The results have been compiled in Table \ref{table:tn}.
\begin{table}[ht]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|}
\cline{1-2} \cline{4-5} \cline{7-8} \cline{10-11}
\cline{1-2} \cline{4-5} \cline{7-8} \cline{10-11}
\rule{-0.5ex}{2.5ex}
\cellcolor[gray]{0.85} $\boldsymbol{n}$
& \cellcolor[gray]{0.85} $\boldsymbol{T_n}$
&
& \cellcolor[gray]{0.85} $\boldsymbol{n}$
& \cellcolor[gray]{0.85} $\boldsymbol{T_n}$
&
& \cellcolor[gray]{0.85} $\boldsymbol{n}$
& \cellcolor[gray]{0.85} $\boldsymbol{T_n}$
&
& \cellcolor[gray]{0.85} $\boldsymbol{n}$
& \cellcolor[gray]{0.85} $\boldsymbol{T_n}$ \\
\cline{1-2} \cline{4-5} \cline{7-8} \cline{10-11}
1 & {\it undefined} & & 8 & 13 & & 15 & 101 & & 22 & 121 \\
2 & {\it undefined} & & 9 & 17 & & 16 & 104 & & 23 & 124 \\
3 & 1 & & 10 & 21 & & 17 & 103 & & 24 & 123 \\
4 & 0 & & 11 & 24 & & 18 & 111 & & 25 & 173 \\
5 & 3 & & 12 & 23 & & 19 & 115 & & 26 & 323 \\
6 & 11 & & 13 & 73 & & 20 & 113 & & 27 & 373 \\
7 & 15 & & 14 & $\ge 1000$ & & 21 & 117 & & 28+ & $\ge 1000$ \\
\cline{1-2} \cline{4-5} \cline{7-8} \cline{10-11}
\end{tabular}
\caption{The smallest nonnegative integer $T_n$ that requires exactly
$n$ characters to spell.} \label{table:tn}
\end{table}
The table indicates that the preimage of any $n \ge 28$ must consist of more than three decimal digits.
Thus evaluating $\tau_6$ reduces to knowing the preimages of the first four elements in $I_5$.
That is,
\[
\tau_6
= \min(I_6)
= \min \{ T_{23},T_{24},T_{25},T_{27} \}
= 123.
\]
We summarize this result as
\begin{lemma}
The least nonnegative integer of height 6 through $\mathcal{W}$ is $\tau_6 = 123$.
\end{lemma}
Table \ref{table:tn} also serves an additional purpose in that it can partially answer the theorem given earlier that all iteration sequences converge to 4.
\begin{proof}[Partial proof of Theorem \ref{convergence}]
Initially, we observe by Figure \ref{fi:graph} that all seeds less than 11 converge to 4.
We also note from Table \ref{table:tn} that $n < T_n$ for all $n$ from 6 to 28.
Consider a seed $m$ such that $11 \le m < 1000$.
Since both $m$ and $T_{\mathcal{W}(m)}$ map to $\mathcal{W}(m)$ and $T_{\mathcal{W}(m)}$ is the smallest integer that maps to $\mathcal{W}(m)$, then $m \ge T_{\mathcal{W}(m)} > \mathcal{W}(m)$, indicating that iterations of $\mathcal{W}$ are decreasing for those values of $m$.
Thus all iteration sequences with seed $m \in \mathbb{N}_{1000}$ must invariably converge to 4.
\end{proof}
The proof is completed in $\S$\ref{section:completion}.
\section{An etymology of the names of large numbers -- and a choice}
To determine $\tau_7$, we need the name designation of three more numbers: $10^3$, $10^6$, and $10^9$.
The first two ({\it thousand} and {\it million}) are widely accepted designations, but the third is not.
To explain, we step back to the last quarter of the 15th century in France to when these names were first defined and follow their usage and the evolution of their meaning.
One of the first references of the names of numbers larger than $10^6$ was in 1484 by French mathematician and physician Nicolas Chuquet (c.1445--c.1488) in his manuscript {\em Triparty en la science des nombres} ({\em The Science of Numbers in Three Parts}).
The beginning of the first part includes definitions of the words {\em billion, trillion, quadrillion, quillion, sixlion, septillion, ottillion,} and {\it nonillion} as the name designations of, respectively, $10^{12}$, $10^{18}$, $10^{24}$, and so on, up to $10^{54}$, thus grouping the decimal digits in {\em periods} of six.
(These spellings are from the English translation of Chuquet's manuscript by Flegg, Hay, and Moss \cite[p.\ 29]{flegg}.)
{\em Million}, which is of Italian origin, had been in usage in the previous centuries prior to Chuquet.
The idea of adding Latin cardinal numbers as prefixes to {\em -illion} was not new but the origin is, nonetheless, now attributed to Chuquet.
In 1475, French mathematician Jehan Adam includes the words {\em million, bymillion,} and {\em trimillion} in his manuscript {\em Traicte en arismeticque}.
It is speculated by Flegg, Hay, and Moss \cite[p.\ 339]{flegg} that Chuquet and Adam may have seen the definitions from the same source.
Both mention Bertheleny de Romanis as an inspiration, but none of his work has survived.
Chuquet's manuscript was discovered by French scholar Aristide Marre (1823--1918) and not published until 1880 and 1881 \cite{marre1, marre2, marre3}, making Chuquet's contribution effectively unknown to the mathematical community for nearly four centuries.
Notwithstanding, the mathematics contained in the {\em Triparty} was known even while unpublished because, after Chuquet's death, possession passed to fellow Frenchman Estinenne de la Roche (1470--1530).
A substantial portion of the contents of Chuquet's man\-u\-script was more widely disseminated with the publication of the arithmetic text {\em Larismethique nouellement compose} in 1520 by de la Roche who copied nearly verbatim large swaths of Chuquet's work, including the name designation of numbers given above.
The history of Chuquet's {\em Triparty} and its impact on the mathematical community are stories unto themselves.
Only one copy has survived and it is the same one owned by de la Roche -- his notes are in the margins.
Flegg, Hay, and Moss \cite{flegg} trace the manuscript from de la Roche to Marre and provide a comprehensive analysis of Chuquet's mathematics and its influence including an explanation of the conditions for which it was permissable to plagiarize in 15th/16th century France.
Additional history about de la Roche's role in the legacy of Chuquet is provided by Moss \cite{moss}.
In 1690, over 200 years after the {\em Triparty} was written, the name designations, with the same definitions as given by Chuquet/de la Roche, reappeared in the classical work {\em An Essay Concerning Human Understanding} \cite[II-16]{locke} by the English philosopher John Locke (1632--1704).
The spellings used by Locke are identical to the ones used today with one exception: Locke used {\em quatrillion} instead of today/Chuquet's {\em quadrillion}.
The vast majority of subsequent authors recognized Locke's mistake and used the latter representation.
As the {\em Essay} was Locke's most celebrated work and he presented the name designations without attribution, the {\em Essay} was cemented as the standard for numeration.
Locke's naming convention became known as the {\em English method} of numeration, despite being of French origin.
How the terms came to Locke has never been definitely established, but one possible link between de la Roche and Locke is provided by Moss \cite{moss}:
Locke's geometry professor at Oxford, John Wallis (1616--1703), was aware of de la Roche through French monk and mathematician Jean Bu\'{e}ton (1492--c.1564) who wrote {\em Logistica, quae et arithmetica vulgo dicitur} in 1559 and cited de la Roche.
It is at this point where the definitions, and hence $\mathcal{W}$, become ill-defined.
Mathematicians and educators in France in the late 18th century grouped the decimal digits in periods of three but used the same name designations as given by Locke.
They defined {\em billion} through {\em nonillion} as the name designations for $10^9, 10^{12}, \dots,10^{30}$.
As noted by historian Florian Cajori (1859--1930) \cite[p.\ 49]{cajori}, France went through a revitalization of mathematics and mathematical education that originated with Swiss education reformer Johann Pestalozzi (1746--1827).
Many mathematicians and educators in the United States were influenced by this reform and among the changes adopted was this new method (and referred to as the {\em French method} of numeration) replacing the English method.
The earliest use of the French method in the United States was Patterson's 1805 edition of Dilworth's {\em School-master's Assistant} (as observed by Cajori \cite[p.\ 108]{cajori}) with many arithmetic textbooks rapidly transitioning to this new method between 1825 and 1830.
We note that this 1805 publication date is in contrast with mathematician David E. Smith (1860--1944) who writes in one of his more popular history books \cite[p.\ 86]{smithd} that the earliest use of the French method in the American colonies is an arithmetic textbook \cite{greenwood} by Harvard professor Isaac Greenwood (1702--45) in 1729.
In fact, Greenwood used the English method and cited it as ``Mr. Lock's [sic] Method of Numeration''.
Greenwood's textbook was published anonymously and was the first arithmetic textbook written in colonial America.
Greenwood himself was the first Hollis Chair of Mathematics and Natural Philosophy at Harvard (and the position is still occupied today after nearly 300 years).
He is also noteworthy to be the first person to teach calculus in the colonies \cite{leonard}.
Sadly, his academic career ended when he was censured in 1737 for drunkenness and dismissed in the next year.
Acceptance of the French method in the United States may have been popular, but it was not so universally.
A noteworthy dissent was by Elijah Slack (1784--1866), a mathematician, chemist, and Presbeterian minister (and served early in his academic career as vice president of Princeton College from 1812 to 1817, a very tumultuous time in its history when the students openly revolted against the administration).
After relocating to Ohio and much later in his career, Slack wrote a remarkable 1853 paper \cite{slack} where he presented a passionate defense of the English method.
The paper, however, failed to resonate with the Pestalozzian reformers, perhaps because the message was lost since the first portion of the paper consisted of Slack's proclamation of the divine origin of the decimal digits.
It is more likely, however, that Slack failed to dissuade the movement of the numeration community toward the French method because it was already over -- the last use of the English method to appear in the United States in an arithmetic textbook was three years earlier in Gibson's revised edition of Fowler's {\em Youth's Assistant} (as noted by Cajori \cite[p.\ 108]{cajori}).
To complicate matters further, a movement began in parts of Europe to use the suffix {\em -illiard} (first proposed by French mathematician and poet Jacques Pelletier du Mans (1517--83)) for the intermediate name designations of $10^9$, $10^{15}$, $10^{21}$, etc.\ (while still using the English method for the name designations for $10^{12}$, $10^{18}$, etc.).
It was slowly adopted in many European countries and is referred to as the {\em Traditional European} naming designation.
The French, finally realizing their earlier error in the 18th century, moved to the Traditional European naming designation in the 1960s.
The English method is now called the {\em Traditional British} naming convention.
But England, citing influence by the United States, officially switched to the French method which is now called the {\em U.S. and Modern British} naming convention.
Overall, there are three naming conventions for large numbers; they are given in Table \ref{table:scale} and make $\mathcal{W}$ ill-defined for all $n \ge 10^9$.
As it is not feasible to present the remaining two iterations for all three naming conventions, we simplify by choosing only one.
Since $\mathcal{W}$ has been defined as the length of a number spelled in English, we use the system prevalent with most English-speaking countries: the U.S. and Modern British naming convention.
\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|}
\hline
\rowcolor[gray]{0.85}
\rule{-0.5ex}{2.5ex}
\bf Naming Convention & \bf Name of $\boldsymbol{10^9}$ \\
\hline
U.S. and Modern British (French method) & {\em Billion} \\
Traditional British (English method) & {\em Thousand Million} \\
Traditional European & {\em Milliard} \\
\hline
\end{tabular}
\caption{The three different naming conventions and the corresponding names of $10^9$.} \label{table:scale}
\end{center}
\end{table}
\section{Representing integers}
We begin this section with a well-known result of the unique representation of an integer in a chosen base $b$.
\begin{theorem} \label{t1}
Given $n,b \in \mathbb{N}$ with $b>1$, there exist unique
integers $\xi_1,\xi_2,\dots,\xi_\delta \in \mathbb{N}_b = \{ 0, 1, \dots, b-1 \}$
such that $n = \sum_{k=1}^\delta \xi_k b^{k-1}$
{\rm (}with $\xi_\delta \ne 0$ if $n > 0$ and $\delta = 1$ if
$n = 0${\rm)}.
\end{theorem}
We shall refer to each $\xi_k$ as a {\em base-b digit} of $n$ (or, more specifically, the {\em k-th base-b digit} of $n$) with $\xi_\delta$ the {\em leading base-b digit} and, for $n > 0$,
\[
\delta \equiv \delta_b(n) = 1 + \lfloor \log_bn \rfloor
\]
(where $\lfloor \cdot \rfloor$ is the floor function) is the number of base-$b$ digits of $n$.
The proof of Theorem \ref{t1} uses the division algorithm and the well-ordering principle and is omitted since it can be found in many introductory textbooks in discrete mathematics (such as Kolman, Busby, and Ross \cite[p.\ 27]{kbr}).
We call the summation representation of $n$ in Theorem \ref{t1} the {\em base-b expansion} of $n$ and use the notation
\begin{equation} \notag
n =
\big(
\xi_\delta,\xi_{\delta-1},\dots,\xi_2,\xi_1
\big)_b.
\end{equation}
This format gives us the flexibility to use decimal digits but represent integers in any base.
To avoid the difficulty of naming numbers when the digits are grouped as one long string and, in the tradition of most countries using the U.S. and Modern British naming convention, integers consisting of five or more base-10 digits will be grouped by threes (starting on the right) with the final group on the left consisting of one to three base-10 digits.
To avoid confusion with the notation of multivariable functions and the base-$b$ expansion notation, we will not follow the tradition using a comma as a separatrix between groups, but rather a half space.
Two examples are $12 \: 379 = (1,2,3,7,9)_{10} = (12,379)_{1000} = (12 \: 379)_{10^6}$ and $(1,0,0)_{1000} = 10^6$.
\section{Seven iterations} \label{section:seven}
We return to the problem of ascertaining $\tau_7$, the least positive integer requiring exactly seven iterations until reaching the fixed point 4 through $\mathcal{W}$.
Because $\tau_6 = 123$, $\tau_7$ will require over one hundred characters to spell so our answer must maximize the number of characters used while minimizing the number itself.
From Table \ref{table:tn}, the maximum number of characters that are necessary to spell a three decimal digit number is 27, and the smallest number with exactly that number of characters to spell is 373.
Thus our initial attempt to find $\tau_7$ will involve constructing a number consisting of ``373'' concatenated to itself multiple times.
Necessary before continuing, we have a definition and a modification to clarify notation.
The {\em length} of a string $s$, denoted $|s|$, which is the number of characters in $s$.
Because it may not be immediately obvious when a blank space is placed at the beginning and/or the end of a string, we will, hereafter, use the visible space symbol $``\text{\textvisiblespace}"$ for a blank space.
For $n \in \mathbb{N}$, define
\begin{equation} \label{eq:Mk}
M_n
:= \sum_{j=0}^{n+1} 373 \cdot 1000^j
=
\big(
\underbrace{373,373,\dots,
373}_{\text{repeated $n+2$ times}}
\big)_{1000}
\end{equation}
to be the number constructed by writing ``373'' $n+2$ times.
The lengths of $M_0$, $M_1$, and $M_2$ are, respectively,
\begin{equation} \begin{aligned}
\mathcal{W}(M_0)
&= \mathcal{W}(373) + |``\text{\textvisiblespace}
\mspace{1mu}
\verb"thousand"
\mspace{1mu}
\text{\textvisiblespace}"| + \mathcal{W}(373)
= 64, \\
\mathcal{W}(M_1)
&= \mathcal{W}(373) + |``\text{\textvisiblespace}
\mspace{1mu}
\verb"million"
\mspace{1mu}
\text{\textvisiblespace}" \,| + \mathcal{W}(M_0)
= 100, \text{ and} \notag \\
\mathcal{W}(M_2)
&= \mathcal{W}(373) + |``\text{\textvisiblespace}
\mspace{1mu}
\verb"billion"
\mspace{0mu}
\text{\textvisiblespace}" \,| + \mathcal{W}(M_1)
= 136. \notag
\end{aligned} \end{equation}
Since $\mathcal{W}(M_1) < \tau_6 < \mathcal{W}(M_2)$, then $\tau_7$ must consist of exactly four base-1000 digits.
Somewhat anticlimactically, we forgo the thrill of discovery and present
\begin{theorem} \label{theorem:tau7}
The least nonnegative integer of height 7 through $\mathcal{W}$ is $\tau_7 = 101 \; 323 \; 373 \; 373$.
\end{theorem}
\begin{proof}
To start, we verify that $N := 101 \; 323 \; 373 \; 373$ is of height 7.
We use the value of $\mathcal{W}(M_2)$ and Table \ref{table:tn} to get
\[
\mathcal{W}(N)
= \mathcal{W}(M_2) - 2 \mathcal{W}(373)
+ \mathcal{W}(101) + \mathcal{W}(323)
= 123 = \tau_6.
\]
Thus $\mathcal{W}^\#(N) = 7$ implying $\tau_7 \le N$.
Next we show that all integers smaller than $N$ must have a smaller height.
Suppose $n < N$ with $\mathcal{W}^{\#}(n) = 7$.
By the discussion preceding this theorem, $n$ must consist of four base-1000 digits.
Then $n = (\alpha_4, \alpha_3, \alpha_2, \alpha_1)_{1000}$ where $\alpha_j > 0$ for each $ 0 \le j \le 4$.
If $\alpha_4 < 101$, then
\[
\mathcal{W}(n)
= \mathcal{W}(\alpha_4)
+ \sum\nolimits_{i = 1}^3 \mathcal{W}(\alpha_i) + 28
\le 13 + 3 \cdot 27 + 28
= 122
< \tau_6.
\]
This contradicts the assumption that $\mathcal{W}^{\#}(n) = 7$ and so $\alpha_4 = 101$.
Presuming $\alpha_3 < 323$ leads to a similar conclusion, forcing $\alpha_3 = 323$.
Finally, presuming either $\alpha_2 < 373$ or $\alpha_1 < 373$ each lead to similar conclusions.
Thus $n = N$ and the result follows.
\end{proof}
\section{Extending the names of large numbers} \label{section:CGW}
The next iteration will take us to a number requiring over one hundred billion characters to spell.
Not surprisingly, it is monstrous and poses a significant problem because $\mathcal{W}$ is ill-defined for most integers between $\tau_7$ and $\tau_8$ as there is not a consensus for the names of large numbers.
Consequently, we need a numeration scheme that goes completely beyond the current accepted designations.
To define the name designations for every prefix cardinal, we start with those already established in the English language and appear in comprehensive modern dictionaries (such as Webster's dictionary \cite[p.\ 1549]{dictionary}).
They are summarized in Table \ref{table:dictionarynames}.
Our goal is to choose a naming convention most consistent with those names but is defined for all prefix cardinals.
\begin{table}[ht]
\centering
\begin{tabular}{|c|c|c|c|c|}
\cline{1-2} \cline{4-5}
\cline{1-2} \cline{4-5}
\rule{-0.5ex}{2.5ex}
\cellcolor[gray]{0.85} Prefix
& \cellcolor[gray]{0.85} Latin name
&
& \cellcolor[gray]{0.85} Prefix
& \cellcolor[gray]{0.85} Latin name \\
\cellcolor[gray]{0.85} cardinal
& \cellcolor[gray]{0.85} designation
&
& \cellcolor[gray]{0.85} cardinal
& \cellcolor[gray]{0.85} designation \\
\cline{1-2} \cline{4-5}
0 & {\it thousand} & & 11 & {\it undecillion} \\
1 & {\it million} & & 12 & {\it duodecillion} \\
2 & {\it billion} & & 13 & {\it tredecillion} \\
3 & {\it trillion} & & 14 & {\it quattuordecillion} \\
4 & {\it quadrillion} & & 15 & {\it quindecillion} \\
5 & {\it quintillion} & & 16 & {\it sexdecillion} \\
6 & {\it sextillion} & & 17 & {\it septendecillion} \\
7 & {\it septillion} & & 18 & {\it octodecillion} \\
8 & {\it octillion} & & 19 & {\it novemdecillion} \\
9 & {\it nonillion} & & 20 & {\it vigintillion} \\
10 & {\it decillion} & & 100 & {\it centillion} \\
\cline{1-2} \cline{4-5}
\end{tabular}
\caption{The Latin name designations as they appear in modern dictionaries.
} \label{table:dictionarynames}
\end{table}
But when were the dictionary names beyond {\em nonillion} first established?
We continue with where Locke left off by citing the earliest known published instances to extend the Latin name designation beyond those given by Chuquet.
{\em Decillion}, {\em undecillion}, and {\em duodecillion} first appear in a 1788 arithmetic textbook \cite[p.\ 19]{pike1} by Nicholas Pike (1743--1819).
This text is noteable as the first major arithmetic textbook in the newly created United States and is historically significant for being endorsed by George Washington (1732--99) \cite[vol. 6, p. 7--8]{washington} when he reviewed it before becoming president.
{\em Tredecillion} through {\em vigintillion} first appear in a revised edition \cite[p.\ 19]{pike2} of Pike's text published posthumously in 1822.
The word {\em centillion} first appears in an 1834 collection of short stories \cite[p.\ 118]{southey}, but it is not until 1853 in the same article by Slack \cite{slack} referenced earlier where {\em centillion} is given with its proper definition.
There are only a handful of published sources that provide names filling the gap in Table \ref{table:dictionarynames} (that is, the name designation corresponding to the prefix cardinals $m=21$ through $m=99$).
The first is the article by Slack \cite{slack} again.
He provides the name designations corresponding to prefix cardinals up to $m=27$ and for each of the multiples of 10 from $m=30$ to $m=100$.
Similar presentations follow by Heath \cite[p.\ 17]{heath} in 1856, Holbrook \cite[p.\ 306]{holbrook} and Loomis \cite[p.\ 18]{loomis}) in 1859, and much later by Borgmann \cite[p.\ 223]{borgmann65} (the same book defining truthful numbers) in 1965.
Beyond centillion, the references are remote.
This first is by Slack \cite{slack} again whose last entry in the article is his name designation corresponding to $m=1000$ which he calls {\it millillion}.
Holbrook \cite[p.\ 306]{holbrook} provides names corresponding to the prefix cardinals $m=101$, 200, and 1000 (using the same name for $m=1000$ as did Slack).
Far surpassing all others, Henkle \cite{henkle} in 1860 (and reprinted with subsequent corrections by Brooks \cite[p.\ 100, 571]{brooks} in 1876) presents a system with over 100 additional name designations but constructed utilizing a mixture of Latin cardinals and ordinals (although he does use the same name designation for $m=1000$ as given by Slack and Holbrook).
The last designation by Henkle is for $m=1 \: 000 \: 000$ which he calls {\it milli-millillion}.
The other designations, however, are completely unsystematic and not presentable in any compact way.
An attempt was made in a series of articles over a 10 year span in {\em Word Ways: The Journal of Recreational Linguistics} \cite{borgmann68-1, borgmann68-2, candelaria75, candelaria76, ondrejka} to modify the extended names in Henkle/Brooks and construct a more consistent system.
Their overall result, however, is only marginally better.
Conway and Guy's {\em The Book of Numbers} \cite[p.\ 14--15]{conway} provides the most notable and complete naming extension that is consistent with Chuquet's initial intent and we will use it to calculate $\tau_8$.
For easier reference, we christen it the {\em CGW system} for the Latin name designation of large numbers.
(The ``W'' in the designation is because the authors credit Allan Wechsler as a contributor to their system.)
We review some needed terminology for strings and formalize a few definitions before presenting the CGW system (given in Definition \ref{def:CGWsystem} below).
The string consisting of no characters, denoted $\lambda$, is the {\em empty string} (with length $|\lambda| = 0$).
Given two strings $s$ and $t$, we denote the {\it concatenation} as $st$ (with the usual convention that $\lambda s = s\lambda = s$).
Given a collection of $k$ strings $s_1, s_2, \dots, s_k$, we use the product notation $\prod^k_{i=1} s_i$ to define the concatenation recursively as $s_1$ if $k=1$ and $s_k \prod^{k-1}_{i=1} s_i$ otherwise (so that the resultant string $s_k s_{k-1} \dots s_2 s_1$ is ordered from right to left).
Given a string $s$ and a nonnegative integer $k$, we define the $k$-th {\em power} of $s$, denoted $s^k$ as $\lambda$ if $k=0$ and $s^k := \prod^k_{i=1} s$ otherwise (that is, $s^k$ consists of $s$ written $k$ times with $s^0 = \lambda$).
For a nonnegative integer $m$, define $\mathcal{L}^\ast(m)$ to be the {\em Latin name designation} of a one to three digit positive number followed by $3(m +1)$ zeros (so $\mathcal{L}^\ast(1) = ``\verb"million""$).
Accordingly, $m$ is called the {\it prefix cardinal} associated to a given Latin name designation.
In a similar manner, we define $\mathcal{W}^\ast$ to be the name designation of a nonnegative integer (so
$\mathcal{W}^\ast(126) = ``\verb"one" \text{\textvisiblespace} \mspace{1mu} \verb"hundred" \text{\textvisiblespace} \mspace{1mu} \verb"twenty" \text{\textvisiblespace} \mspace{1mu} \verb"six""$).
The lengths of these strings are denoted by the functions $\mathcal{L} \equiv |\mathcal{L}^\ast|$ and $\mathcal{W} \equiv |\mathcal{W}^\ast|$.
The following definition is a formal representation to the very colloquial (but equivalent) version given by Conway/Guy.
\begin{definition}[{\it The CGW system\rm}] \label{def:CGWsystem}
The Latin name designation associated to the prefix cardinal $m$ is
\begin{equation} \label{eq:L}
\mathcal{L}^\ast(m)
:=
\begin{cases}
``\verb"thousand"", & \text{if $m=0$}; \\
\left(
\prod_{j=1}^{\rho}
\Gamma_{\omega_j}
``\verb"illi""
\right)
``\verb"on"",
& \text{if $m>0$}
\end{cases}
\end{equation}
where, for $m > 0$, the base-1000 expansion is $m = (\omega_\rho, \dots, \omega_2, \omega_1)_{1000}$ with $\rho = 1 + \lfloor \log_{1000}m\rfloor$.
We refer to each $\Gamma_\eta$ as a {\em base string}. For each $\eta \in \mathbb{N}_{1000}$, there are associated unique integers $\eta_1,\eta_2,\eta_3 \in \mathbb{N}_{10}$ such that $\eta = 100 \eta_3 + 10 \eta_2 + \eta_1$.
The base string is
\begin{equation} \label{eq:Gamma}
\Gamma_\eta :=
\begin{cases}
``$\verb"n"''$, & \text{if $\eta=0$}; \\
\mathfrak{q}_\eta, & \text{if $0 < \eta < 10$}; \\
\mathfrak{A}_{\eta_1}
\mu_{\eta}
\mathfrak{B}_{\eta_2}
\nu_\eta
\mathfrak{C}_{\eta_3}, & \text{if $\eta \ge 10$}
\end{cases}
\end{equation}
where the strings $\mathfrak{q}_i$, $\mathfrak{A}_i$, $\mathfrak{B}_i$, and $\mathfrak{C}_i$, are given by Table \ref{table:CGW}.
The connective components $\mu_\eta$ and $\nu_\eta$ each consist of no more than a single character and are given by
\begin{equation} \label{eq:etanu}
\mu_\eta :=
\begin{cases}
\Phi_{\eta_1,\eta_3}, & \text{if $\eta_2 = 0$}; \\
\Psi_{\eta_1,\eta_2}, & \text{if $\eta_2 > 0$}
\end{cases}
\quad \text{and} \quad
\nu_\eta :=
\begin{cases}
\lambda, & \text{if $\eta_2 = 0$ or $\eta_3 = 0$}; \\
``\verb"i"", & \text{if $\eta_2 = 1,2$ and $\eta_3 > 0$}; \\
``\verb"a"", & \text{if $\eta_2 > 2$ and $\eta_3 > 0$}
\end{cases}
\end{equation}
where the characters for $\Phi$ and $\Psi$ are given in, respectively, Tables \ref{table:Phi} and \ref{table:Psi}.
\end{definition}
\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
\rowcolor[gray]{0.85}
$i$ & $\mathfrak{q}_i$ \bf (Chuquet) & $\mathfrak{A}_i$ \bf (Units) & $\mathfrak{B}_i$ \bf (Tens) & $\mathfrak{C}_i$ \bf (Hundreds) \\
\hline
0 & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ \\
1 & ``$\verb"m"$'' & ``$\verb"un"$'' & ``$\verb"dec"$'' & ``$\verb"cent"$'' \\
2 & ``$\verb"b"$'' & ``$\verb"duo"$'' & ``$\verb"vigint"$'' & ``$\verb"ducent"$'' \\
3 & ``$\verb"tr"$'' & ``$\verb"tre"$'' & ``$\verb"trigint"$'' & ``$\verb"trecent"$'' \\
4 & ``$\verb"quadr"$'' & ``$\verb"quattuor"$'' & ``$\verb"quadragint"$'' & ``$\verb"quadringent"$'' \\
5 & ``$\verb"quint"$'' & ``$\verb"quinqua"$'' & ``$\verb"quinquagint"$'' & ``$\verb"quingent"$'' \\
6 & ``$\verb"sext"$'' & ``$\verb"se"$'' & ``$\verb"sexagint"$'' & ``$\verb"sescent"$'' \\
7 & ``$\verb"sept"$'' & ``$\verb"septe"$'' & ``$\verb"septuagint"$'' & ``$\verb"septingent"$'' \\
8 & ``$\verb"oct"$'' & ``$\verb"octo"$'' & ``$\verb"octogint"$'' & ``$\verb"octingent"$'' \\
9 & ``$\verb"non"$'' & ``$\verb"nove"$'' & ``$\verb"nonagint"$'' & ``$\verb"nongent"$'' \\
\hline
\end{tabular}
\caption{The components of the base strings of the Chuquet names and the CGW system.} \label{table:CGW}
\end{center}
\end{table}
\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c c c c c c c c c c|}
\hline
& \multicolumn{10}{c|}{\cellcolor[gray]{0.85} $\eta_3$} \\
$\eta_1$ & \cellcolor[gray]{0.85} 0 & \cellcolor[gray]{0.85} 1 & \cellcolor[gray]{0.85} 2 & \cellcolor[gray]{0.85} 3 & \cellcolor[gray]{0.85} 4
& \cellcolor[gray]{0.85} 5 & \cellcolor[gray]{0.85} 6 & \cellcolor[gray]{0.85} 7 & \cellcolor[gray]{0.85} 8 & \cellcolor[gray]{0.85} 9 \\
\hline
0 & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ \\
1 & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ \\
2 & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ \\
3 & $\lambda$ & $``\verb"s""$ & $\lambda$ & $``\verb"s""$ & $``\verb"s""$ & $``\verb"s""$ & $\lambda$ & $\lambda$ & $``\verb"s""$ & $\lambda$ \\
4 & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ \\
5 & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ \\
6 & $\lambda$ & $``\verb"x""$ & $\lambda$ & $``\verb"s""$ & $``\verb"s""$ & $``\verb"s""$ & $\lambda$ & $\lambda$ & $``\verb"x""$ & $\lambda$ \\
7 & $\lambda$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"m""$ & $\lambda$ \\
8 & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ \\
9 & $\lambda$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"m""$ & $\lambda$ \\
\hline
\end{tabular}
\caption{Components of $\Phi_{\eta_1,\eta_3}$ for the CGW system (where $\eta_2 = 0$).} \label{table:Phi}
\end{center}
\end{table}
\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c c c c c c c c c|}
\hline
& \multicolumn{9}{c|}{\cellcolor[gray]{0.85} $\eta_2$} \\
$\eta_1$ & \cellcolor[gray]{0.85} 1 & \cellcolor[gray]{0.85} 2 & \cellcolor[gray]{0.85} 3 & \cellcolor[gray]{0.85} 4
& \cellcolor[gray]{0.85} 5 & \cellcolor[gray]{0.85} 6 & \cellcolor[gray]{0.85} 7 & \cellcolor[gray]{0.85} 8 & \cellcolor[gray]{0.85} 9 \\
\hline
0 & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ \\
1 & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ \\
2 & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ \\
3 & $\lambda$ & $``\verb"s""$ & $``\verb"s""$ & $``\verb"s""$ & $``\verb"s""$ & $\lambda$ & $\lambda$ & $``\verb"s""$ & $\lambda$ \\
4 & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ \\
5 & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ \\
6 & $\lambda$ & $``\verb"s""$ & $``\verb"s""$ & $``\verb"s""$ & $``\verb"s""$ & $\lambda$ & $\lambda$ & $``\verb"x""$ & $\lambda$ \\
7 & $``\verb"n""$ & $``\verb"m""$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"m""$ & $\lambda$ \\
8 & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ & $\lambda$ \\
9 & $``\verb"n""$ & $``\verb"m""$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"n""$ & $``\verb"m""$ & $\lambda$ \\
\hline
\end{tabular}
\caption{Components of $\Psi_{\eta_1,\eta_2}$ for the CGW system (where $\eta_2 > 0$ and $\eta_3 \in \mathbb{N}_{10}$).} \label{table:Psi}
\end{center}
\end{table}
We illustrate the definition by looking at a few simple examples.
If $m = 1 = (1)_{1000}$, then $\rho = 1$ and
\begin{equation} \notag
\mathcal{L}^\ast(1)
= \left( \prod\nolimits_{j=1}^{\rho} \Gamma_{\omega_j} ``\verb"illi"" \right) ``\verb"on""
= \left( \Gamma_1 ``\verb"illi"" \right) ``\verb"on""
= \mathfrak{q}_1 ``\verb"illion""
= ``\verb"million""
\end{equation}
as expected.
We note that
$\mathcal{L}^\ast(1000) = \Gamma_1 ``\verb"illi"" \Gamma_0 ``\verb"illion"" = ``\verb"millinillion""$
demonstrates that the use of $``\verb"n""$ as a placeholder for some larger prefix cardinals (making this slightly inconsistent with the designations by Slack and Henkle).
A longer Latin name designation sampling of the rules in the CGW system is
\begin{equation} \begin{aligned}
\mathcal{L}^\ast(27 \: 002 \: 103 \: 300)
&= \Gamma_{27} ``\verb"illi"" \Gamma_{2} ``\verb"illi"" \Gamma_{103} ``\verb"illi"" \Gamma_{300} ``\verb"illion"" \\
&= \mathfrak{A}_7 ``\verb"m"" \mathfrak{B}_2 \lambda \lambda ``\verb"illi""
\mathfrak{q}_2 ``\verb"illi""
\mathfrak{A}_3 ``\verb"s"" \lambda \lambda \mathfrak{C}_1 ``\verb"illi""
\lambda \lambda \lambda \lambda \mathfrak{C}_3 ``\verb"illion"" \\
&= ``\verb"septe" \verb"m" \verb"vigint" \verb"illi"
\verb"b" \verb"illi"
\verb"tre" \verb"s" \verb"cent" \verb"illi"
\verb"trecent" \verb"illion"".
\end{aligned} \notag \end{equation}
A more explicit example to consider is the {\sc googol} sequence of numbers.
It is defined recursively as $g_0 := 100$ and $g_n := 10^{g_{n-1}}$ for $n \in \mathbb{Z}^+$.
The second term of the sequence, $g_1 = 10^{100}$, is the {\sc googol} (first defined by Kasner and Newman \cite[p.\ 20]{knn}). Since $g_1 = 10^{100} = 10 \cdot 1000^{1+32}$, then
\begin{equation} \notag
\mathcal{W}^\ast(g_1)
= \mathcal{W}^\ast(10) ``\text{\textvisiblespace}" \mathcal{L}^\ast(32)
= ``\verb"ten" \text{\textvisiblespace} \mspace{2mu} " \mathfrak{A}_2 \lambda \mathfrak{B}_3 \lambda \lambda ``\verb"illion""
= ``\verb"ten" \text{\textvisiblespace} \mspace{2mu} \verb"duotrigintillion"".
\end{equation}
The third term of the sequence, $g_2$, is the \textsc{googolplex}.
Since
\begin{align}
g_2
=10^{g_1}
=10^{1+\sum_{i=1}^{100}9 \cdot 10^{i-1}}
&=10 \cdot 10^{3\sum_{i=1}^{100}3 \cdot 10^{i-1}}
\notag \\
&=10 \cdot 1000^{1+
\left(
3 \cdot 1000^{33} + \sum_{j=2}^{33}333 \cdot 1000^{j-1} + 332
\right)}
\notag \\
&=10 \cdot 1000^{1+ m_{g_2}},
\notag
\end{align}
where $m_{g_2} = \left( 3, 333, 333, \dots, 333, 332 \right)_{1000}$ is the associated prefix cardinal (and consists of 34 base-1000 digits), then the Latin name designation is
\begin{equation} \begin{aligned}
&\mathcal{W}^\ast(g_2)
\notag \\
&= \mathcal{W}^\ast(10) ``\text{\textvisiblespace}" \mathcal{L}^\ast(m_{g_2})
\notag \\
&= ``\verb"ten" \text{\textvisiblespace} \mspace{2mu}"
\Gamma_{3} ``\verb"illi""
(\Gamma_{333} ``\verb"illi"")^{32}
\Gamma_{332} ``\verb"illion""
\notag \\
&= ``\verb"ten" \text{\textvisiblespace} \mspace{2mu}"
\mathfrak{q}_3 ``\verb"illi""
(\mathfrak{A}_3 ``\verb"s"" \mathfrak{B}_3 ``\verb"a"" \mathfrak{C}_3 ``\verb"illi"")^{32}
\mathfrak{A}_2 \lambda \mathfrak{B}_3 ``\verb"a"" \mathfrak{C}_3 ``\verb"illion""
\notag \\
&= ``\verb"ten" \text{\textvisiblespace} \mspace{2mu} \verb"trilli""
``\verb"trestrigintatrecentilli""^{32}
``\verb"duotrigintatrecentillion""
\notag
\end{aligned} \end{equation}
and requires $\mathcal{W}(g_2) = 10 + 23 \cdot 32 + 24 = 770$ characters to spell.
One criticism of the CGW system is its inconsistency with three of the dictionary definitions in Table \ref{table:dictionarynames}.
They are $\mathcal{L}^\ast(15) = ``\verb"quinquadecillion""$, $\mathcal{L}^\ast(16) = ``\verb"sedecillion""$, and $\mathcal{L}^\ast(19) = ``\verb"novendecillion""$.
Although it was highly desirous to have chosen a system that corresponds with the dictionary definitions, the designer's choice was deliberate knowing that it did conflict and instead choosing a spelling they determined more consistent with the Latin spellings of numbers.
We therefore utilize the CWG system exactly as it was intended by Conway/Guy.
\section{The Completion of the Proof of Theorem \ref{convergence}} \label{section:completion}
With the name designations of all nonnegative integers defined, we can now provide the (obvious!) proof that all iteration sequences converge to the fixed point (proposed in $\S$\ref{section:intro} and partially proven in $\S$\ref{section:zerotosix}).
The proof utilizes a bound on the longest possible base string $\Gamma_\eta$ (with $\eta \in \mathbb{N}_{1000}$) that can be constructed in Definition \ref{def:CGWsystem}.
A little experimenting with the definition and Table \ref{table:CGW} can easily produce the upper bound of $|\Gamma_{454}| = |\mathfrak{A}_4 \lambda \mathfrak{B}_5 ``\verb"a"" \mathfrak{C}_4| = 31$.
As in the partial proof, this remaining part is also based on the counting of the length of $M_n$ given by \eqref{eq:Mk}.
For $n \in \mathbb{N}$, we have
\begin{align}
\mathcal{W}(M_n)
&= \sum\nolimits_{i=0}^n \Big( \mathcal{W}(373) + |``\text{\textvisiblespace}"| + \mathcal{L}(i) + |``\text{\textvisiblespace}"| \Big) + \mathcal{W}(373) \notag \\
&= 29n + 56 + \sum\nolimits_{i=0}^n \mathcal{L}(i)
= 29n + 64 + \sum\nolimits_{i=1}^n \mathcal{L}(i) \label{eq:lengthWn}
\end{align}
where we take the convention that the summand is zero if the upper bound of summation is less than the lower bound.
\begin{customthm}{1}
All iteration sequences through $\mathcal{W}$ converge to 4.
\end{customthm}
\begin{proof}[Completion of the proof]
As in the partial proof in $\S$\ref{section:zerotosix}, we show that $\mathcal{W}(n) < n$ for all $n \ge 10^3$.
If $10^3 \le n < 10^6$, then $\mathcal{W}(n) \le \mathcal{W}(M_0) = 64 < n$.
For a given $n \ge 10^6$, let $\delta$ be the number of base-1000 digits of $n$.
Then
\[
\delta
= 1 + \lfloor \log_{1000} n \rfloor
\le 1 + \log_{1000} n
\]
and hence $\delta \ge 3$.
Let $\kappa$ be the number of base-1000 digits of $\delta - 2$.
Then
\[
\kappa = 1 + \lfloor \log_{1000} (\delta - 2) \rfloor \le 1 + \log_{1000} (\delta - 2).
\]
We can easily verify that, for any $n \ge 10^6$, $29 \delta + 6 < \tfrac{1}{2} n$, $\delta - 2 < \tfrac{1}{2} \sqrt{n}$, and $35 \kappa + 2 < \sqrt{n}$.
Then, using \eqref{eq:lengthWn},
\begin{equation} \begin{aligned}
\mathcal{W}(n)
\le \mathcal{W}(M_{\delta - 2})
&= 29(\delta - 2) + 64 + \sum\nolimits_{i=1}^{\delta - 2} \mathcal{L}(i)
\notag \\
&\le 29\delta + 6 + (\delta - 2)
\left(
\sum\nolimits_{j=1}^{\kappa}
\left| \Gamma_{454} ``\verb"illi"" \right|
+ \left| ``\verb"on"" \right|
\right)
\notag \\
&= 29\delta + 6 + (\delta - 2)(35\kappa + 2) \le \tfrac{1}{2} n + \tfrac{1}{2} \sqrt{n}\sqrt{n} = n
\notag
\end{aligned} \end{equation}
and hence $\mathcal{W}(n) < n$ for all $n \ge 10^6$.
Therefore, using this and the partial proof given in $\S$\ref{section:zerotosix}, all iteration sequences with seed $n \in \mathbb{N}$ must converge to 4.
\end{proof}
The proof outlines that the growth rate of $\mathcal{W}$ using the CGW system is $\mathcal{O} \big( \log n \cdot \log \log n \big)$.
It is not always true that any naming convention will have this growth rate.
For example, the one provided by Noll \cite{noll} is a slightly worse $\mathcal{O} \big( \log n \cdot (\log \log n )^2 \big)$ despite it having a very similar appearance to Conway/Guy.
\section{Counting the contributions of $\mu_\eta$ in the CGW system}
\label{section:mu}
The process of establishing $\tau_8$ will require us to count all of the string components in Definition \ref{def:CGWsystem}.
Of these, the hardest part will be the contribution of the characters from $\mu_n$ (specifically, $\Phi$ and $\Psi$ from Tables \ref{table:Phi} and \ref{table:Psi}).
We expedite the computations by grouping together in the tables neighboring characters by rows.
For $p,q \in \mathbb{Z}^+$ and $d \in \mathbb{N}$, let
\begin{equation} \label{eq:setnumbers}
S_d(p,q)
:= \{ d + 10i + 100j : i \in \mathbb{N}_p, j \in \mathbb{N}_q \}
\end{equation}
be the set of $pq$ numbers constructed by starting at $d$ and increasing, in base-10, the tens digits by 0 through $p-1$ and increasing the hundreds digit by 0 through $q-1$.
(We presume that $p$ and $q$ are small enough so that neither the tens digit nor the hundreds digit go above 9.)
To illustrate, an example is $S_{270}(2,3) = \{ 270, 280, 370, 380, 470, 480 \}$.
We partition the contributions of $\Phi$ and $\Psi$ into six sets.
\begin{itemize}
\item In $\Phi$ (Table \ref{table:Phi}), the location of the three contiguous $``\verb"s""$s in the third
and sixth rows are represented by, respectively,
$S_{303}(1,3)$ and $S_{306}(1,3)$.
Let $D_1$ be the union of these two sets.
\item In $\Phi$, the location of the eight contiguous characters (one $``\verb"m""$ and seven $``\verb"n""$s) in the seventh and ninth rows are
represented by, respectively, $S_{107}(1,8)$ and $S_{109}(1,8)$.
Let $D_2$ be the union of these two sets.
\item The location of the four remaining characters in $\Phi$
(two $``\verb"s""$s in the third row and two $``\verb"x""$s in the sixth row)
are represented by
$S_{103}(1,1)$, $S_{106}(1,1)$, $S_{803}(1,1)$, and
$S_{806}(1,1)$. Let $D_3$ be the union of these four sets.
\item In $\Psi$ (Table \ref{table:Psi}), the location of the four contiguous $``\verb"s""$s in the third
and sixth rows are represented by, respectively,
$S_{23}(4,10)$ and $S_{26}(4,10)$.
Let $D_4$ be the union of these two sets.
\item In $\Psi$, the location of the eight contiguous characters (one $``\verb"m""$ and seven $``\verb"n""$s) in the seventh and ninth rows are
represented by, respectively, $S_{17}(8,10)$ and $S_{19}(8,10)$. Let
$D_5$ be the union of these two sets.
\item The location of the two remaining characters in $\Psi$ (the ``\verb"s"" and
the ``\verb"x"" in the eighth column) are represented by
$S_{83}(1,10)$ and $S_{86}(1,10)$. Let
$D_6$ be the union of these two sets.
\end{itemize}
Thus, for $\omega \in \mathbb{N}_{1000}$, the length of $\mu_\omega$ is 1 if $\omega \in \bigcup_{i=1}^6 D_i$ and 0 otherwise.
\section{Generating functions}
To get an exact value of $\tau_8$, we follow the same format used in $\S$\ref{section:seven} to find $\tau_7$.
This will require us to find a systematic way to count the number of characters in $\mathcal{W}(M_n)$, where $M_n$ is given by (\ref{eq:Mk}).
Since there are a large number of components where the length needs to be determined, we use generating functions because they are compact and can be easily combined into a single answer.
\begin{lemma}[{\it Generating functions for base-$b$ digit counting}\rm]
\label{lemma:gf} Let $b \in \mathbb{N}$ with $b>1$ be a given base and $k \in \mathbb{N}$.
\begin{itemize}
\item Let $P_{b,k}(x)$ be the generating function whose coefficient
of $x^n$ is the number of integers in the set $\{ 1,2, \dots, n \}$
consisting of $k+1$ or more base-$b$ digits. Then
\begin{equation} \label{eq:q}
P_{b,k}(x) = \frac{x^{b^k}}{(1-x)^2}.
\end{equation}
\item For $d \in \mathbb{N}_b - \{ 0 \}$ a nonzero base-$b$ digit, let
$Q_{b,d,k}(x)$ be the generating function whose coefficient of $x^n$
is the number of integers in the set $\{ 1,2, \dots, n \}$ such that
the $(k+1)$-th base-$b$ digit is $d$. Then
\begin{equation} \label{eq:s}
Q_{b,d,k}(x)
= \frac{x^{b^k d}
(1-x^{b^k})}{(1-x)^2
\left(
1-x^{b^{k+1}}
\right)}.
\end{equation}
\end{itemize}
\end{lemma}
\begin{proof}
Only four identities are needed. The first two are the finite and infinite geometric series.
They are
\[
\frac{1-x^{r+1}}{1-x}
= 1 + x + x^2 + \dots + x^r
\textrm{ and }
\frac{1}{1-x} = 1 + x + x^2 + \cdots
\]
(presuming $r \in \mathbb{N}$).
Differentiating each gives
\[
\frac{1-(r+1)x^r + rx^{r+1}}{(1-x)^2}
= 1 + 2x + 3x^2 + \dots + rx^{r-1}
\]
(presuming $r \in \mathbb{Z}^+$) and
\[
\frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + \cdots.
\]
Since $b^k$ is the smallest integer consisting of $k+1$ base-$b$ digits, then
\[
P_{b,k}(x)
= x^{b^k} + 2x^{b^k+1} + 3x^{b^k+2}+ \cdots
= x^{b^k}
\left(
1 + 2x + 3x^2 + \cdots
\right)
=\frac{x^{b^k}}{(1-x)^2}.
\]
To demonstrate $Q_{b,d,k}(x)$, we note that the first occurrence of $d$ in the $(k+1)$-th position is the integer $b^k d$.
The occurrence of $d$ in that position continues until $b^k(d+1) - 1$ (and each of these numbers consist of exactly $k+1$ base-$b$ digits).
The next occurrence in the $(k+1)$-th position is at $b^{k+1} + b^k d$ (consisting of $k+2$ base-$b$ digits) and continues until $b^{k+1} + b^k (d+1) - 1$.
In general, for $j \in \mathbb{N}$, all integers from $j \cdot b^{k+1} + b^k d$ to $j \cdot b^{k+1} + b^k (d+1) - 1$ have the digit $d$ in the $(k+1)$-th position.
Thus
\begin{align}
Q_{b,d,k}&(x)
\notag \\
&= x^{b^kd}
\left(
1 + 2x + 3x^2 + \cdots + b^k x^{b^k-1}
\right)
+ b^k x^{b^k(d+1)}
\left(
1 + x + x^2 + \cdots
\right)
\notag \\
& \qquad
+ x^{b^{k+1}+b^kd}
\left(
1 + 2x + 3x^2 + \cdots + b^k x^{b^k-1}
\right)
+ b^k x^{b^{k+1}+b^k(d+1)}
\left(
1 + x + x^2 + \cdots
\right)
\notag \\
& \qquad
+ x^{2b^{k+1}+b^kd}
\left(
1 + 2x + 3x^2 + \cdots + b^k x^{b^k-1}
\right)
+ b^k x^{2b^{k+1}+b^k(d+1)}
\left(
1 + x + x^2 + \cdots
\right)
\notag \\
& \qquad
+ \cdots
\notag \\
&= x^{b^kd}
\left(
1 + x^{b^{k+1}} + x^{2b^{k+1}} + \cdots
\right)
\left(
1 + 2x + 3x^2 + \cdots + b^k x^{b^k-1}
\right)
\notag \\
& \qquad
+ b^k x^{b^k(d+1)}
\left(
1 + x^{b^{k+1}} + x^{2b^{k+1}} + \cdots
\right)
\left(
1 + x + x^2 + \cdots
\right)
\notag \\
&= x^{b^kd}
\left(
1 + x^{b^{k+1}} + (x^{b^{k+1}})^2 + \cdots
\right)
\left(
\frac{1-(b^k + 1)x^{b^k} + b^kx^{b^k+1}}{(1-x)^2}
+ b^k x^{b^k}
\frac{1}{1-x}
\right)
\notag \\
&= \frac{x^{b^kd}
(1-x^{b^k})}{(1-x)^2
\left(
1-x^{b^{k+1}}
\right)}.
\notag
\end{align}
\end{proof}
Since (\ref{eq:s}) includes integers whose leading digit is $d$ (with $d$ nonzero), the lemma does not apply to cases where $d=0$.
So we present the following to specifically count those cases (but the corollary applies to the nonzero digits as well).
\begin{corollary} \label{lemma:gfcor}
For $b \in \mathbb{N}$ with $b>1$ a given base, $k \in \mathbb{N}$, and $d \in \mathbb{N}_b$, let $Q^{\star}_{b,d,k}(x)$ be the generating function whose coefficient of $x^n$ is the number of occurrences of $d$ in the set $\{ 1,2, \dots, n \}$ as the $(k+1)$-th base-$b$ digit in a number consisting of $k+2$ or more base-$b$ digits.
Then
\[
Q^{\star}_{b,d,k}(x) = x^{b^{k+1}} Q_{b,d,k}(x).
\]
\end{corollary}
\begin{proof}
Following the same format used for $Q_{b,d,k}(x)$ in Lemma \ref{lemma:gf} except start at $b^{k+1} + b^k d$ instead of $b^k d$.
\end{proof}
For counting contiguous blocks of characters (needed for counting the contribution of characters from $\mu_n$ in Definition \ref{def:CGWsystem} and $\S$\ref{section:mu}), we have the following lemma.
\begin{lemma} \label{lemma:PT}
Given the set $S_d(p,q)$ {\rm (}with $d \ne 0${\rm)} defined in \eqref{eq:setnumbers}, let $R_{S_d(p,q),k}(x)$ be the generating function whose coefficient of $x^n$ is the number of occurrences of any element of $S_d(p,q)$ in the set $\{ 1, 2, \dots, n \}$ as the $(k+1)$-th base-1000 digit.
Then
\[
R_{S_d(p,q),k}(x)
= \frac{y_k^d(1- y_k)(1 - y_k^{10p})(1 - y_k^{100q})}{(1-x)^2(1- y_k^{10})(1 - y_k^{100})(1 - y_k^{1000}) }
\]
where $y_k \equiv y_k(x) = x^{1000^k}$.
\end{lemma}
\begin{proof}
Using Lemma \ref{lemma:gf} and the formula for the sum of a finite geometric series, we have
\begin{align}
R_{S_d(p,q),k}(x) = \sum_{\omega \in S_d(p,q)} Q_{1000,\omega,k}(x)
&= \frac{1-y_k}{(1-x)^2(1-y_k^{1000})} \sum_{\omega \in S_d(p,q)} y_k^\omega
\notag \\
&= \frac{1-y_k}{(1-x)^2(1-y_k^{1000})} \sum_{i=0}^{p-1} \sum_{j=0}^{q-1} y_k^{d + 10i + 100j}
\notag \\
&= \frac{y_k^d(1-y_k)}{(1-x)^2(1-y_k^{1000})}
\sum_{i=0}^{p-1} \left ( y_k^{10} \right)^i
\sum_{j=0}^{q-1} \left ( y_k^{100} \right)^j
\notag \\
&= \frac{y_k^d(1- y_k)}{(1-x)^2(1 - y_k^{1000})}
\cdot \frac{1 - y_k^{10p}}{1- y_k^{10}}
\cdot \frac{1 - y_k^{100q}}{1 - y_k^{100}}.
\notag
\end{align}
\end{proof}
\section{Eight iterations}
The two theorems in this section are the culmination of the previous four sections.
The final element needed to present the theorems is to convert the lengths of the strings in Table \ref{table:CGW} to generating functions.
We represent the lengths as four vectors:
\begin{align}
& \mathbf{v}_0 = \langle 0,1,1,2,5,5,4,4,3,3 \rangle, \notag \\
& \mathbf{v}_1 = \langle 0,2,3,3,8,7,2,5,4,4 \rangle, \notag \\
& \mathbf{v}_2 = \langle 0,3,6,7,10,11,8,10,8,8 \rangle, \mbox{ and} \notag \\
& \mathbf{v}_3 = \langle 0,4,6,7,11,8,7,10,9,7 \rangle \notag.
\end{align}
The $i$-th component of each vector is, respectively, the lengths of the strings $\mathfrak{q}_i$, $\mathfrak{A}_i$, $\mathfrak{B}_i$, and $\mathfrak{C}_i$.
For each $j \in \mathbb{N}_4$, define the polynomial $V_j(z):=\mathbf{v}_j \cdot \langle 1, z,\dots, z^9 \rangle$.
\begin{theorem} \label{theorem:F}
Let $F(x)$ be the generating function whose coefficient of $x^n$ is $\mathcal{W}(M_n)$ where $M_n$ is given by \eqref{eq:Mk}.
Then
\begin{equation} \notag
F(x)
= \frac{64}{1-x} + \frac{1}{(1-x)^2}
\left(
31x
+\sum_{k=0}^\infty
\left(
4y_k + y_k^{100} + H(y_k)
\right)
\right)
\end{equation}
where $y_k \equiv y_k(x) = x^{1000^k}$,
\begin{align}
&H(z) = \frac{(1-z) V_1(z)}{1-z^{10}}
+ \frac{G_1(z)}{1-z^{100}}
+ \frac{G_2(z)}{1-z^{1000}}
+ \frac{1-z}{1-z^{100}}
\left(
\frac{G_3(z)}{1-z^{10}} + \frac{G_4(z)}{1-z^{1000}}
\right), \notag \\
&G_1(z) =
\left( 1-z^{10} \right)
\left( V_2(z^{10})-z^{100} \right)
+(1-z) \left( z^{83} + z^{86} \right),
\notag \\
&G_2(z) =
(1-z^{100})
V_3(z^{100}) + z^{1000} \left( z^{100} - z^{10} \right)
\notag \\
& \qquad \quad \qquad \quad
+ (1-z)
\left( z^{103} + z^{106} + z^{803} + z^{806} + z^{1000} + V_0(z) - V_1(z) \right),
\notag \\
&G_3(z) =
\left( z^{23}+z^{26} \right)
(1-z^{40})
+ \left( z^{17}+z^{19} \right)
\left( 1-z^{80} \right),
\notag \\
\intertext{and}
&G_4(z) =
\left( z^{303}+z^{306} \right)
(1-z^{300})
+ \left( z^{107}+z^{109} \right)
\left( 1-z^{800} \right).
\notag
\end{align}
\end{theorem}
\begin{proof}
Using (\ref{eq:lengthWn}) and the geometric series formulas given in the proof of Lemma \ref{lemma:gf}, we have
\begin{align}
F(x)
= \sum_{n=0}^\infty \mathcal{W}(M_n) x^n
&= \sum_{n=0}^\infty
\left (
29n + 64 + \sum_{i=1}^n \mathcal{L}(i)
\right ) x^n
\notag \\
&= 64 \sum_{n=0}^\infty x^n
+ 29 \sum_{n=0}^\infty n x^n + \sum_{n=0}^\infty
\left(
\sum_{i=1}^n \mathcal{L}(i)
\right) x^n
\notag \\
&= \frac{64}{1-x}
+ \frac{29x}{(1-x)^2}
+\sum_{n=1}^\infty \sum_{i=1}^n \mathcal{L}(i) x^n.
\label{eq:F(x)}
\end{align}
We will count the double sum $\sum_{n=1}^\infty \sum_{i=1}^n \mathcal{L}(i) x^n$ in terms of each string component appearing in Definition \ref{def:CGWsystem} with $n$ representing the Latin prefix cardinal.
The counting is done with regard to the base-10 or base-1000 digits, wherever appropriate.
Each generating function is evaluated using Lemma \ref{lemma:gf}, Corollary \ref{lemma:gfcor}, or Lemma \ref{lemma:PT}, as needed.
In (\ref{eq:L}), the $``\verb"on""$ string appears once for every positive prefix cardinal, so the generating function to count the number of characters is
\begin{equation} \label{eq:on}
|``\verb"on""| P_{b,0}(x) = \frac{2x}{(1-x)^2}
\end{equation}
(any choice of $b > 1$ will work).
The $``\verb"illi""$ string occurs once for every base-1000 digit.
So the generating function for the $(k+1)$-th base-1000 digit is
\begin{equation} \label{eq:illi}
|``\verb"illi""| P_{1000,k}(x)
= \frac{4y_k}{(1-x)^2}.
\end{equation}
In (\ref{eq:Gamma}), $``\verb"n""$ occurs every time the $(k+1)$-th base-1000 digit is 0, so the generating function is
\begin{equation}
|``\verb"n""| Q^\star_{1000,0,k}(x)
= \frac{y_k^{1000}(1-y_k)}{(1-x)^2(1-y_k^{1000})}.
\end{equation}
We next count the strings appearing in Table \ref{table:CGW}.
For the Chuquet strings $\mathfrak{q}_i$, the generating function for the $(k+1)$-th base-1000 digit is
\begin{equation}
\sum_{d=0}^9 |\mathfrak{q}_d| Q_{1000,d,k}(x)
= \frac{(1-y_k)V_0(y_k)}{(1-x)^2(1-y_k^{1000})}.
\end{equation}
For $\mathfrak{A}_i$, the unit component of the base strings (used only when the tens or the hundreds component is nonzero), a generating function for all strings for the $(k+1)$-th base-1000 digit is
\begin{equation}
\sum_{d=0}^9 |\mathfrak{A}_d|
\big(
Q_{10,d,3k}(x)-Q_{1000,d,k}(x)
\big)
= \frac{(1-y_k)V_1(y_k)}{(1-x)^2}
\left(
\frac{1}{1-y_k^{10}}
- \frac{1}{1-y_k^{1000}}
\right).
\end{equation}
For $\mathfrak{B}_i$, the tens component of the base strings, a generating function for all strings for the $(k+1)$-th base-1000 digit is
\begin{equation}
\sum_{d=0}^9 |\mathfrak{B}_d| Q_{10,d,3k+1}(x)
= \frac{(1-y_k^{10})V_2(y_k^{10})}{(1-x)^2(1-y_k^{100})} .
\end{equation}
For $\mathfrak{C}_i$, the hundreds component of the base strings, a generating function for all strings for the $(k+1)$-th base-1000 digit is
\begin{equation} \label{eq:hundreds}
\sum_{d=0}^9 |\mathfrak{C}_d| Q_{10,d,3k+2}(x)
= \frac{(1-y_k^{100})V_3(y_k^{100})}{(1-x)^2(1-y_k^{1000})}.
\end{equation}
In (\ref{eq:etanu}), the length of $\nu_\eta$ is 1 if both the tens digit and hundreds digit of $\eta$ are nonzero and 0 otherwise.
We count all the base-1000 digits, throw out the cases where the hundreds digits is 0 and the tens digits is 0 and then cases that were thrown out twice have to be put back in.
The generating function is
\begin{align}
P_{10,3k+2}(x) &- Q^\star_{10,0,3k+1}(x) - Q^\star_{10,0,3k+2}(x) +
\sum_{d=0}^9 Q^\star_{1000,d,k}(x)
\notag \\
&= \frac{1}{(1-x)^2}
\left(
y_k^{100}
- \frac{y_k^{100}(1-y_k^{10})}{1-y_k^{100}}
+ \frac{y_k^{1000}(y_k^{100}-y_k^{10})}{1-y_k^{1000}}
\right).
\end{align}
For $\mu_\eta$, we use Lemma \ref{lemma:PT} and the decomposition by sets $D_1$ through $D_6$ as presented in $\S$\ref{section:mu}.
The generating functions are
\begin{align}
&\sum_{d \in D_1 } R_{S_d(1,3)}(x) = \frac{(1-y_k)(y_k^{303} + y_k^{306})(1-y_k^{300})}{(1-x)^2 (1-y_k^{100})
(1-y_k^{1000})},
\\
&\sum_{d \in D_2 } R_{S_d(1,8)}(x) = \frac{(1-y_k)(y_k^{107} + y_k^{109})(1-y_k^{800})}{(1-x)^2 (1-y_k^{100})
(1-y_k^{1000})},
\\
&\sum_{d \in D_3 } R_{S_d(1,1)}(x) = \frac{(1-y_k)(y_k^{103} + y_k^{106} + y_k^{803} + y_k^{806})}{(1-x)^2
(1-y_k^{1000})},
\\
&\sum_{d \in D_4 } R_{S_d(4,10)}(x) = \frac{(1-y_k)(y_k^{23} + y_k^{26})(1-y_k^{40})}{(1-x)^2 (1-y_k^{10})
(1-y_k^{100})},
\\
&\sum_{d \in D_5 } R_{S_d(8,10)}(x) = \frac{(1-y_k)(y_k^{17} + y_k^{19})(1-y_k^{80})}{(1-x)^2 (1-y_k^{10})
(1-y_k^{100})}, \textrm{ and}
\\
&\sum_{d \in D_6 } R_{S_d(1,10)}(x) = \frac{(1-y_k)(y_k^{83} + y_k^{86})}{(1-x)^2
(1-y_k^{100})} \label{eq:D6}.
\end{align}
The double sum in (\ref{eq:F(x)}) is given by (\ref{eq:on}) and the sum (\ref{eq:illi}) through (\ref{eq:D6}) over all $k \in \mathbb{N}$.
Substituting these into (\ref{eq:F(x)}) gives the desired result.
\end{proof}
It is left as an exercise to the reader to use Theorem \ref{theorem:F} to verify that
\[
F(x) = 64 + 100x + 136x^2 + 173x^3 + 213x^4 + 253x^5 + 292x^6 + 331x^7 + \cdots.
\]
With the assistance of a computer, more of these coefficients have been compiled in Table \ref{table:coefficients}.
The table and Theorem \ref{theorem:tau7} indicate that $M_{10^9} < \tau_8 < M_{10^{10}}$ since $\mathcal{W}(M_{10^9}) < \tau_7 < \mathcal{W}(M_{10^{10}})$.
\begin{table}[ht]
\centering
\begin{tabular}{|c|c|c|c|c|}
\cline{1-2} \cline{4-5}
\rule{-0.5ex}{2.5ex}
\cellcolor[gray]{0.85} $n$
& \cellcolor[gray]{0.85} $\mathcal{W}(M_n)$
&
& \cellcolor[gray]{0.85} $n$
& \cellcolor[gray]{0.85} $\mathcal{W}(M_n)$ \\
\cline{1-2} \cline{4-5}
10 & 445 & & $10^6$ & $76 \; 769 \; 074$ \\
$10^2$ & 4674 & & $10^7$ & $831 \; 735 \; 076$ \\
$10^3$ & $53 \; 956$ & & $10^8$ & $9 \; 179 \; 395 \; 077$ \\
$10^4$ & $602 \; 941$ & & $10^9$ & $99 \; 655 \; 995 \; 079$ \\
$10^5$ & $6 \; 890 \; 772$ & & $10^{10}$ & $1 \; 060 \; 604 \; 995 \; 081$ \\
\cline{1-2} \cline{4-5}
\end{tabular}
\caption{A selection of coefficients of $F(x)$ given in Theorem \ref{theorem:F}.} \label{table:coefficients}
\end{table}
We can now present the value of $\tau_8$.
Again, rather anticlimactically, we have
\begin{theorem} \label{theorem:tau8}
The least nonnegative integer of height 8 through $\mathcal{W}$ is
\[
\tau_8
= 101 \: \underbrace{373 \: 373 \dots \dots \dots \dots \dots 373}_{\text{repeated $1 \; 018 \; 436 \; 987$ times}}.
\]
\end{theorem}
\begin{proof}
We verify that $N = 101 \cdot 1000^{\varepsilon_0 + 2} + M_{\varepsilon_0}$, where $\varepsilon_0 = 1 \; 018 \; 436 \; 985$, is of height 8.
The generating function in Theorem \ref{theorem:F} is used to verify that
\begin{equation} \label{eq:tau8inequality}
\mathcal{W}(M_{\varepsilon_0})
< \tau_7
< \mathcal{W}(M_{\varepsilon_0 + 1})
= 101 \; 323 \; 373 \; 385
= \tau_7 + 12.
\end{equation}
Since $\mathcal{W}(373) = \mathcal{W}(101) + 12$ (via Table \ref{table:tn}), then $\mathcal{W}(N) = \tau_7$ and so $\tau_8 \le N$.
Suppose $n < N$ with $\mathcal{W}^\#(n) = 8$.
From (\ref{eq:tau8inequality}), we know that $n$ must consist of $\varepsilon_0 + 3$ base-1000 digits.
Suppose $n = (\alpha_{\varepsilon_0 + 3}, \dots, \alpha_1)_{1000}$ with each $\alpha_j > 0$ for $1 \le j \le \varepsilon_0 + 3$.
If $\alpha_{\varepsilon_0 + 3} < 101$, then
\[
\mathcal{W}(n)
= \mathcal{W}(\alpha_{\varepsilon_0 + 3}) - \mathcal{W}(373) + \mathcal{W}(M_{\varepsilon_0 + 1})
\le 13 - 27 + \tau_7 + 12 = \tau_7 - 2.
\]
This contradicts the assumption that $\mathcal{W}^{\#}(n) = 8$.
Thus $\alpha_{\varepsilon_0 + 3} = 101$.
Taking $\alpha_j < 373$ for any $1 \le j < \varepsilon_0 + 3$ also leads to a contradiction.
And so $n = N$ and the result follows.
\end{proof}
\section{Concluding remarks}
A summary of the answers is given in Table \ref{table:summary}.
\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|}
\hline
\rowcolor[gray]{0.85}
\rule{-0.5ex}{2.5ex} $\boldsymbol{k}$ & $\boldsymbol{\tau_k}$ \\
\hline
0 & 4 \\
\hline
1 & 0 \\
\hline
2 & 3 \\
\hline
3 & 1 \\
\hline
4 & 11 \\
\hline
5 & 23 \\
\hline
6 & 123 \\
\hline
7 & $101 \: 323 \: 373 \: 373$ \\
\hline
8 & $101 \: \underbrace{373 \: 373 \dots \dots \dots \dots \dots 373}_{\text{repeated $1 \; 018 \; 436 \; 987$ times}}$ \\
\hline
9 & ? \\
\hline
\end{tabular}
\caption{Minimal nonnegative integer requiring exactly $k$ iterations of
$\mathcal{W}$ to reach the fixed point.} \label{table:summary}
\end{center}
\end{table}
There are a number of additional problems that can be explored. The first would be to find additional terms in the sequence (that is, $\tau_9, \tau_{10}, \dots$).
Another is to modify the base function to not count spaces in the word, or to include the word $``\verb"and""$ where appropriate, or both (as was done in \seqnum{A227290} in Sloane \cite{sloan}).
And finally, another continuation problem would be to ask the same questions in other languages using the counting system prevalent in the associated country based on language and choice of appropriate scale (per Table \ref{table:scale}).
\vspace{0.2cm}
\section{Acknowledgement}
The author is grateful to Google for digitizing many of the older texts \cite{brooks, heath, holbrook, locke, loomis, pike1, pike2, slack, southey} that appear in the references.
\begin{thebibliography}{99}
\bibitem{washington} W.~Abbot, ed.,
{\it The Papers of George Washington, Confederation Series},
University Press of Virginia, Charlottesville, VA, 1997.
\bibitem{bgs} M.~Beeler, R.~Gosper, and R.~Schroeppel,
%Michael Beeler, Ralph William Gosper, Jr., and Richard Schroeppel
Memo AIM-239, MIT Artificial Intelligence Laboratory, Cambridge, MA, 1972,
\url{http://w3.pppl.gov/~hammett/work/2009/AIM-239-ocr.pdf}.
\bibitem{borgmann65} D.~Borgmann, %Dmitri
{\it Language on Vacation: An Olio of Orthographical Oddities},
Charles Scribner's Sons, 1965.
\bibitem{borgmann68-1} D.~Borgmann,
Naming the numbers,
{\it Word Ways:~J.~Rec.~Linguist.}~{\bf 1} (1968), 28--31.
\bibitem{borgmann68-2} D.~Borgmann,
Renaming the numbers,
{\it Word Ways:~J.~Rec.~Linguist.}~{\bf 1} (1968), 89--93.
\bibitem{brooks} E.~Brooks, %Edward
{\it The Philosophy of Arithmetic as Developed from the Three Fundamental Processes of Synthesis, Analysis, and Comparison:~Containing Also a History of Arithmetic},
Sower, Potts and Company, Philadelphia, PA, 1876.
\bibitem{cai} T.~Cai and X.~Zhou, On the heights of happy numbers,
{\it Rocky Mountain J.~Math.}~\textbf{38} (2008), 1921--1926.
\bibitem{cajori} F.~Cajori, % Florian
{\it The Teaching and History of Mathematics in the United States},
Washington Government Printing Office, 1890.
\bibitem{candelaria75} J.~Candelaria, %John
Extending the number names,
{\it Word Ways:~J.~Rec.~Linguist.}~{\bf 8} (1975), 141--142.
\bibitem{candelaria76} J.~Candelaria,
Renaming the extended numbers,
{\it Word Ways:~J.~Rec.~Linguist.}~{\bf 9} (1976), 39.
\bibitem{conway} J.~Conway and R.~Guy, % John H. Conway and Richard K. Guy
{\it The Book of Numbers},
Springer-Verlag, 1995.
\bibitem{ecker86} M.~Ecker, %Michael W. Ecker
Strange attractors and black holes (part 5),
{\it REC Newsl.}, Vol.~1, No.~6 (1986), 3--4.
\bibitem{ecker87} M.~Ecker,
Mathemagical black holes (part 9),
{\it REC Newsl.}, Vol.~2, No.~6 (1987), 6.
\bibitem{ecker99} M.~Ecker,
Number play, calculators, and card tricks: Mathemagical black holes,
in E. Berlekamp and T. Rodgers, eds., {\it The Mathemagician and Pied Puzzler:~A Collection in Tribute to Martin Gardner},
A.\ K. Peters, 1999, pp. 41--52.
\bibitem{flegg} G.~Flegg, C.~Hay, and B.~Moss, eds.,
{\it Nicolas Chuquet, Renaissance Mathematician},
%Graham Flegg, Cynthia Hay, and Barbara Moss
Reidel Publishing, Dordrecht, Holland, 1985.
\bibitem{gardner66} M.~Gardner, %Martin
Mathematical games,
{\it Sci.~Amer.}~{\bf 214} (1966), 112--115.
\bibitem{gardner90} M.~Gardner,
{\it The Magic Numbers of Dr. Matrix},
Prometheus, Buffalo, NY, 1985.
\bibitem{greenwood} I.~Greenwood,
{\it Arithmetick, Vulgar and Decimal, with the Application Thereof to a Variety of Cases in Trade and Commerce},
Kneeland and Green, Boston, MA, 1729.
\bibitem{grundman} H.~Grundman and E.~Teeple, Heights of happy numbers and cubic happy numbers,
{\it Fibonacci Quart.}~\textbf{41} (2003), 301--306.
\bibitem{guy} R.~Guy, %Richard K. Guy
{\it Unsolved Problems in Number Theory}, 2nd edition,
Springer-Verlag, 1994.
\bibitem{heath} N.~Heath, % Noble
{\it Treatise on Arithmetic:~Through Which the Entire Science Can be Most Expeditiously and Perfectly Learned Without the Aid of a Teacher},
T.~Ellwood Chapman, Philadelphia, PA, 1856.
\bibitem{henkle} W.~Henkle, %W.D.
Names of the periods in numeration,
{\it Ohio Educ.~Monthly:~J.~Sch.~Home Educ.}~{\bf 9} (1860), 151--153.
\bibitem{holbrook} A.~Holbrook, % Alfred
{\it The Normal:~or, Methods of Teaching the Common Branches, Orthoepy, Orthography, Grammar, Geography, Arithmetic and Elocution},
Barnes and Burr, New York, NY, 1859.
\bibitem{knn} E.~Kasner and J.~Newman, %Edward Kasner and James Newman
{\it Mathematics and the Imagination},
Simon and Schuster, NY, 1940.
\bibitem{kbr} B.~Kolman, R.~Busby, and S.~Ross, %Bernard Kolman, Robert Busby, and Sharon Cutler Ross
{\it Discrete Mathematical Structures}, 5th edition,
Pearson/Prentice Hall, 2004.
\bibitem{kravitz} S.~Kravitz, %Sidney
The lucky languages,
{\it J.~Recreational Math.}~{\bf 7} (1974), 225--228.
\bibitem{leonard} D.~Leonard,
Harvard's first science professor:~A sketch of Isaac Greenwood's life and work,
{\it Harv.~Libr.~Bull.}~{\bf 29} (1981), 135--168.
\bibitem{locke} J.~Locke, %John
{\it An Essay Concerning Human Understanding},
Thomas Bassett, London, UK, 1690.
\bibitem{loomis} S.~Loomis, % Silas Lawrence
{\it Normal Arithmetic:~A Text-book, Theoretical and Practical, in Six Parts},
J.B. Lippincott \& Co, Philadelphia, PA, 1859.
\bibitem{marre1} A.~Marre, ed., %Aristide
Notice sur Nicolas Chuquet et son Triparty en la sciences
des nombres,
{\it Boll.~Bibliogr.~Stor.~Sci.}~{\bf 13} (1880), 555--592.
\bibitem{marre2} A.~Marre, ed.,
Le Triparty en la sciences des nombres par Maistre Nicolas Chuquet, Parisien,
{\it Boll.~Bibliogr.~Stor.~Sci.}~{\bf 13} (1880), 593--658, 693--814.
\bibitem{marre3} A.~Marre, ed.,
Appendice au Triparty en la sciences des nombres de Nicolas Chuquet, Parisien,
{\it Boll.~Bibliogr.~Stor.~Sci.}~{\bf 14} (1881), 413--460.
\bibitem{moss} B.~Moss, %Barbara
Chuquet's mathematical executor: Could Estinenne de la Roche have changed the history of algebra?,
in C.~Hay, ed., {\it Mathematics from Manuscript to Print 1300--1600},
Clarendon Press, Oxford, 1988, pp.~117--126.
\bibitem{noll} L.~Noll, %Landon Curt Noll
How High Can You Count?,
\url{http://www.isthe.com/chongo/tech/math/number/howhigh.html}.
\bibitem{ondrejka} R.~Ondrejka, %Rudolf
From unillillion to ultimillillion,
{\it Word Ways:~J.~Rec.~Linguist.}~{\bf 9} (1976), 177--178.
\bibitem{pike1} N.~Pike, %Nicolas
{\it A New and Complete System of Arithmetic Composed for the Use Of The Citizens of the United States}, John Mycall, Newburyport, MA, 1788.
\bibitem{pike2} N.~Pike and C.~Dewey, %Nicolas Pike and Charles Dewey
{\it A New and Complete System of Arithmetick Composed for the Use Of The Citizens of the United States}, 4th edition, Parker, Troy, NY, 1822.
\bibitem{slack} E.~Slack, %Elijah
The origin of arithmetical symbols,
{\it Ohio J.~Educ.}~{\bf 2}
(1853), 214--221.
\bibitem{sloan} N.~J.~A.~Sloane, The On-Line Encyclopedia of Integer Sequences,
\url{http://oeis.org}.
\bibitem{smithd} D.~Smith, %David Eugene
{\it History of Mathematics, Vol.~2, Special Topics of Elementary Mathematics}, 1925. Reprinted by Dover, NY, 1958.
\bibitem{southey} R.~Southey, %Robert
{\it The Doctor, {\rm \&}c, Vol.~II},
Longman, Rees, Orme, Brown, Green and Longman, London, UK, 1834.
\bibitem{dictionary}
{\it Webster's Third New International Dictionary of the English Language Unabridged},
Merriam-Webster, Inc., 1993.
\bibitem{zerger} M.~Zerger, %Monte J.
Fatal attraction,
{\it Math.~Comput.~Educ.}~{\bf 27} (1993), 116--123.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}: Primary
00A08; Secondary 05A15, 01A99.
\noindent \emph{Keywords:}
recreational mathematics, height, numeration, generating function.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A001273},
\seqnum{A005589},
\seqnum{A227290}, and
\seqnum{A301408}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received July 6 2018;
revised versions received
October 1 2018; October 3 2018.
Published in {\it Journal of Integer Sequences}, December 5 2018.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}