# On fractal patterns in Ulam words

Andrei Mandelshtam111Department of Mathematics, Stanford University, Stanford,
CA 94305, USA<EMAIL_ADDRESS>
###### ?abstractname?

We show that already a seemingly simple set of Ulam words – those with two
$1$’s – possess an intricate intrinsic structure. We create a logarithmic-time
algorithm to determine whether any given such word is Ulam, uncovering
properties such as biperiodicity and various parity conditions, as well as
sharp bounds on the number of $0$’s outside the two $1$’s. We also discover
and prove that sets of Ulam words indexed by the number $y$ of $0$’s between
the two $1$’s have an inherent dual hierarchical structure, determined by the
arithmetic properties of $y.$ In particular, this allows us to construct an
infinite family of self-similar fractals $\tilde{U}(y)$ indexed by the set of
$2$-adic integers $y,$ containing for example the outward Sierpinski gasket as
$\tilde{U}(-1).$

##  1 Introduction

Many integer sequences have curious properties that are difficult to
understand. In 1964, Ulam  introduced one such sequence—the Ulam sequence [7].
It is inductively defined with $U_{1}=1,U_{2}=2,$ and $U_{n}$ being the
smallest positive integer not yet in the sequence that is expressible uniquely
as a sum of two distinct previous terms. The first few terms of the sequence
are $1,2,3,4,6,8,11,\dots.$ This sequence displays several interesting
periodicity and concentration properties that cannot be due to random
sampling. In 2015, Steinerberger performed a Fourier analysis on the first ten
million terms of the sequence and discovered that there is a value $\lambda$
such that all but four terms of the Ulam sequence fall into the central-half
interval modulo $\lambda$ [6]. Moreover, it is conjectured that for every
$\varepsilon>0$ all but finitely many Ulam numbers fall within $\varepsilon$
of the central third. These empirical observations give rise to an almost
linear-time algorithm to calculate successive Ulam numbers and also explain
some curious facts, such as that there are only four pairs of Ulam numbers
differing by $1$ [2].

More recently, it has become of interest to consider Ulam-type sequences and
sets in different contexts. For instance, Ulam sets in two dimensions display
a fascinating mixture of order and chaos [3]. Ulam-type multiplicative sets
can also be defined on the complex plane, which naturally lead to examining
Ulam sets in groups $\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}.$ In contrast with
the original Ulam sequence, Ulam sets in
$\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}$ can be finite [3].

In this paper, we will look specifically at the binary Ulam set $\mathcal{U},$
a set defined on the free group on two letters, conveniently denoted by $0$
and $1.$

######  Definition 1.1 ([1]).

Define $\mathcal{U}(1)=\\{0,1\\}.$ For each $n>1,$ inductively define
$\mathcal{U}(n)$ as the set of all length-$n$ words that are expressible
uniquely as a concatenation of two distinct words in $\mathcal{U}(i)$ and
$\mathcal{U}(j)$ for some $i,j<n.$ Then define
$\mathcal{U}=\bigcup\limits_{n=1}^{\infty}\mathcal{U}(n).$ Words in
$\mathcal{U}$ are called Ulam words.

(a) $(x,z)$ such that $0^{x}10^{276}10^{z}$ is Ulam

(b) $(x,z)$ such that $0^{x}10^{344}10^{z}$ is Ulam

(c) $(x,z)$ such that $0^{x}10^{400}10^{z}$ is Ulam

?figurename? 1: Fractal-type structures arising in the study of Ulam words
with two $1$’s. For complete descriptions of these phenomena, see Theorem
1.15.

Observe that the set of Ulam words is constructed in batches. This is possible
because two words of lengths $a,b>0$ can only be concatenated to form a word
of length strictly greater than both $a$ and $b.$ Thus, the Ulamness of all
words of any given length $n>0$ is independent. As we will see, it is
reasonable to consider other types of batches to construct Ulam words. Some
batch decompositions do have elements within one batch interacting with one
another, but in a much more controlled fashion. For example, if we layer words
based on the number of $1$’s (or $0$’s) that they contain, then the Ulamness
of a word $w$ with $k$ $1$’s depends only on that of words with fewer $1$’s
and two special words with $k$ $1$’s—one formed by removing the leftmost $0$
of $w$ and the other formed by removing the rightmost $0$ (Section 6).

Ulam words differ in many ways from the classical Ulam sequence. For instance,
the above batch-like structure of Ulam words allows for easy discovery of
classes of words that are known to be or not to be Ulam (e.g., palindromes of
odd length [1]), whereas Ulam numbers can only be constructed linearly, and
thereby it is much harder to determine any of their persistent or forbidden
properties.

The layers inherent to the binary Ulam set suggest that it may be possible to
explicitly describe its elements. However, even the counts of Ulam words of
each given length do not seem to follow any known patterns [4, A337361].
Nonetheless, restricting to specific types of words reveals very interesting
properties of the binary Ulam set. For example, we may choose to focus on the
number of instances of a letter in Ulam words. Note that Ulamness is preserved
under the symmetries of reversing and taking complements, so we may consider
specifically the count of $1$’s. A word with no $1$’s (or no $0$’s) is Ulam if
and only if its length is $1$ (i.e., it is $0$ or $1$). More interestingly, a
word with exactly one $1,$ i.e. of the form $\underbrace{00\cdots
0}_{m}1\underbrace{0\cdots 00}_{n}=:0^{m}10^{n}$ is Ulam if and only if
$\binom{m+n}{m}$ is odd [1], or, equivalently, if the binary representations
of $m$ and $n$ have no entries both equal to $1$ (2.2). By symmetry, this also
gives a characterization of all Ulam words with a single $0.$ We also see that
this provides an algorithm of logarithmic complexity (based on the length of a
word) to calculate whether the given word of such a type is Ulam.

In this paper, we consider the significantly more complicated case of Ulam
words with two $1$’s. We discover and fully describe fascinating hierarchical
structures embedded within the study of these words, as well as a family of
exceptions that we are also able to completely describe. We construct an
algorithm to completely classify all Ulam words with two $1$’s, which works in
logarithmic time to determine the Ulamness of any particular word, a
significant improvement over the $O(n^{3})$ time required for general words of
length $n.$

As it turns out, Ulam words with two $1$’s can be determined more simply than
just checking all possible concatenations. In fact, aside from $0$’s appended
from either side, the Ulamness of a word with two $1$’s is determined by
splitting it between the two $1$’s and checking the resulting Ulamness of the
two words with one $1$ each.

Then, in order to gain a better understanding of general Ulam sets, we can
look at them in finer detail—through what we call c-Ulam labelings. Precisely,
$\operatorname{c-Ulam}[y]:\mathbb{N}^{2}\to\\{0,1,2\\}$ labels every
coordinate $(x,z)$ with one of three ‘caveman’ labels: $0,$ meaning zero
representations of $0^{x}10^{y}10^{z}$ as a concatenation of Ulam words with
one $1$; $1,$ meaning one such representation; and $2,$ meaning two or more.

######  Remark 1.2.

The word ‘culam’ (kwlm) means ‘everybody’ in Hebrew. This can be interpreted
as sets $\operatorname{c-Ulam}[y]$ being responsible for the entire rich
structure of Ulam words with two $1$’s.

Let $\textit{Ulam}[y]\subset\mathbb{N}^{2}$ be the set of points $(x,z)$ for
which the corresponding word $0^{x}10^{y}10^{z}$ is Ulam. Then
$\operatorname{Ulam}[y]$ may seem to consist of $(x,z)$ labeled with $1$ by
$\operatorname{c-Ulam}[y].$ However, we should also take care of
representations either consisting of two equal words or those where one word
is $0$ and the other has both $1$’s. It turns out, however, that the structure
of $\operatorname{Ulam}[y]$ can be easily deduced by that of
$\operatorname{c-Ulam}[y].$ The exact structure depends on whether or not the
binary representation of $y$ possesses a special property.

######  Definition 1.3.

[4, A089633] A positive integer $y$ is called a Zumkeller number if it has at
most one $0$ in its binary representation.

######  Remark 1.4.

The name for these numbers was introduced by Shevelev in 2011 [5].

######  Theorem 1.5.

If $y$ is not a Zumkeller number, then $\operatorname{Ulam}[y]$ is simply the
set of $(x,z)$ where $x+z\equiv 1\pmod{2}$ and
$\operatorname{c-Ulam}[y](x,z)=1.$

Now, it is not difficult to observe that:

######  Lemma 1.6.

$\operatorname{c-Ulam}[y]$ is biperiodic with biperiod $2^{k+1}\times
2^{k+1},$ where $2^{k}\leq y<2^{k+1}.$

Yet, again, it is not immediately evident how we can translate this to
$\operatorname{Ulam}[y].$ The next theorem shows us that indeed we can, but
the exact result depends on whether $y$ is Zumkeller.

######  Theorem 1.7.

Suppose that $2^{k}\leq y<2^{k+1}.$

  * •

The set $\operatorname{Ulam}[y]$ is biperiodic if and only if $y$ is not a
Zumkeller number, and in this case it has a biperiod of $2^{k+1}\times
2^{k+1}.$

  * •

If $y$ is a Zumkeller number, then $\operatorname{Ulam}[y]$ is eventually
biperiodic with a biperiod of $2^{k+1}\times 2^{k+1}$; moreover, the only
aperiodicities (called “impurities”) occur in the bottom-left block: $(x,z)$
satisfying $x,z<2^{k+1}.$

This biperiodicity is useful in a number of other properties, one of which is
particularly intriguing.

######  Theorem 1.8.

If $y$ is odd and not a Zumkeller number, then
$\operatorname{Ulam}[y]=\operatorname{Ulam}[y-1].$ These sets also coincide
for Zumkeller $y$ outside of points $(x,z)$ that are impurities as in Theorem
1.7.

This result is surprising because the corresponding $\operatorname{c-Ulam}$
labelings look quite different for odd and even $y,$ as shown in Figure 2.

(a) $\operatorname{c-Ulam}[50]$

(b) $\operatorname{c-Ulam}[51]$

?figurename? 2: Here and in the future, squares labeled $0$ are in white; $1$
in gray; and $2$ in black.

(a) $\operatorname{Ulam}[50]$

(b) $\operatorname{Ulam}[51]$

Indeed, more points seem to be labeled $1$ in $\operatorname{c-Ulam}[50]$ than
in $\operatorname{c-Ulam}[51].$ Yet, Theorem 1.8 implies that the final
configurations of points with exactly one representation as a concatenation of
(distinct) Ulam words are the same.

Note that all above descriptions of $\operatorname{Ulam}[y]$ list Zumkeller
$y$ with $x,z<2^{k+1}$ as exceptions. This corresponds to the bottom left
block of $\operatorname{Ulam}[y],$ which we are able to fully describe for all
such $y.$

######  Theorem 1.9 (The case of Zumkeller $y$).

  * •

The set $\operatorname{Ulam}[2^{k+1}-1]$ consists of $(x,z)$ such that
$x+z\equiv-1\pmod{2^{k+1}}$ and $x+z\neq 2^{k+1}-1.$

  * •

The set $\operatorname{Ulam}[2^{k+1}-2]$ consists of $(x,z)$ such that either
$x+z\equiv-1\pmod{2^{k+1}}$ and $x+z\neq 2^{k+1}-1$; or $x+z=2^{k+1}-2$ and
$x,z\equiv 0\pmod{2}$; or $x+z=2^{k+1}$ and $x,z>0.$

  * •

Suppose $y=2^{k+1}-2^{a}-1$ is a Zumkeller number for some $0<a<k.$ Then
$\operatorname{Ulam}[y]$ is the set of $(x,z)$ such that either $x+z=y$ and
$x\pmod{2^{a+1}}<2^{a}$; or $x+z\equiv-1\pmod{2^{k+1}}$; or
$x\pmod{2^{k+1}}+z\pmod{2^{k+1}}=2^{k+1}+2^{a}-1.$

Now that $\operatorname{Ulam}[y]$ has been fully described for all Zumkeller
numbers $y,$ we can fully ignore this case and assume that the set is fully
biperiodic.

(a) $\operatorname{Ulam}[9]$

(b) $\operatorname{Ulam}[25]$

(c) $\operatorname{Ulam}[32]$

?figurename? 4: Biperiodic blocks of $\operatorname{Ulam}[y]$ for various $y.$

The more images we look at, the more evident it becomes that a large number of
$0$’s in the binary representation of $y$ creates a more fractal-like
structure. If there are $1$’s interspersed sporadically between the $0$’s,
then the structure becomes even richer, looking like a fractal made out of
fractals.

It is clear, then, that $\operatorname{Ulam}$ labelings and, even more
noticeably, $\operatorname{c-Ulam}$ labelings feature interesting fractal
patterns. To describe them precisely, we introduce procedures of ‘adding’ and
‘multiplying’ $\operatorname{c-Ulam}$ labelings. However, since we are
assigning the number $2$ to any word representable as a concatenation of Ulam
words in more than one way, we replace simple addition and multiplication by a
modified, ‘caveman’-style arithmetic:

######  Definition 1.10.

For integers $m,n\in\\{0,1,2\\},$ define the operations

$m\widehat{+}n:=\min(m+n,2)$

and

$m\widehat{\cdot}n:=\min(m\cdot n,2).$

In addition, our hierarchical description of $\operatorname{c-Ulam}[y]$
depends fundamentally on splitting into smaller squares and establishing a
given structure on each. In particular, we are reminded of the tensor product
operation, with $M\otimes N$ being a matrix tiled by blocks of the same
dimensions as $N,$ and with $(i,j)$-th entry equal to $m_{ij}N.$ Analogously,
we can define $M\widehat{\otimes}N$ being a matrix tiled by blocks
$m_{ij}\widehat{\cdot}N.$

Since we are now working with tilings by finite matrices, it is useful to
define the basic block used in these tilings. Precisely, let
$B_{d}=\\{0,1,2,\dots,2^{d}-1\\}^{2}$ be the fundamental periodic block of
$\operatorname{c-Ulam}[y]$ (for $y$ with $2^{d-1}\leq y<2^{d}$ as in Lemma
1.6). The following algorithm is then able to inductively construct
$\operatorname{c-Ulam}[y],$ implying, in particular, that for any $y,$ Ulam
words $0^{x}10^{y}10^{z}$ can also be determined in a logarithmic fashion.

######  Theorem 1.11.

There are universal dyadic patterns
$\operatorname{E_{1}},\operatorname{E_{2}},\operatorname{O_{1}},\operatorname{O_{2}}$
such that for all $d$ they give labelings
$\operatorname{E_{1}}[d],\operatorname{E_{2}}[d],\operatorname{O_{1}}[d],\operatorname{O_{2}}[d]:B_{d}\to\\{0,1,2\\}$
computable in $O(d)$ time and for any odd $y$ we have

$\operatorname{c-Ulam}[2^{d}y]=\operatorname{c-Ulam}[y-1]\widehat{\otimes}\operatorname{E_{1}}[d]\widehat{+}\operatorname{c-Ulam}[y]\widehat{\otimes}\operatorname{E_{2}}[d]$

and

$\operatorname{c-Ulam}[2^{d}y+1]=\operatorname{c-Ulam}[y-1]\widehat{\otimes}\operatorname{O_{1}}[d]\widehat{+}\operatorname{c-Ulam}[y]\widehat{\otimes}\operatorname{O_{2}}[d].$

The patterns
$\operatorname{E_{1}},\operatorname{E_{2}},\operatorname{O_{1}},\operatorname{O_{2}}$
are presented in the following table:

$\operatorname{E_{1}}$ |  | $\operatorname{O_{1}}$ |
---|---|---|---
$\operatorname{E_{2}}$ |  | $\operatorname{O_{2}}$ |
?tablename? 1: $E_{i}[d]$ and $O_{i}[d]$ for $d=5.$

The tensor product operation implies that every combination of two squares in
$\operatorname{c-Ulam}[y-1]$ and $\operatorname{c-Ulam}[y]$ gives two
different unique patterns in $\operatorname{c-Ulam}[2^{d}y]$ and
$\operatorname{c-Ulam}[2^{d}y+1].$ Table 2 provides the precise conversion
chart implied by Theorem 1.11:

$\operatorname{c-Ulam}[y-1]$ | $\operatorname{c-Ulam}[y]$ | $\operatorname{c-Ulam}[2^{d}y]$ | $\operatorname{c-Ulam}[2^{d}y+1]$
---|---|---|---
|  |  |
|  |  |
|  |  |
|  |  |
|  |  |
|  |  |
?tablename? 2: The labelings of $(x,z)$ in $\operatorname{c-Ulam}[2^{d}y]$ and
$\operatorname{c-Ulam}[2^{d}y+1]$ given the labelings of
$(x^{\prime},z^{\prime})$ in $\operatorname{c-Ulam}[y]$ and
$\operatorname{c-Ulam}[y-1]$; $x^{\prime}=\lfloor\frac{x}{2^{d}}\rfloor,$
$z^{\prime}=\lfloor\frac{z}{2^{d}}\rfloor.$ Case shown: $d=5.$

For example, the periodic patterns of $\operatorname{c-Ulam}[2^{d}]$ and
$\operatorname{c-Ulam}[2^{d}+1]$ are tiled by three blocks in the third and
fourth columns, respectively:

(a) $\operatorname{c-Ulam}[32]$

(b) $\operatorname{c-Ulam}[33]$

We can analogously flip our tensor operation. However, we must then restrict
ourselves to single periodic blocks.

######  Theorem 1.12.

Suppose $2^{k}\leq y<2^{k+1}.$ Define the labelings $L,S:B_{k}\to\\{0,1,2\\}$
by

$L(x,z):=\operatorname{c-Ulam}[y](x,2^{k}+z)=\operatorname{c-Ulam}[y](2^{k}+x,z)$

and

$S(x,z):=\operatorname{c-Ulam}[y](2^{k}+x,2^{k}+z).$

Then we have

$\operatorname{c-Ulam}[2^{\ell}+y]_{\big{|}_{B_{\ell+1}}}=\operatorname{c-Ulam}[2^{\ell-k}]_{\big{|}_{B_{\ell-k+1}}}\widehat{\otimes}S\widehat{+}\operatorname{c-Ulam}[2^{\ell-k}+1]_{\big{|}_{B_{\ell-k+1}}}\widehat{\otimes}L.$

(a) $\operatorname{c-Ulam}[273]\quad\quad\quad\quad\qquad\qquad$

(b) $\operatorname{c-Ulam}[17]$

?figurename? 6: Since $273=16*17+1=256+17,$ the resulting labeling
$\operatorname{c-Ulam}[273]$ has the structure of $\operatorname{c-Ulam}[17]$
looking both externally and internally.

These theorems allow us to also prove several sharp and surprising properties
of the structure of $\operatorname{Ulam}[y],$ determining simple litmus tests
for the set.

######  Theorem 1.13.

Suppose $2^{k}\leq y<2^{k+1},$ and let $x^{\prime}$ and $z^{\prime}$ be the
reductions of $x$ and $z,$ respectively, modulo $2^{k+1}.$

  1. 1.

If there exist $(x,z)\in\operatorname{Ulam}[y]$ with $x+z<2^{k+1}-1,$ then $y$
is a Zumkeller number.

  2. 2.

If $y$ is not a Zumkeller number, then $(x,z)\in\operatorname{Ulam}[y]$ only
if $2^{k+1}-1\leq x^{\prime}+z^{\prime}\leq 2^{k+2}-y-2.$ If $y$ is a
Zumkeller number, then the previous inequality is true unless
$x+z\in\\{y,y+1,y+2\\}.$

  3. 3.

If $y\not\in\\{2^{k+1}-1,2^{k+1}-2\\},$ then $(x,z)\in\operatorname{Ulam}[y]$
for all $x+z\equiv-1\pmod{2^{k+1}}.$ If $y=2^{k+1}-1$ or $y=2^{k+1}-2,$ then
the same result holds except when $x+z=2^{k+1}-1.$

  4. 4.

For all $y,$ we have $(x,z)\in\operatorname{Ulam}[y]$ whenever
$x^{\prime}+z^{\prime}=2\left\lfloor\frac{2^{k+2}-y-3}{2}\right\rfloor+1.$

######  Remark 1.14.

In particular, Item 1 improves a bound set in [1] (see Lemma 2.4).

?figurename? 7: The periodic building block for $\operatorname{Ulam}[117].$
Diagonals $(x,z)$ satisfying $x+z=127$ and $x+z=137$ are completely filled,
and all other elements are in between them.

Notably, we show the existence of two full diagonals in the periodic block of
$\operatorname{Ulam}[y]$—one corresponding to $x+z=2^{k+1}-1$ and one
corresponding to $x+z=2^{k+2}-2\left\lceil\frac{y+1}{2}\right\rceil-1,$ and
show that the entire contents of the block are in between these two diagonals.
However, these theorems do not immediately make obvious the beautifully dual
hierarchical nature of Ulam sets. To understand it better, we first need to
define exactly what we mean by said hierarchy. The precise definitions
themselves are somewhat technical and presented fully in Definitions 3.1 and
3.2. But in short, an ‘internal’ $i_{d_{1},d_{2},\dots,d_{s}}$ hierarchical
structure consists of taking entries in a given labeling and ‘blowing them
up’; based on two previous labelings of a given entry, it is replaced by a new
(universal) dyadic pattern of size $2^{d_{i}}\times 2^{d_{i}}$; this is done
inductively for $i$ from $s$ to $1.$ Almost inversely, an ‘external’
$e_{d_{1},d_{2},\dots,d_{s}}$ hierarchical structure consists of taking a
given pattern, dividing it into four equal blocks, and tiling a given
$2^{d_{i}}\times 2^{d_{i}}$ block $B$ with them, one empty pattern, and one
pattern filling all non-empty labels in the same (in our case black) way,
based on the parity and initial labeling of the entries of $B$; this is done
inductively for $i$ from $1$ to $s.$ Interestingly, our
$\operatorname{c-Ulam}$ labeling presents both of these types of hierarchies!

######  Theorem 1.15 (Hierarchical structure).

Suppose that

$y=\sum_{i=1}^{s}2^{d_{1}+\cdots+d_{i}}=1\underbrace{00\cdots
0}_{d_{s}-1}1\cdots 1\underbrace{0\cdots 00}_{d_{1}},$

or

$y=1+\sum_{i=1}^{s}2^{d_{1}+\cdots+d_{i}}=1\underbrace{00\cdots
0}_{d_{s}-1}1\cdots 1\underbrace{0\cdots 00}_{d_{1}-1}1,$

where $d_{i}\geq 1$ for all $i.$ Then $\operatorname{c-Ulam}[y]$ has both
$i_{d_{1},d_{2},\dots,d_{s}}$ and $e_{d_{1},d_{2},\dots,d_{s}}$ hierarchical
structure.

While the internal hierarchical structure $i_{d_{1},d_{2},\dots,d_{s}}$ does
make a finite-step fractal shape, after any given step, no label is
necessarily fixed, as each small square is blown up to create a large square
with a relatively arbitrary labeling. Yet, with the external structure
$e_{d_{1},d_{2},\dots,d_{s}},$ the situation is different. Instead of being
tiled arbitrarily within, the blocks (and their parts) now become the tiles
themselves. Continuing this process infinitely, we can in fact make
infinitely-hierarchical sets corresponding to $2$-adic integers.

Precisely, for any $2$-adic integer $\tilde{y}\not\in\mathbb{N}$ with
approximants $y_{i}\in\mathbb{N},$ if we extend the periodic structure of
$\operatorname{c-Ulam}[y_{i}]$ into the fourth (or second) quadrant, then they
naturally converge to a fractal as $y_{i}\to_{2}\tilde{y}.$

Namely, set $Q=\mathbb{N}\times\\{-1-\mathbb{N}\\}\subset\mathbb{Z}^{2}$
(where $\\{-1-\mathbb{N}\\}=\\{-1,-2,\cdots\\}$). Equip the space $S$ of
labelings of $Q$ with a natural metric as in Definition 3.3. First, suppose
$2^{k}\leq y<2^{k+1},$ and define $\tilde{U}(y):Q\to\\{0,1,2\\}$ by

$\tilde{U}(y)(x,z)=\operatorname{c-Ulam}[y](x,z^{\prime})$

for some $z^{\prime}$ satisfying $z^{\prime}\equiv z\pmod{2^{k+1}}$ and
$z^{\prime}\geq 0$ (this is well-defined because $\operatorname{c-Ulam}[y]$ is
periodic in any direction with period $2^{k+1}$). For any
$\tilde{y}\in\mathbb{Z}_{2}\backslash\mathbb{N},$ define

$\tilde{U}(\tilde{y})(x,z)=\tilde{U}(y^{\prime})(x,z)$

for any $y^{\prime}\geq x,\left|z\right|$ such that $\tilde{y}\equiv
y^{\prime}\pmod{2^{k+1}}$ for some $2^{k+1}>y^{\prime}.$ Such a $y^{\prime}$
can indeed be found because the binary expansion of $\tilde{y}$ has infinitely
many $1$’s.

######  Theorem 1.16.

The map $\tilde{U}:\mathbb{Z}_{2}\to S$ is well-defined everywhere and
continuous at all $y\in\mathbb{Z}_{2}\backslash\mathbb{N}.$

######  Remark 1.17.

It is additionally possible to naturally extend the definition of external
hierarchical structure to an infinite setting. Then, it is not hard to see
that for a $2$-adic number $y=\\{0,1\\}+2^{d_{1}}+2^{d_{1}+d_{2}}+\cdots,$ the
set $\tilde{U}(y)$ possesses $e_{d_{1},d_{2},\dots}$ hierarchical structure.

(a) $\tilde{U}(-1)$

(b) $\tilde{U}(\sqrt{-7})$

(c) $\tilde{U}(2/3)$

?figurename? 8: Fractal shapes for choices of
$y\in\mathbb{Z}_{2}\backslash\mathbb{N}.$

######  Remark 1.18.

The fractal $\tilde{U}(-1)$ simply gives the label $2$ to all points except
the top diagonal, which is labeled with $1,$ of the regular Sierpinski gasket.

This paper is organized as follows. In Sections 2 and 3, we discuss prior
relevant results and introduce some definitions. In Section 4, we discuss the
curious effect of the update step and how it is essentially a triviality. As a
result, this allows us to prove Theorems 1.5 and 1.8. However, Theorem 1.7 is
delayed to Section 5, where we fully describe the special case of Zumkeller
numbers listed as exceptions in the previous theorems, with our full
description given in Theorem 1.9. In Section 6, we prove the general
descriptions of $\operatorname{c-Ulam}[y]$ for all $y,$ in particular proving
Theorems 1.11, 1.12, 1.15, and 1.16. In Section 7, we use the general
description to prove several surprising facts in Theorem 1.13.

##  2 Preliminaries

We begin with some notation that we will use extensively throughout the paper.

######  Definition 2.1.

For nonnegative integers $x_{1},x_{2},\dots,x_{n},$ let the word
$w(x_{1},x_{2},\dots,x_{n})$ consist of $x_{1}$ $0$’s followed by a $1,$
followed by $x_{2}$ $0$’s followed by another $1,$ and so on, ending with
$x_{n}$ $0$’s. More concisely, it is $0^{x_{1}}10^{x_{2}}1\cdots 10^{x_{n}}.$

Prior to this paper, Ulam words of type $w(x,y)$ were fully classified, as
stated in the introduction: $w(x,y)$ is Ulam if and only if $\binom{x+y}{x}$
is odd. However, this binomial coefficient quickly becomes large and difficult
to compute, so we now recall Lucas’s criterion:

######  Proposition 2.2 (Lucas).

The binomial coefficient $\binom{x+y}{x}$ is odd if and only if the binary
expansions of $x$ and $y$ never both have a $1$ in the same place value.

Thus, in reality we can simply look at the binary expansions of $x$ and $y$ to
determine whether $w(x,y)$ is Ulam. Notably, if $w(x,y)$ is Ulam and either
$x$ or $y$ is odd, then the other is even.

Ulam words $w(x,y,z)$ have also been studied, and the following facts are
known.

######  Lemma 2.3 ([1]).

The word $w(x,0,z)$ is Ulam if and only if $x+z$ is odd. The word $w(x,1,z)$
is Ulam if and only if $x+z$ is odd and $x+z>1.$

######  Lemma 2.4 ([1]).

If $w(x,y,z)$ is Ulam, then $x+z\geq y.$

Our results, particularly those of Section 4, rely repeatedly on basic facts
about the Ulamness of some words in relation to others. Precisely, we have the
following useful fact:

######  Lemma 2.5.

An even number (zero or two) of the words $w(x,y),w(x,y-1),w(x-1,y)$ are Ulam.

######  ?proofname? .

The identity $\binom{x+y}{x}=\binom{x+y-1}{x}+\binom{x+y-1}{x-1}$ tells us
that either zero or two of these binomial coefficients are odd; now recall
that $w(a,b)$ is Ulam if and only if $\binom{a+b}{a}$ is odd.∎

##  3 Defining hierarchical structures

Typically, a self-similar fractal structure features a sequence of scales, at
each of which the same pattern is repeated. Here, however, the situation is
more complex, so we need to introduce more general definitions to describe the
hierarchies inherent in $\operatorname{c-Ulam}$ labelings. Essentially, the
two below definitions correspond to tiling a set in $\mathbb{N}^{2}$ either
from the inside out or from the outside in, and account for several universal
patterns of tiling present in the structure.

######  Definition 3.1 (Internal hierarchy).

Fix some (labeling) set $T$333In our case, $T=\\{0,1,2\\}.$. For any
nonnegative integer $d,$ fix maps $I_{d}^{e},I_{d}^{o}:T\times
T\to\mathcal{P}^{d},$ where $\mathcal{P}^{d}$ is a set of some labelings
$L:B_{d}\to T.$ We may typically assume that the labelings $\mathcal{P}^{d}$
all belong to a common family $\mathcal{P},$ e.g. as in Table 2.

For any nonnegative integers $d_{1},d_{2},\dots,d_{s},$ a labeling
$\mathcal{L}:B_{d_{1}+d_{2}+\cdots+d_{s}+1}\to T$ exhibits
$i_{d_{1},d_{2},\dots,d_{s}}$ hierarchical structure with respect to
$\mathcal{P}$ if we have
$c_{j}^{e},c_{j}^{o}:B_{d_{j}+d_{j+1}+\cdots+d_{s}+1}\to T,j=1,\dots,s,$ and
$c_{s+1}^{e},c_{s+1}^{o}:B_{1}\to T$ satisfying the inductive relations

$\displaystyle
c_{j}^{e}(x,z)=I_{d_{j}}^{e}(c_{j+1}^{e}(x^{\prime},z^{\prime}),c_{j+1}^{o}(x^{\prime},z^{\prime}))(x^{\prime\prime},z^{\prime\prime})$
$\displaystyle
c_{j}^{o}(x,z)=I_{d_{j}}^{o}(c_{j+1}^{e}(x^{\prime},z^{\prime}),c_{j+1}^{o}(x^{\prime},z^{\prime}))(x^{\prime\prime},z^{\prime\prime})$

and $\mathcal{L}=c_{1}^{e}$ or $c_{1}^{o},$ where $x^{\prime},z^{\prime}$ are
the first (counting $0$’s) $d_{j+1}+d_{j+2}+\cdots+d_{s}+1$ digits and
$x^{\prime\prime},z^{\prime\prime}$ are the last $d_{j}$ digits, respectively,
of $x,z$ in binary.

In our definition, $\mathcal{L}=c_{1}^{o}$ occurs in the case when the final
hierarchy is ‘odd’. Specifically, it occurs in $\operatorname{c-Ulam}[y]$ when
$y$ is odd.

######  Definition 3.2 (External hierarchy).

Fix some (labeling) set $T$ and ‘empty’ label $t\in T,$ as well as ‘full’
label $f\in T.$ Fix a map $I:T\times T\to\\{0,1,2,3,4,5\\}.$ Also, for every
$d$ and $i\in\\{0,1,2,3\\}$ fix labelings $L_{d,i}^{e},L_{d,i}^{o}:B_{d}\to
T.$

For any nonnegative integers $d_{1},d_{2},\dots,d_{s},$ a labeling
$\mathcal{L}:B_{d_{1}+d_{2}+\cdots+d_{s}+1}\to T$ exhibits
$e_{d_{1},d_{2},\dots,d_{s}}$ hierarchical structure with respect to $L$ if we
have, for $i\in\\{0,1,2,3,4,5\\},$ labelings
$c_{j}^{i}:B_{d_{1}+d_{2}+\cdots+d_{j}}\to T$ satisfying $c_{j}^{4}(x,z)=t$
and $c_{j}^{5}(x,z)=\begin{cases}t&c_{j}^{3}(x,z)=t,\\\ f&c_{j}^{3}(x,z)\neq
t,\end{cases}$ and, for $i<4,$ we have

$c_{j}^{i}(x,z)=c_{j-1}^{I(L_{d_{j},i}^{e}(x^{\prime\prime},z^{\prime\prime}),L_{d_{j},i}^{o}(x^{\prime\prime},z^{\prime\prime}))}(x^{\prime},z^{\prime})$

and

$c_{s}^{0}(x,z)=\mathcal{L}(x,z),\quad
c_{s}^{1}(x,z)=\mathcal{L}(\overline{1x},z),\quad
c_{s}^{2}(x,z)=\mathcal{L}(x,\overline{1z}),\quad
c_{s}^{3}(x,z)=\mathcal{L}(\overline{1x},\overline{1z})$

where $x^{\prime},z^{\prime}$ are the trailing $d_{1}+\cdots+d_{j-1}$ digits
and $x^{\prime\prime},z^{\prime\prime}$ are the first $d_{j}$ digits (counting
$0$’s), respectively, of $x,z$ in binary, and
$\overline{1x}=2^{d_{1}+d_{2}+\cdots+d_{s}}+x$ (resp.,
$\overline{1z}=2^{d_{1}+d_{2}+\cdots+d_{s}}+z$) is the binary number defined
by inserting a $1$ in the $(d_{1}+d_{2}+\cdots+d_{s}+1)$-th slot from the
right of the binary representation of $x.$

In our case, $T$ is simply the set $\\{0,1,2\\},$ and the ‘trivial’ label is
$t=0,$ while the ‘full’ label is $s=2.$ The labelings $\mathcal{P}^{d}$ are
exactly those in Table 2, and $L_{d,i}^{e}$ and $L_{d,i}^{o}$ each give four
labelings of $B_{d}$ partitioning $\operatorname{c-Ulam}[2^{d}].$ Precisely,
they are the fourth, third, third, and second figures, respectively, of the
third and fourth columns, respectively, of Table 2.

Recall from the introduction that Definition 3.2 allows us to construct an
infinite, self-similar fractal for every $2$-adic integer. However, it is
essential that we define a form of convergence for these fractal shapes.

######  Definition 3.3.

Set $Q=\mathbb{N}\times\\{-1-\mathbb{N}\\}.$ For a given set $T,$ define a
metric $\rho$ on the set of labelings $Q\to T$ as follows:
$\rho(L_{1},L_{2})=\frac{1}{d}$ where $d$ is the largest integer (perhaps
$\infty$) such that $L_{1}(m,n)=L_{2}(m,n)$ for all $m,\left|n\right|\leq d.$

##  4 Parity phenomena in $\operatorname{Ulam}[y]$

First, we discuss a more understandable general procedure to determine whether
a word of the form $0^{x}10^{y}10^{z}$ is Ulam. Observe that a sequence of
$0$’s (or $1$’s) is Ulam if and only if it has length exactly $1.$ An Ulam
word must be expressible uniquely as a concatenation of two smaller (Ulam)
words, so we must understand in what ways this can happen. The words are
determined by ‘slicing’ $w$ between two letters:

$w=00\cdots 010\cdots 0\mid 0\cdots 010\cdots 0.$

By the previous reasoning, the slice may not be past the second $0$ but before
the first $1,$ or past the second $1$ but before the second-to-last $0.$ Thus,
the slice is either directly after the first $0,$ directly before the last
$0,$ or somewhere in between the two $1$’s. In the former two cases, the word
is formed from a $0$ and another word of the form
$0^{x^{\prime}}10^{y}10^{z^{\prime}}$ (where either $x^{\prime}=x-1$ and
$z^{\prime}=z,$ or $x^{\prime}=x$ and $z^{\prime}=z-1$; if $x=0$ or $z=0$ then
one or both of these cases may disappear). The latter case, however, is more
complicated. There are $y+1$ total positions for the slice, each of which
splits the $y$ $0$’s into two groups: one of size $a$ and another of size
$y-a$ (where either may be $0$). The corresponding words are then
$0^{x}10^{a}$ and $0^{y-a}10^{z}.$ Note also that we require the words to be
distinct. If one of the words is $0$ and the other contains both $1$’s, then
this is not an issue. However, we may run into problems if $w(x,a)=w(y-a,z),$
which happens if $x=y-a$ and $a=z.$ This implies that $x+z=(y-a)+a=y.$ Note
that this is the equality case of Lemma 2.4. It seems from the outset as if
both words in the concatenation having a single $1$ dominates the arguments,
and indeed it does; the remaining two possible representations can in fact be
considered separately. Observe that in all of these representations, either
the words in the concatenation representation have one $1$ each, or the number
$y$ of $0$’s in between the two $1$’s does not change. Thus, it makes sense to
layer Ulam words with two $1$’s based on the distance between them; separate
layers will not interact whatsoever.

Whether $w(x,y,z)$ is an Ulam word then depends, inductively, only on several
previous words: $w(x-1,y,z)$ and $w(x,y,z-1),$ as well as $w(x,a)$ and
$w(y-a,z)$ for $0\leq a\leq y.$ Instead of considering all of these words as
once, we can split the process of determining Ulam words in a calculation step
and an update step.

The calculation step will incorporate only the words $w(x,a)$ and $w(y-a,z)$
in the determination. After this, each word $w(x,y,z)$ is expressible as a
concatenation in either zero, one, or at least two ways. If there are at least
two expressions, then the word can be immediately discarded; there is no
chance for it to be Ulam, even after considering $w(x-1,y,z)$ and
$w(x,y,z-1).$ If, on the other hand, there is exactly one representation, then
the word is Ulam if and only if neither $w(x-1,y,z)$ nor $w(x,y,z-1)$ is Ulam.
Finally, if there are no representations, then the word is Ulam if and only if
exactly one of $w(x-1,y,z)$ and $w(x,y,z-1)$ is Ulam; we will show, in
particular, that this case in fact never occurs.

All in all, we can therefore create a tentative scheme for Ulam and non-Ulam
words:

######  Definition 4.1.

The word $w(x,y,z)$ is non-Ulam if there are at least two representations
prior to considering $w(x-1,y,z)$ and $w(x,y,z-1)$; it is pseudo-Ulam if there
is exactly one representation, and it is probably not Ulam if there are no
representations.

######  Remark 4.2.

The choice to label the final case of words $w(x,y,z)$ with no representations
as probably not Ulam is due to the fact (that we will prove later) that they
are never Ulam.

In the update step, we inductively determine whether
$w(x^{\prime},y,z^{\prime})$ is Ulam for all $x^{\prime}\leq x,z^{\prime}\leq
z$ satisfying $x^{\prime}+z^{\prime}<x+z,$ and then $w(x,y,z)$ is Ulam if and
only if either it is pseudo-Ulam and $w(x-1,y,z)$ and $w(x,y,z-1)$ (if they
exist) are non-Ulam, or it is probably not Ulam and exactly one of
$w(x-1,y,z)$ and $w(x,y,z-1)$ is Ulam.

The first calculation step of the algorithm unfortunately has the caveat that
it has to consider the case when $w(x,y,z)=w(x,z)*w(x,z)$ is split into two
equal Ulam words, violating the condition that the words must be distinct,
which slightly derails some further arguments. Nevertheless, we can in fact
significantly bound the instances when this affects further calculations.

######  Lemma 4.3.

Suppose $y=x+z$ is not Zumkeller. If $w(x,z)$ is Ulam, then there are at least
two decompositions of $w(x,y,z)$ as a concatenation of distinct Ulam words
$w(x,a)*w(y-a,z).$ In particular, $w(x,y,z)$ is not Ulam and
$\operatorname{c-Ulam}[y](x,z)=2.$

######  ?proofname?.

As noted above, $x$ and $z$ share no $1$’s in their binary representation. By
assumption, $y$ has at least two $0$’s in its binary representation and hence
is of the form

$y=c_{m}c_{m-1}\cdots c_{1}0b_{\ell}b_{\ell-1}\cdots b_{1}0a_{k}a_{k-1}\cdots
a_{1}$

for some $a_{h},b_{i},c_{j}\in\\{0,1\\}.$

Assume first that there are $1$’s between the two $0$’s, so then we may assume
without loss of generality that $b_{1}=c_{1}=1.$ Observe that $y=x+z$ and the
sum of $x$ and $z$ in binary has no carrying. Hence, the entries of $x$ and
$z$ at all the (at least two) entries of $y$ that are $0$ are also $0$ (since
of the pairs $0,1$; $1,0$; $0,0$ only two $0$’s sum to $0$). Therefore, we can
write

$x=c_{m}^{x}c_{m-1}^{x}\cdots c_{1}^{x}0b_{\ell}^{x}b_{\ell-1}^{x}\cdots
b_{1}^{x}0a_{k}^{x}a_{k-1}^{x}\cdots a_{1}^{x},\hskip
3.61371ptz=c_{m}^{z}c_{m-1}^{z}\cdots
c_{1}^{z}0b_{\ell}^{z}b_{\ell-1}^{z}\cdots
b_{1}^{z}0a_{k}^{z}a_{k-1}^{z}\cdots a_{1}^{z}.$

Then consider slightly altering both as follows:

$x^{\prime}=c_{m}^{x}c_{m-1}^{x}\cdots
c_{2}^{x}01b_{\ell}^{x}b_{\ell-1}^{x}\cdots
b_{1}^{x}0a_{k}^{x}a_{k-1}^{x}\cdots a_{1}^{x},\hskip
1.4457ptz^{\prime}=c_{m}^{z}c_{m-1}^{z}\cdots
c_{2}^{z}01b_{\ell}^{z}b_{\ell-1}^{z}\cdots
b_{1}^{z}0a_{k}^{z}a_{k-1}^{z}\cdots a_{1}^{z}.$

Observe that $x^{\prime}+z^{\prime}=y$ and $x,z^{\prime}$ still share no $1$’s
in their binary representations, and neither do $x^{\prime},z.$ Therefore, we
have $w(x,y,z)=w(x,z^{\prime})*w(x^{\prime},z)$ is a representation of
$w(x,y,z)$ as a concatenation of (distinct) Ulam words. Similarly, it is
possible to define

$x^{\prime\prime}=c_{m}^{x}c_{m-1}^{x}\cdots
c_{1}^{x}0b_{\ell}^{x}b_{\ell-1}^{x}\cdots
b_{2}^{x}01a_{k}^{x}a_{k-1}^{x}\cdots a_{1}^{x},\hskip
1.4457ptz^{\prime\prime}=c_{m}^{z}c_{m-1}^{z}\cdots
c_{1}^{z}0b_{\ell}^{z}b_{\ell-1}^{z}\cdots
b_{2}^{z}01a_{k}^{z}a_{k-1}^{z}\cdots a_{1}^{z}$

and then $w(x,y,z)=w(x,z^{\prime\prime})*w(x^{\prime\prime},z)$ is another
representation of $w(x,y,z)$ as a concatenation of Ulam words. Hence, in fact
the existence of $w(x,y,z)=w(x,z)*w(x,z)$ as a representation in this case is
not relevant; regardless, $w(x,y,z)$ is not Ulam (since it has two other
representations).

Now, suppose $y$ has two consecutive zeroes together; consider the leftmost
such pair so that there is a $1$ to the left of them. We can then write

$y=b_{\ell}b_{\ell-1}\cdots b_{2}100a_{k}a_{k-1}\cdots a_{1}$

and

$x=b_{\ell}^{x}b_{\ell-1}^{x}\cdots b_{1}^{x}00a_{k}^{x}a_{k-1}^{x}\cdots
a_{1}^{x},\hskip 3.61371ptz=b_{\ell}^{z}b_{\ell-1}^{z}\cdots
b_{1}^{z}00a_{k}^{z}a_{k-1}^{z}\cdots a_{1}^{z}.$

Note that $b_{1}^{x}+b_{1}^{z}=1$ so exactly one of the two is $1.$ Then
consider

$x^{\prime}=b_{\ell}^{x}b_{\ell-1}^{x}\cdots
b_{2}^{x}011a_{k}^{x}a_{k-1}^{x}\cdots a_{1}^{x},\hskip
3.61371ptz^{\prime}=b_{\ell}^{z}b_{\ell-1}^{z}\cdots
b_{2}^{z}001a_{k}^{z}a_{k-1}^{z}\cdots a_{1}^{z}.$

Observe that $x^{\prime}+z^{\prime}=y,$ $x$ and $z^{\prime}$ share no $1$’s in
their binary representations, and neither do $z$ and $x^{\prime}.$ Thus,
$w(x,y,z)=w(x,z^{\prime})*w(x^{\prime},z)$ is a representation of $w(x,y,z)$
as a concatenation of Ulam words. Similarly, if we define

$x^{\prime\prime}=b_{\ell}^{x}b_{\ell-1}^{x}\cdots
b_{2}^{x}001a_{k}^{x}a_{k-1}^{x}\cdots a_{1}^{x},\hskip
3.61371ptz^{\prime\prime}=b_{\ell}^{z}b_{\ell-1}^{z}\cdots
b_{2}^{z}011a_{k}^{z}a_{k-1}^{z}\cdots a_{1}^{z},$

then $w(x,y,z)=w(x,z^{\prime\prime})*w(x^{\prime\prime},z)$ is a second such
representation. Hence, by the same reasoning as before, $w(x,y,z)$ is not Ulam
(independent of $w(x,z)$ being Ulam). ∎

The splitting of the algorithm into two steps is particularly useful because,
except in one very special case (when $y$ is $2$ less than a power of $2$),
the update step is in fact quite simple to describe; it will just remove all
pseudo-Ulam words satisfying $x+z\equiv 0\pmod{2}.$ However, in order to
understand how this works, we need to understand the fundamental reason why
these words are removed.

######  Lemma 4.4.

Suppose that $x+z\equiv 0\pmod{2}$ and $y\neq 2^{k+1}-2.$ If $w(x,y,z)$ is
pseudo-Ulam, then the words $w(x-1,y,z)$ and $w(x,y,z-1)$ are both also
pseudo-Ulam.

###### ?proofname?.

The proof fundamentally relies on constructing parity-based bijections between
the single representation of $w(x,y,z)$ and the resulting unique
representations of $w(x-1,y,z)$ and $w(x,y,z-1).$

First, by the condition that $x+z\equiv 0\pmod{2},$ the only possibility for
$x+z=y$ is if $y$ is even. However, we then see that $y$ is not Zumkeller as
by assumption it does not equal $2^{k+1}-2.$ In particular, by Lemma 4.3, a
representation of $w(x,y,z)$ as a concatenation of equal Ulam words does not
affect the final state of $w(x,y,z).$ If $x+z\neq y,$ then there are no such
representations so this is a non-issue regardless. Thus, we will assume
without loss of generality that any representation of $w(x,y,z)$ consists of
distinct Ulam words.

By assumption, there is exactly one such representation, i.e., $0\leq a\leq y$
such that $w(x,a)$ and $w(y-a,z)$ are distinct Ulam words. Without loss of
generality, assume that $a\neq z.$ We now split into cases based on the parity
of $x+z.$

######  Case 1.

If $x,z$ are odd, then observe that

$w(x-1,y,z)=w(x-1,a)*w(y-a,z)$

is a representation as a concatenation of two (distinct since $a\neq z$) Ulam
words. Suppose by way of contradiction that there is also some other
representation

$w(x-1,y,z)=w(x-1,b)*w(y-b,z).$

Then $b$ must be odd, as otherwise $w(x,b)*w(y-b,z)$ is an additional
representation of $w(x,y,z).$ On the other hand, $y-b$ is even because $z$ is
odd. Therefore, $y$ is odd and so one of $a,y-a$ is odd. But this is a
contradiction since then one of $w(x,a)$ and $w(y-a,z)$ is non-Ulam (because
both $x$ and $z$ are odd). Hence, there can be no other representation and so
$w(x-1,y,z)$ is pseudo-Ulam. Observe that $x\neq y-a$ as well because
otherwise $y-a$ is odd and so $w(y-a,z)$ is not Ulam. Therefore, by similar
reasoning $w(x,y,z-1)$ is also pseudo-Ulam.

######  Case 2.

Now, suppose instead that $x,z$ are both even. Since there is a unique $a$
such that $w(x,a)$ and $w(y-a,z)$ are Ulam and distinct, we must have that for
any other $a^{\prime}$ the words $w(x,a^{\prime})$ and $w(y-a^{\prime},z)$
cannot both be Ulam. If $y$ were odd, then exactly one of $a$ and $y-a$ would
be odd, without loss of generality $a,$ so then

$w(x,y,z)=w(x,a-1)*w(y-a+1,z)$

would be an alternative representation as a concatenation of (distinct due to
parity) Ulam words, contradicting uniqueness. Thus, $y$ is even. It is now
important to consider the parity of $a.$

######  Case 2.1.

If $a$ and $y-a$ are both even, then observe that $w(y-a+1,z)$ is a valid Ulam
word since $z$ is even and $y-a$ is even as well. But
$w(x,y,z)=w(x,a-1)*w(y-a+1,z),$ so either the words are the same or one is not
Ulam. Trivially the words are distinct because $x$ and $y-a+1$ are of
different parities. Therefore, we must have that $w(x,a-1)$ is not Ulam.
Hence, by Lemma 2.5, $w(x-1,a)$ is Ulam. In particular, we obtain a
representation

$w(x-1,y,z)=w(x-1,a)*w(y-a,z)$

as a concatenation of distinct (since $a\neq z$) Ulam words. We now show that
no other such representation exists. Supposing we also had

$w(x-1,y,z)=w(x-1,b)*w(y-b,z)$

for some $b\neq a,$ we immediately notice that $b$ must be even (since $x-1$
is odd), and so $y-b$ is as well. But observe that $y-b$ is even and so is
$z,$ so $w(y-b+1,z)$ is also Ulam. Again by Lemma 2.5, exactly one of $w(x,b)$
and $w(x,b-1)$ is Ulam. In particular, we have either an additional (since
$b\neq a$ by assumption and $b-1\neq a$ because $b$ is even) representation

$w(x,y,z)=w(x,b)*w(y-b,z)\text{ or }w(x,y,z)=w(x,b-1)*w(y-b+1,z)$

of $w(x,y,z)$ as a concatenation of distinct (by the argument in the second
paragraph of the proof) Ulam words, a contradiction.

Hence, $w(x-1,y,z)$ has a unique representation as a concatenation of distinct
Ulam words, so it is pseudo-Ulam. If $x\neq y-a,$ then the same argument as
above works to show that $w(x,y,z-1)$ is also pseudo-Ulam. Otherwise,
$w(x,y,z)=w(x,a)*w(x,z)$ is the unique representation. In particular, again we
see that $w(x,z-1)$ is Ulam. The only issue in the above argument that may
arise is if $a=z-1,$ so that the resulting representation
$w(x,y,z-1)=w(x,a)*w(x,z-1)$ consists of two equal words. But this is
impossible, as both $a$ and $z$ were assumed to be even. Hence, $w(x,y,z-1)$
is still pseudo-Ulam, as desired.

######  Case 2.2.

If, now, $a$ and $y-a$ are both odd, then observe that $w(y-a-1,z)$ is Ulam
since $y-a$ is odd. But since $w(x,y,z)$ is pseudo-Ulam, we cannot have
$w(x,y,z)=w(x,a+1)*w(y-a-1,z)$ as an alternate representation of $w(x,y,z)$ as
a concatenation of two (distinct by assumption) Ulam words. Therefore, one of
the words in the representation must not be Ulam—specifically, $w(x,a+1).$
Hence, by Lemma 2.5, $w(x-1,a+1)$ is Ulam. This therefore gives a
representation

$w(x-1,y,z)=w(x-1,a+1)*w(y-a-1,z).$

The words are distinct because $x-1\neq y-a-1$ by parity. We now show that no
other such representation exists. To this end, suppose we have an alternate
decomposition

$w(x-1,y,z)=w(x-1,b)*w(y-b,z),$

where $b\neq a+1.$ Observe that $b$ is even since $x-1$ is odd, and thus since
$y$ is even, we must have that $y-b$ is even as well. But therefore, since $z$
is even, we must have that $w(y-b+1,z)$ is also Ulam. As before, by Lemma 2.5,
exactly one of $w(x,b)$ or $w(x,b-1)$ is Ulam. In particular, we have either
an additional (since $b\neq a+1$ by assumption and $b-1\neq a+1$ by parity)
representation

$w(x,y,z)=w(x,b)*w(y-b,z)\text{ or }w(x,y,z)=w(x,b-1)*w(y-b+1,z)$

of $w(x,y,z)$ as a concatenation of Ulam words, in any case a contradiction.
Thus, $w(x-1,y,z)$ has no additional representations, so it must be pseudo-
Ulam. Similarly, so is $w(x,y,z-1).$

Hence, if $w(x,y,z)$ is pseudo-Ulam, then both $w(x-1,y,z)$ and $w(x,y,z-1)$
are as well, as desired. ∎

Therefore, if pseudo-Ulam words $w(x,y,z)$ with odd $x+z$ are Ulam, then those
with even $x+z$ are not. However, we could still have issues with $w(x,y,z)$
with even $x+z$ that are probably not Ulam. We now show that these are in fact
unaffected.

######  Lemma 4.5.

Suppose $w(x,y,z)$ is Ulam and $y\neq 2^{k+1}-2.$ Then $x+z\equiv 1\pmod{2}.$

This means, in particular, that the update step cannot alter the state of any
$w(x,y,z)$ with $x+z\equiv 1\pmod{2},$ as neither $w(x-1,y,z)$ nor
$w(x,y,z-1)$ can be Ulam.

###### ?proofname?.

Our proof incorporates Lemma 4.4, from which it is evident that it suffices by
induction (the base case being words of the form $w(0,y,0),$ all of which are
trivially not Ulam because of the representations $1*w(y,0)$ and $w(0,y)*1$)
to show that probably not Ulam words $w(x,y,z)$ with $x+z\equiv 0\pmod{2}$ are
not Ulam. Indeed, assuming this fact, suppose that all words $w(x,y,z)$ with
$x+z<n$ and $x+z\equiv 0\pmod{2}$ are not Ulam. If $w(x,y,z)$ with
$x+z=n\equiv 0\pmod{2}$ is Ulam, then it must be pseudo-Ulam. But then it is
not Ulam since both $w(x-1,y,z)$ and $w(x,y,z-1)$ are pseudo-Ulam and hence,
by the inductive hypothesis, Ulam (thereby completing the inductive step). As
in the proof of Lemma 4.4, we may assume that any potential representation of
$w(x,y,z)$ consists of distinct Ulam words.

Assume, therefore, that $w(x,y,z)$ is probably not Ulam (it cannot be
expressed as $w(x,a)*w(y-a,z)$ for any $0\leq a\leq y$). Note that this
implies that $x,z>0$; if not, then without loss of generality $z=0,$ so then
we have $w(x,y,0)=w(x,0)*w(y,0),$ which is a decomposition of $w(x,y,0)$ into
two Ulam words that are distinct as long as $x\neq y.$ Therefore, $w(x,y,0)$
is either pseudo-Ulam or not Ulam. If, on the other hand, $x=y,$ then first
recall that $x+z=x\equiv 0\pmod{2}$ (by our assumption), so $x$ is even. In
particular, $w(x,1)$ is Ulam, and so we have the decomposition into Ulam words
$w(x,x,0)=w(x,1)*w(x-1,0),$ which works as long as $x\neq 0,$ which holds
because $x=0$ was the base case. Hence, $w(x,x,0)$ is also either pseudo-Ulam
or not Ulam.

Assuming now that $x,z>0,$ we wish to show that among $w(x-1,y,z)$ and
$w(x,y,z-1),$ either neither or both are Ulam. By the induction hypothesis,
the latter condition is equivalent to these words both being pseudo-Ulam. We
in fact construct a bijection between their representations. Consider,
therefore, any decomposition of

$w(x-1,y,z)=w(x-1,a)*w(y-a,z)$

into (distinct) Ulam words. Now by assumption, there are no representations of
$w(x,y,z)$ as a concatenation of Ulam words with one $1.$ But then $w(x,a)$
cannot be Ulam, as otherwise we would have the (distinct by assumption)
representation $w(x,y,z)=w(x,a)*w(y-a,z).$ Thus, by Lemma 2.5, $w(x,a-1)$ is
Ulam. Moreover, considering the decomposition $w(x,y,z)=w(x,a-1)*w(y-a+1,z),$
we see that $w(y-a+1,z)$ is not Ulam, implying again by Lemma 2.5 that
$w(y-a+1,z-1)$ is Ulam. Then we get the representation

$w(x,y,z-1)=w(x,a-1)*w(y-a+1,z-1).$

The words in the decomposition are distinct because (from the above
decomposition of $w(x-1,y,z)$) either $x-1\neq y-a$ or $a\neq z.$ In
particular, we have constructed a map from representations of $w(x-1,y,z)$ as
a concatenation of distinct Ulam words to those of $w(x,y,z-1).$ But the same
reverse map can be constructed, and it is easy to see that they are inverses.
Thus, decompositions of $w(x-1,y,z)$ and $w(x,y,z-1)$ are in bijection and so
they have the same state, as desired.

In summary, we see that when $x+z\equiv 0\pmod{2},$ if $w(x,y,z)$ is pseudo-
Ulam or probably not Ulam, then after the update step it is simply not Ulam.
This completes the inductive step.

If, on the other hand, $x+z\equiv 1\pmod{2},$ then by the inductive hypothesis
we have that neither $w(x-1,y,z)$ nor $w(x,y,z-1)$ is Ulam, so $w(x,y,z)$ is
Ulam if and only if it has a unique representation as a concatenation of
distinct Ulam words with one $1$—i.e. it is pseudo-Ulam. This also completes
the inductive step. ∎

######  Corollary 4.6 (Theorem 1.5).

If $y$ is not a Zumkeller number, then $\operatorname{Ulam}[y]$ is the set of
$(x,z)$ such that $x+z\equiv 1\pmod{2}$ and $\operatorname{c-Ulam}[y](x,z)=1.$

###### ?proofname?.

Suppose $w(x,y,z)$ is Ulam. By Lemma 4.5, we know immediately that $x+z\equiv
1\pmod{2},$ and by Lemma 4.3, if $x+z=y,$ then $w(x,z)$ is not Ulam. In
addition, since $x+z\equiv 1\pmod{2},$ we now see that neither $w(x-1,y,z)$
nor $w(x,y,z-1)$ is Ulam, again by Lemma 4.5, and so all possible
representations of $w(x,y,z)$ as a concatenation of two Ulam words are of the
form $w(x,a)*w(b,z).$ Moreover, we know that the words must be distinct since
$w(x,z)*w(x,z)$ cannot be a valid representation (even if $x+z=y$). But this
means that there are exactly $\operatorname{c-Ulam}[y](x,z)$-many
representations of $w(x,y,z)$ as a concatenation of two distinct Ulam words,
implying since $w(x,y,z)$ is Ulam that $\operatorname{c-Ulam}[y](x,z)=1.$
Thus, one direction is proved.

Conversely, if we do indeed have $x+z\equiv 1\pmod{2}$ and
$\operatorname{c-Ulam}[y](x,z)=1,$ then again by Lemma 4.3, the word $w(x,z)$
is not Ulam if $x+z=y.$ Thus, there exists a unique representation
$w(x,y,z)=w(x,a)*w(b,z),$ and the words must be distinct. Since $x+z\equiv
1\pmod{2},$ we know that neither $w(x-1,y,z)$ nor $w(x,y,z-1)$ is Ulam. Hence,
there exists a unique representation of $w(x,y,z)$ as a concatenation of two
distinct Ulam words, and thus $w(x,y,z)$ is indeed Ulam, as desierd. ∎

For $y=2^{k+1}-2,$ things are slightly more complicated. It is Zumkeller, so
the case of $x+z=y$ becomes relevant. In particular, in the set of Ulam words
$w(x,y,z),$ there are exceptional cases with $x+z$ even.

######  Lemma 4.7.

Suppose $y=2^{k+1}-2$ for some $k>0$ and say $w(x,y,z)$ is Ulam. Then
$x+z\equiv 1\pmod{2}$ unless $x+z=2^{k+1}-2$ or $x+z=2^{k+1}.$ In the former
case, $w(x,y,z)$ is Ulam if and only if $x,z\equiv 0\pmod{2}$ and in the
latter, if and only if $x,z>0.$

###### ?proofname?.

In this proof, we quantify the error produced by ignoring representations of
words $w(x,y,z)$ as concatenations of equal Ulam words in our proof of Lemma
4.5. We also observe that this error propagates past the case
$x+z=y=2^{k+1}-2,$ in fact all the way to $x+z=2^{k+1}.$ As a consequence, we
need to investigate each of these cases separately.

The only place in our proof where we actually used that $y\neq 2^{k+1}-2$ was
when arguing that in representations of $w(x,y,z)$ as a concatenation of Ulam
words, the words can be assumed to be distinct. This only arises as an issue
when:

######  Case 1.

$x+z=y=2^{k+1}-2$ (and note that $w(x,y,z)$ is not Ulam whenever $x+z<y$) and
moreover only if both $x$ and $z$ are even; if $x,z$ are both odd, then
$w(x,z)$ is not Ulam. If, on the other hand, $x,z$ are both even with
$x+z=2^{k+1}-2,$ then we now prove that $w(x,2^{k+1}-2,z)$ is indeed Ulam. To
see this, note that $\frac{x}{2}+\frac{z}{2}=2^{k-1}-1.$ In particular, if we
write the binary representation of

$\frac{x}{2}=a_{k}a_{k-1}\cdots a_{1},$

then

$\frac{z}{2}=b_{k}b_{k-1}\cdots b_{1},$

where $b_{i}=1-a_{i}.$ Observe, then, that if we have a decomposition into
Ulam words

$w(x,2^{k+1}-2,z)=w(x,a)*w(2^{k+1}-2-a,z)$

where $a$ is even, then $2^{k+1}-2-a$ is even and the words being Ulam is
equivalent (since the binary representations of $x,a,2^{k+1}-2-a,z$ all end
with $0$) to the words $w(x/2,a/2)$ and $w(2^{k}-1-a/2,z/2)$ being Ulam. By
the same reasoning, we can write the binary representations

$\frac{a}{2}=c_{k}c_{k-1}\cdots c_{1}$

and

$2^{k}-1-\frac{a}{2}=d_{k}d_{k-1}\cdots d_{1}\quad\quad\quad\hskip 5.42003pt$

where $d_{i}=1-c_{i}.$ Since $w(x/2,a/2)$ and $w(2^{k}-1-a/2,z/2)$ are both
Ulam, the corresponding two elements share no $1$’s in their binary
representations. In particular, for every $i,$ we have that $a_{i}+c_{i}\leq
1$ and $b_{i}+d_{i}=2-a_{i}-c_{i}\leq 1.$ Thus, both sums in fact equal $1$
and so $a_{i}=1-c_{i}=d_{i}$ and $b_{i}=1-d_{i}=c_{i}.$ Hence,
$x/2=2^{k}-1-a/2$ and $a/2=z/2,$ so $x=2^{k+1}-2-a$ and $a=z.$ Thus, the
decomposition splits into two equal Ulam words and is not valid. Hence, any
valid decomposition into distinct Ulam words must have $a$ (and thus
$2^{k+1}-2-a$) be odd.

Say then that $a=b+1$ and so $2^{k+1}-2-a=2^{k+1}-3-b.$ Then we can once again
cut off the last digits to see that $w(x,a)$ is Ulam if and only if
$w(x/2,b/2)$ is Ulam and $w(2^{k+1}-2-a,z)$ is Ulam if and only if
$w(2^{k}-2-b/2,z/2)$ is Ulam. If both are Ulam, then we have an Ulam
decomposition of $w(x/2,2^{k}-2,z/2)$:

$w\left(\frac{x}{2},2^{k}-2,\frac{z}{2}\right)=w\left(\frac{x}{2},\frac{b}{2}\right)*w\left(2^{k}-2-\frac{b}{2},\frac{z}{2}\right).$

Now, observe that $x/2+z/2=2^{k}-1,$ in particular exactly one of the two is
odd, say without loss of generality that it is $x/2.$ Then note that $b/2$
must be even in order for $w(x/2,b/2)$ to be Ulam, and therefore so must
$2^{k}-2-b/2.$ But then observe that $w(x/2,b/2)$ is Ulam if and only if
$w((x/2-1)/2,b/4)$ is (since the last two digits are $1$ and $0$ and thus not
both $1$) and $w(2^{k}-2-b/2,z/2)$ is Ulam if and only if
$w(2^{k-1}-1-b/4,z/4)$ is. Observe, however, that

$w\left(\frac{x-2}{4},2^{k-1}-1,\frac{z}{4}\right)=w\left(\frac{x-2}{4},\frac{b}{4}\right)*w\left(2^{k-1}-1-\frac{b}{4},\frac{z}{4}\right)$

is a decomposition into Ulam words, and thus decompositions of
$w((x-2)/4,2^{k-1}-1,z/4)$ into (not necessarily distinct) Ulam words
correspond to those of $w(x/2,2^{k}-2,z/2),$ which in turn correspond to
decompositions of $w(x,2^{k+1}-2,z)$ into distinct Ulam words (the words are
distinct by a parity argument). Recall the binary representations

$\frac{x-2}{4}=a_{k}a_{k-1}\cdots a_{2}$

and

$\frac{z}{4}=b_{k}b_{k-1}\cdots b_{2},$

where $b_{i}=1-a_{i}.$ If we have a decomposition

$w\left(\frac{x-2}{4},2^{k-1}-1,\frac{z}{4}\right)=w\left(\frac{x-2}{4},c\right)*w\left(d,\frac{z}{4}\right),$

where

$c=c_{k}c_{k-1}\cdots c_{2}$

and

$d=d_{k}d_{k-1}\cdots d_{2},$

then note that $c+d=2^{k-1}-1$ and thus $c_{i}=1-d_{i}.$ By the same reasoning
as before, we eventually deduce that in fact, for all $i,$ we have
$a_{i}=d_{i}$ and $b_{i}=c_{i},$ implying that $\frac{x-2}{4}=d$ and
$\frac{z}{4}=c.$ Therefore, the unique decomposition is

$w\left(\frac{x-2}{4},2^{k-1}-1,\frac{z}{4}\right)=w\left(\frac{x-2}{4},\frac{z}{4}\right)*w\left(\frac{x-2}{4},\frac{z}{4}\right),$

which therefore leads to a unique decomposition of $w(x,2^{k+1}-2,z)$;
precisely, in this case—$x\equiv 2\pmod{4}$—the decomposition is

$w(x,2^{k+1}-2,z)=w(x,z+1)*w(x-1,z).$

From this we deduce that $w(x,2^{k+1}-2,z)$ with $x+z=2^{k+1}-2$ is Ulam, and
equivalently by Lemma 2.4, pseudo-Ulam, if and only if $x\equiv z\equiv
0\pmod{2}.$ This discrepancy from what is expected (that $x+z\equiv
1\pmod{2}$), unfortunately, has the adverse effect of propagating slightly
further due to the update step. However, we can quantify exactly how far it
does so.

######  Case 2.

We will now deduce that $w(x,2^{k+1}-2,z)$ with $x+z=2^{k+1}-1$ is not Ulam;
in fact, we explicitly construct two representations of it as a concatenation
of smaller Ulam words. Luckily, these are not too difficult to construct.
Since $x+z$ is odd, exactly one of $x,z$ is, too; say, without loss of
generality, that it is $x.$ Then $x-1$ and $z$ are both even and sum to
$2^{k+1}-2,$ in particular we know that $w(x-1,2^{k+1}-2,z)$ is Ulam. Thus, we
immediately obtain the representation

$w(x,2^{k+1}-2,z)=0*w(x-1,2^{k+1}-2,z).$

The words are trivially distinct, so this is a valid representation. The other
representation is also simple; since $x+z=2^{k+1}-1,$ their binary
representations are complementary and thus do not share any $1$’s. Hence,
$w(x,z)$ is Ulam. Since $x$ is odd, the word $w(x-1,z)$ is also Ulam. Thus, we
have the representation

$w(x,2^{k+1}-2,z)=w(x,z)*w(x-1,z)$

as a concatenation of trivially distinct Ulam words.

Now, we know that some (in fact, all) words $w(x,2^{k+1}-2,z)$ with
$x+z=2^{k+1}-1$ that previously would have been Ulam are not, anymore.
Therefore, we have to go one more step further.

######  Case 3.

Consider words $w(x,2^{k+1}-2,z)$ with $x+z=2^{k+1}.$ First, there are the two
cases $x=0$ or $z=0.$ To resolve them, we have the two representations

$w(0,2^{k+1}-2,2^{k+1})=w(0,2^{k+1}-2)*w(0,2^{k+1})=w(0,0)*w(2^{k+1}-2,2^{k+1}).$

These two representations are distinct (since $k>0$), so
$w(0,2^{k+1}-2,2^{k+1})$ and, symmetrically, $w(2^{k+1},2^{k+1}-2,0)$ are not
Ulam. With this, we may assume that $x,z>0.$

Note that $x+z=2^{k+1}$ and neither is $0,$ so both are strictly less than
$2^{k+1}.$ In particular, if $2^{a}$ divides $x,$ then it divides
$z=2^{k+1}-x=2^{a}(2^{k+1-a}-x/2^{a}),$ and vice versa. Therefore, $x$ and $z$
have the same exponent of $2,$ so say that we can write them as
$x=2^{a}x^{\prime},z=2^{a}z^{\prime}$ with $x^{\prime},z^{\prime}$ being odd.
Observe that any representation as a concatenation of Ulam words

$w(x,2^{k+1}-2,z)=w(x,c)*w(d,z)$

is valid if and only if, correspondingly, $w(x^{\prime},c^{\prime})$ and
$w(d^{\prime},z^{\prime})$ are both Ulam, where
$c^{\prime}=\lfloor\frac{c}{2^{a}}\rfloor$ and
$d^{\prime}=\lfloor\frac{d}{2^{a}}\rfloor$ (the last $a$ digits of $x$ and $z$
are $0$ so they are irrelevant; the $i$-th digit from the right cannot be $1$
for both $x$ and $c$ or for both $d$ and $z$). Now, note that
$2^{a}c^{\prime}\leq c<2^{a}(c^{\prime}+1),$ and the same for $d^{\prime},$ so
$2^{a}(c^{\prime}+d^{\prime})\leq 2^{k+1}-2<2^{a}(c^{\prime}+d^{\prime}+2).$
The only way for this to happen is if $c^{\prime}+d^{\prime}=2^{k+1-a}-2$ or
$2^{k+1-a}-1.$ The latter cannot happen, as $x^{\prime}$ and $z^{\prime}$ are
both odd, so $c^{\prime}$ and $d^{\prime}$ are both even (and so is their
sum). Thus, we must have $c^{\prime}+d^{\prime}=2^{k+1-a}-2.$ We see that
$w(x^{\prime},c^{\prime})$ and $w(d^{\prime},z^{\prime})$ are then Ulam if and
only if, respectively, $w(x^{\prime}-1,c^{\prime})$ and
$w(d^{\prime},z^{\prime}-1)$ are. But observe that
$(x^{\prime}-1)+(z^{\prime}-1)=c^{\prime}+d^{\prime}=2^{k+1-a}-2$ and so we
have a decomposition into (not necessarily distinct) Ulam words of

$w(x^{\prime}-1,2^{k+1-a}-2,z^{\prime}-1)=w(x^{\prime}-1,c^{\prime})*w(d^{\prime},z^{\prime}-1),$

where $x^{\prime}-1,c^{\prime},d^{\prime},z^{\prime}-1$ are even. But we know
from the above arguments that only one such decomposition exists—when
$c^{\prime}=z^{\prime}-1$ and $d^{\prime}=x^{\prime}-1.$ Thus, we have fixed
all but the last $a$ digits of any $c$ and $d,$ giving a valid decomposition
of $w(x,2^{k+1}-2,z)$ into Ulam words with one $1.$ To determine the last $a$
digits, define $c^{\prime\prime}=c-2^{a}c^{\prime}$ and
$d^{\prime\prime}=d-2^{a}d^{\prime},$ and observe that these are exactly the
last $a$ digits of $c$ and $d,$ respectively. But now, note that $0\leq
c^{\prime\prime},d^{\prime\prime}\leq 2^{a}-1$ by definition of $c^{\prime}$
and $d^{\prime},$ and we have

$c^{\prime\prime}+d^{\prime\prime}=(c+d)-2^{a}(c^{\prime}+d^{\prime})=2^{k+1}-2-2^{a}(x^{\prime}+z^{\prime}-2)=2^{k+1}+2^{a+1}-2-(x+z)=2^{a+1}-2.$

This immediately implies that $c^{\prime\prime}=d^{\prime\prime}=2^{a}-1,$ and
so they must be fixed as well. Thus, there is a unique representation of
$w(x,2^{k+1}-2,z)$ as a concatenation of (distinct) Ulam words with one
$1$—precisely,

$w(x,2^{k+1}-2,z)=w(x,z-1)*w(x-1,z);$

these are trivially distinct. Hence, $w(x,2^{k+1}-2,z)$ is pseudo-Ulam, and,
since no words $w(x,2^{k+1}-2,z)$ with $x+z=2^{k+1}-1$ are Ulam, it is in fact
Ulam. Note that this holds for all $x,z$ with $x,z>0$ (and $x+z=2^{k+1}$).

So far, we now know that there are Ulam words $w(x,2^{k+1}-2,z)$ with either
$x+z=2^{k+1}-2$ or $x+z=2^{k+1}.$ One may think that the propagation continues
to occur, but luckily, the next step is the last.

######  Case 4.

We now prove that there are no representations for $w(x,2^{k+1}-2,z)$ with
$x+z=2^{k+1}+1$ and $x,z>1$ as a concatenation of (distinct) Ulam words with
one $1.$ We also show that $w(x-1,2^{k+1}-2,z)$ and $w(x,2^{k+1}-2,z-1)$ are
both Ulam, and thus $w(x,2^{k+1}-2,z)$ is not Ulam. Thus, the Ulam status of
words $w(x,2^{k+1}-2,z)$ with $x+z=2^{k+1}$ does not affect any of these
(since they are non-Ulam regardless). However, we must separately consider the
case when one of $x,z$ is $0$ or $1.$ Observe that the state of the words
$w(0,2^{k+1}-2,2^{k+1}+1)$ and $w(2^{k+1}+1,2^{k+1}-2,0)$ in fact does not
matter, since they can only be affected by $w(0,2^{k+1}-2,2^{k+1})$ and
$w(2^{k+1},2^{k+1}-2,0),$ respectively, both of which are non-Ulam.
Additionally, consider the two representations of

$w(2^{k+1},2^{k+1}-2,1)=w(2^{k+1},0)*w(2^{k+1}-2,1)=w(2^{k+1},2^{k+1}-2)*w(0,1)$

as a concatenation of distinct Ulam words, implying that it is not Ulam, and,
symmetrically, neither is $w(1,2^{k+1}-2,2^{k+1}),$ as desired.

Suppose now that $x,z>1.$ Since $x+z=2^{k+1}+1,$ exactly one of $x,z$ is odd,
say without loss of generality it is $x.$ Note that $x,z>1,$ so $x-1,z>0.$ Any
valid decomposition of $w(x,2^{k+1}-2,z)=w(x,a)*w(b,z)$ into Ulam words
implies that $a$ is even, and thus $w(x-1,a)$ is also Ulam. This, in turn,
gives a decomposition $w(x-1,2^{k+1}-2,z)=w(x-1,a)*w(b,z).$ But then the case
of $x+z=2^{k+1}$ applies, allowing us to deduce that the only possible valid
decomposition of $w(x-1,2^{k+1}-2,z)$ is

$w(x-1,2^{k+1}-2,z)=w(x-1,z-1)*w(x-2,z).$

Yet, this decomposition truly being valid would imply that the original
decomposition is

$w(x,2^{k+1}-2,z)=w(x,z-1)*w(x-2,z).$

Since $x$ and $z-1$ are both odd, the word $w(x,z-1)$ is not Ulam, and thus
this is not a valid decomposition. In other words, $w(x,2^{k+1}-2,z)$ has no
valid decompositions as a concatenation of two Ulam words with one $1.$ On the
other hand, both $w(x-1,2^{k+1}-2,z)$ and $w(x,2^{k+1}-2,z-1)$ are Ulam, since
$x+z-1=2^{k+1}$ and $x,z>1$ so $x-1,z-1>0.$

Thus, $w(x,2^{k+1}-2,z)$ is not Ulam regardless of the update step, implying
that for any $x,z$ with $x+z>2^{k+1},$ the update step once again begins to
behave as it normally would—removing all words $w(x,y,z)$ with $x+z\equiv
0\pmod{2}$ and ignoring words with $x+z\equiv 1\pmod{2},$ as desired. ∎

This indicates that the update step is essentially null; unless $y=2^{k+1}-2$
(in which case we can explicitly describe exceptions), we can simply ignore
$w(x,y,z)$ with $x+z\equiv 0\pmod{2},$ as we immediately know that they are
not Ulam, and all other words are Ulam if and only if they have exactly one
representation as a sum of distinct Ulam words $w(x,a)*w(y-a,z).$

Meanwhile, the calculation step simply examines the interactions of binomial
coefficients modulo $2.$ In particular, it will preserve the fascinating
phenomenon of biperiodicity.

######  Lemma 4.8.

Suppose $2^{k}\leq y<2^{k+1}$ and $y$ is not a Zumkeller number. Then
$\operatorname{Ulam}[y]$ is biperiodic with biperiod $2^{k+1}\times 2^{k+1}.$

######  Remark 4.9.

The question may arise as to whether any smaller biperiod is possible, but in
fact $2^{k+1}\times 2^{k+1}$ is minimal; for example, it is not hard to see
that $w(x,y,0)$ and $w(0,y,z)$ are Ulam if and only if
$x,z\equiv-1\pmod{2^{k+1}}.$

###### ?proofname?.

By Lemma 4.5, it suffices to prove biperiodicity following the calculation
step. Specifically, we will show that $w(x,y,z)$ for $x+z\equiv 1\pmod{2}$ is
Ulam (equivalently, pseudo-Ulam) if and only if its reduction
$w(x^{\prime},y,z^{\prime})$ is Ulam (pseudo-Ulam), where $x^{\prime}\equiv
x,z^{\prime}\equiv z\pmod{2^{k+1}}.$

Suppose $\binom{x+a}{x}$ and $\binom{z+y-a}{z}$ are both odd. Also, either
$x+z\neq y$ or we also have the condition $x\neq y-a$ (in fact, the case
$x+z=y$ is exactly where biperiodicity may break). By 2.2, we see that $a$ and
$x$ share no $1$’s in their binary representations, and neither do $y-a$ and
$z.$ But observe that $a,y-a\leq y<2^{k+1},$ so they can only have $1$’s in
the last $k+1$ digits of the binary expansion. In particular, adding or
subtracting multiples of $2^{k+1}$ to $x$ and $z$ does not change the
condition that $\binom{x+a}{x}$ and $\binom{z+y-a}{z}$ are both odd. Thus, it
is true if and only if it is true when $x$ and $z$ are considered modulo
$2^{k+1}.$ But pseudo-Ulam and probably not Ulam is exactly counting instances
of $a$ such that $\binom{x+a}{x}$ and $\binom{z+y-a}{z}$ are both odd (and
said instances occur $1$ and $0$ times, respectively). Since this does not
depend on $x,z\pmod{2^{k+1}},$ we therefore can deduce that $w(x,y,z)$ is
pseudo-Ulam (resp. probably not Ulam) if and only if its reduction
$w(x^{\prime},y,z^{\prime})$ is as well, except perhaps when
$x^{\prime}+z^{\prime}=y.$ Precisely, the issue of words needing to be
distinct becomes significant when $w(x^{\prime},z^{\prime})$ is Ulam (since
$w(x^{\prime},y,z^{\prime})=w(x^{\prime},z^{\prime})*w(x^{\prime},z^{\prime})$).
However, by Lemma 4.3 (noting that $y$ satisfies the lemma conditions), the
state of $w(x,y,z)$ is unchanged whether $w(x,z)$ is Ulam or not; relevant
representations will still continue to carry over modulo $2^{k+1}.$ In
particular, we indeed have that in all cases, $w(x,y,z)$ is in the same state
as its reduction $w(x^{\prime},y,z^{\prime}),$ and so the desired set is
biperiodic. ∎

This result implies that, in order to more properly understand Ulam words
$w(x,y,z),$ in reality we only have to understand those satisfying $x,z\leq
2^{k+1}$—the ‘first square.’ Looking more precisely at graphs of
$\operatorname{Ulam}[y]$ for various $y,$ we notice that increasing even $y$
by $1$ does not change the resulting set, except for the occasional
imperfection. We now prove this result.

######  Lemma 4.10.

If $y$ is odd and not a Zumkeller number, then
$\operatorname{Ulam}[y]=\operatorname{Ulam}[y-1].$

###### ?proofname?.

Note that $y-1$ only has more $0$’s in its binary representation and thus is
also not a Zumkeller number. In particular, by Lemma 4.5, both
$\operatorname{Ulam}[y]$ and $\operatorname{Ulam}[y-1]$ contain only
coordinates $(x,z)$ satisfying $x+z\equiv 1\pmod{2},$ and that $w(x,y,z)$
and/or $w(x,y-1,z)$ satisfying the modular condition are Ulam if and only if
they are pseudo-Ulam. It remains to show that these coordinates are the same.
To this end, for any $(x,z)$ with $x+z\equiv 1\pmod{2},$ fix an arbitrary
representation of $w(x,y,z)$ as a concatenation of (not necessarily distinct)
Ulam words: $w(x,y,z)=w(x,a)*w(y-a,z).$ Without loss of generality, $x$ is
odd. Then $a$ is even, and so, since $y$ is odd, $y-a$ must be, too. In
particular, $w(y-a-1,z)$ is also Ulam, so we have the representation of
$w(x,y-1,z)=w(x,a)*w(y-a-1,z)$ as a concatenation of Ulam words. Since this is
true for any $a,$ there are at least as many representations of $w(x,y-1,z)$
as there are of $w(x,y,z).$ Conversely, suppose that we have a representation
$w(x,y-1,z)=w(x,a)*w(y-a-1,z).$ Then $a$ is still even since $x$ is odd, and
so $y-a-1$ is also even. But $z$ is even, and thus $w(y-a,z)$ is also Ulam.
Hence, we obtain a decomposition of $w(x,y,z)=w(x,a)*w(y-a,z).$ In particular,
there are at least as many representations of $w(x,y,z)$ as there are of
$w(x,y-1,z),$ and thus there are equally many of each. But, since neither $y$
nor $y-1$ are Zumkeller, any representation with the Ulam words in question
being equal is irrelevant. This immediately implies that either both have $0$
representations, in which case neither is Ulam, or both have $1,$ in which
case both are Ulam, or both have $2$ or more, in which case neither is Ulam.
In any case, both are of the same type—so $(x,z)\in\operatorname{Ulam}[y]$ if
and only if $(x,z)\in\operatorname{Ulam}[y-1],$ and thus the two sets are
equal, as desired. ∎

Despite $\operatorname{Ulam}[y]$ and $\operatorname{Ulam}[y-1]$ having the
same structure, the graphs $\operatorname{pseudo-Ulam}[y]$ and
$\operatorname{pseudo-Ulam}[y-1]$ (of pseudo-Ulam words $w(\cdot,y,\cdot)$ and
$w(\cdot,y-1,\cdot),$ respectively) are still very
different—$\operatorname{pseudo-Ulam}[y-1]$ generally has points with an even
sum of coordinates that $\operatorname{pseudo-Ulam}[y]$ simply does not have
to begin with. These differences begin to play even greater of a role once we
attempt to describe $\operatorname{Ulam}[2^{d}y].$ In fact, it becomes
important to consider not just coordinates in $\operatorname{pseudo-Ulam}[y],$
but also $(x,z)\in\operatorname{pseudo-Ulam}[y-1]$ corresponding to words
$w(x,y,z)$ that have either zero or more than one representation as a
concatenation of Ulam words.

##  5 Special cases

Recall that the aforementioned numbers with at most one zero in their binary
representation are known as Zumkeller numbers; equivalently, they are the
numbers expressible as $2^{m}-2^{k}-1$ for some nonnegative integers $m$ and
$k<m$ (note that $2^{k+1}-1=2^{k+2}-2^{k+1}-1,$ so it is also expressible in
this form) [4, A089633]. As can be seen from the proof of Lemma 4.8,
biperiodicity essentially continues to hold even when $y$ is a Zumkeller
number; the only impurities arise in the first square of the period—words
$w(x,y,z)$ satisfying $x,z<2^{k+1}.$ We will now describe these impurities
precisely.

######  Theorem 5.1 (Theorem 1.9).

  * •

The set $\operatorname{Ulam}[2^{k+1}-1]$ consists of $(x,z)$ such that
$x+z\equiv-1\pmod{2^{k+1}}$ and $x+z\neq 2^{k+1}-1.$

  * •

The set $\operatorname{Ulam}[2^{k+1}-2]$ consists of $(x,z)$ such that either
$x+z\equiv-1\pmod{2^{k+1}}$ and $x+z\neq 2^{k+1}-1$ or $x+z=2^{k+1}-2$ and
$x,z\equiv 0\pmod{2}$ or $x+z=2^{k+1}$ and $x,z>0.$

  * •

Suppose $y=2^{k+1}-2^{a}-1$ is a Zumkeller number for some $0<a<k.$ Then
$\operatorname{Ulam}[y]$ is the set of $(x,z)$ such that either $x+z=y$ and
$x\pmod{2^{a+1}}<2^{a}$ or the reductions $x^{\prime}$ and $z^{\prime},$
respectively, of $x$ and $z$ modulo $2^{k+1}$ satisfy either
$x^{\prime}+z^{\prime}=2^{k+1}-1$ or $x^{\prime}+z^{\prime}=2^{k+1}+2^{a}-1.$

###### ?proofname?.

  * •

To begin, suppose that $(x,z)\in\operatorname{Ulam}[2^{k+1}-1].$ Then, by
Lemma 4.5, there exists a unique representation of $w(x,2^{k+1}-1,z)$ as a
concatenation of distinct Ulam words $w(x,a)*w(2^{k+1}-1-a,z).$ We remark that
$a,2^{k+1}-1-a\leq 2^{k+1}-1<2^{k+1},$ and thus both can only have $1$’s in
the last $k+1$ digits of their binary representations. In particular, $x$
shares no $1$’s with $a$ if and only if its reduction modulo $2^{k+1},$ which
is equal to $x^{\prime},$ does, and the same applies to $z$ and $2^{k+1}-1-a,$
with the reduction being $z^{\prime}.$ Hence, the word
$w(x^{\prime},2^{k+1}-1,z^{\prime})$ is either pseudo-Ulam or, if the
reduction results in identical words, not Ulam. However, the latter case can
only happen if $x^{\prime}+z^{\prime}=2^{k+1}-1,$ so by Lemma 2.4 we have
$x^{\prime}+z^{\prime}\geq 2^{k+1}-1.$ Now, write the binary representation of
$a=a_{k}a_{k-1}\cdots a_{1}a_{0},$ so that $2^{k+1}-1-a=b_{k}b_{k-1}\cdots
b_{1}b_{0},$ where $b_{i}=1-a_{i}$ for all $i.$ In particular, exactly one of
$a_{i},b_{i}$ is equal to $1,$ so, since $w(x^{\prime},a)$ and
$w(2^{k+1}-1-a,z^{\prime})$ are Ulam, correspondingly, either the $i$-th digit
from the right of the binary expansion of $x^{\prime}$ or respectively that of
$z^{\prime}$ is $0.$ In particular, we have
$(x^{\prime})_{i}+(z^{\prime})_{i}\leq 1$ for all $i.$ But the digits of
$x^{\prime}$ and $z^{\prime}$ only go up to the $(k+1)$-th spot from the right
(since they are residues modulo $2^{k+1}$), so in fact we see that

$x^{\prime}+z^{\prime}=\sum_{i}2^{i}((x^{\prime})_{i}+(z^{\prime})_{i})\leq\sum_{i=0}^{k}2^{i}=2^{k+1}-1.$

In other words, $x^{\prime}+z^{\prime}=2^{k+1}-1.$ Note that this corresponds
to $x+z\equiv-1\pmod{2^{k+1}}.$ In this case, we can write
$x^{\prime}=x_{k}x_{k-1}\cdots x_{1}x_{0}$ and $z^{\prime}=z_{k}z_{k-1}\cdots
z_{1}z_{0}$ where $z_{i}=1-x_{i}.$ As previous arguments have shown us, the
fact that $w(x^{\prime},a)$ and $w(2^{k+1}-1-a,z^{\prime})$ are both Ulam
implies that $x_{i}=b_{i}$ and $a_{i}=z_{i}$ for all $i,$ so that the unique
representation of $w(x^{\prime},2^{k+1}-1,z^{\prime})$ as a concatenation of
Ulam words is $w(x^{\prime},z^{\prime})*w(x^{\prime},z^{\prime}).$ This
representation gives a valid representation of
$w(x,2^{k+1}-1,z)=w(x,z^{\prime})*w(x^{\prime},z)$ as a concatenation of
distinct Ulam words if and only if either $x\neq x^{\prime}$ or $z\neq
z^{\prime}$ (or both). Thus, unless $x=x^{\prime}$ and $z=z^{\prime},$ which
corresponds to the case $x+z=2^{k+1}-1,$ the representation is valid and
unique, so $w(x,2^{k+1}-1,z)$ is Ulam. If, on the contrary, $x+z=2^{k+1}-1,$
then the representation is still unique but invalid, so $w(x,2^{k+1}-1,z)$ is
not Ulam. We therefore obtain precisely the desired description of
$\operatorname{Ulam}[2^{k+1}-1].$

  * •

As for $\operatorname{Ulam}[2^{k+1}-2],$ we have already done most of the work
in the proof of Lemma 4.5—we know that $w(x,2^{k+1}-2,z)$ with $x+z\leq
2^{k+1}$ is Ulam if and only if either $x+z=2^{k+1}-2$ and $x\equiv z\equiv
0\pmod{2}$ or $x+z=2^{k+1}$ and $x,z>0.$ We also know that for $x+z>2^{k+1},$
the update step is irrelevant, so $w(x,2^{k+1}-2,z)$ is Ulam if and only if it
is pseudo-Ulam. Suppose then that $x+z>2^{k+1}$ and there is a unique
representation of $w(x,2^{k+1}-2,z)$ as a concatenation of distinct Ulam words
$w(x,a)*w(2^{k+1}-2-a,z).$ We split into two cases: $a$ being even and odd.

If $a$ is even, then so is $2^{k+1}-2-a,$ and thus the last digits of $x$ and
$z$ in any representation are arbitrary. We can thus cut them off, looking at
the representation
$w(x^{\prime},2^{k}-1,z^{\prime})=w(x^{\prime},a/2)*w(2^{k}-1-a/2,z^{\prime}),$
where $x^{\prime}=\lfloor\frac{x}{2}\rfloor$ and
$z^{\prime}=\lfloor\frac{z}{2}\rfloor.$ But now recall from above that a
representation exists and is unique, hence giving a unique representation for
$w(x,2^{k+1}-2,z)=w(x,a)*w(2^{k+1}-2-a,z)$ with $a$ even, if and only if
$x^{\prime\prime}+z^{\prime\prime}=2^{k}-1,$ where
$x^{\prime\prime}=x^{\prime}\pmod{2^{k}}$ and
$z^{\prime\prime}=z^{\prime}\pmod{2^{k}}.$

If, on the other hand, $a$ is odd, then so is $2^{k+1}-2-a,$ and thus the last
digits of $x$ and $z$ in any representation are both $0.$ We can still cut the
last digits off, remembering the condition that $x$ and $z$ are both even, to
obtain the representation
$w(x/2,2^{k}-2,z/2)=w(x/2,(a-1)/2)*w(2^{k}-2-(a-1)/2,z/2).$ Thus, this case
adds the number of representations of $w(x/2,2^{k}-2,z/2)$ as a concatenation
of Ulam words with one $1$ to the number of such representations of
$w(x,2^{k+1}-2,z).$

Now, a simple inductive argument allows us to conclude that $w(x,2^{k+1}-2,z)$
has exactly one representation as a concatenation of (not necessarily
distinct) Ulam words with one $1$ if and only if $x+z\equiv-1\pmod{2^{k+1}}.$
The base case considers all $(x,z)$ with $x+z\leq 2^{k},$ discussed above.
Now, assume that all $(x^{\prime},z^{\prime})$ with
$x^{\prime}+z^{\prime}<x+z$ have one representation if and only if
$x^{\prime}+z^{\prime}\equiv-1\pmod{2^{k+1}}.$ If, now,
$x+z\equiv-1\pmod{2^{k+1}},$ then first observe that
$x^{\prime}+z^{\prime}\equiv-1\pmod{2^{k}}$ and so
$x^{\prime\prime}+z^{\prime\prime}=2^{k}-1.$ In particular, there exists a
unique representation of $w(x,2^{k+1}-2,z)=w(x,a)*w(2^{k+1}-2-a,z)$ for $a$
even. Moreover, there are no representations for $a$ odd, as this would imply
that $x$ and $z$ are both even. Hence, $w(x,2^{k+1}-2,z)$ has a unique
representation, as desired. Suppose now that $x+z\not\equiv-1\pmod{2^{k+1}}.$
Then observe by the inductive hypothesis that there are $0$ or at least $2$
representations of $w(x,2^{k+1}-2,z)=w(x,a)*w(x,2^{k+1}-2-a,z)$ with $a$ odd,
and the same with $a$ even. Combining these, we see that there are $0$ or at
least $2$ representations of $w(x,2^{k+1}-2,z)$ total, so it is not
(pseudo-)Ulam, completing the inductive step.

In particular, for any $x,z$ with $x+z\geq 2^{k+1},$ we see that
$(x,z)\in\operatorname{Ulam}[2^{k+1}-2]$ if and only if $w(x,2^{k+1}-2,z)$ is
pseudo-Ulam, i.e., if and only if by the above $x+z\equiv-1\pmod{2^{k+1}},$ as
desired.

  * •

Finally, suppose that $(x,z)\in\operatorname{Ulam}[2^{k+1}-2^{a}-1].$ As in
the case of $2^{k+1}-1,$ Lemma 4.5 applies, so we simply need to determine
which words $w(x,2^{k+1}-2^{a}-1,z)$ have a unique representation as a
concatenation of distinct Ulam words $w(x,b)*w(2^{k+1}-2^{a}-1-b,z).$ Note
that we may separately consider the case $x+z=2^{k+1}-2^{a}-1$ and otherwise
remove the condition that the words must be distinct. Note that since
$2^{k+1}-2^{a}-1$ is odd, in order for $w(x,2^{k+1}-2^{a}-1,z)$ to have a
unique representation we must have by an argument in Lemma 4.5 that $x+z$ is
odd.

Hence, suppose first that $x+z\neq 2^{k+1}-2^{a}-1.$ Then exactly one of $x,z$
is odd, say without loss of generality that it is $x.$ Now observe that any
representation $w(x,2^{k+1}-2^{a}-1,z)=w(x,b)*w(2^{k+1}-2^{a}-1-b,z)$ must
satisfy that $b$ is even, and thus $2^{k+1}-2^{a}-1-b$ is odd. Hence, the last
digits of the binary expansions of each term are uniquely determined, and so
we may chop them off. We then obtain the respective representation
$w((x-1)/2,2^{k}-2^{a-1}-1,z/2)=w((x-1)/2,b/2)*w(2^{k}-2^{a-1}-b/2-1,z/2).$ In
other words, $w(x,2^{k+1}-2^{a}-1,z)$ has a unique representation if and only
if $w((x-1)/2,2^{k}-2^{a-1}-1,z/2)$ does, and continuing this repetitive
operation (noting at each step that there is a unique representation only if
exactly one of $x^{\prime},z^{\prime}$ is odd), if and only if
$w(\tilde{x},2^{k+1-a}-2,\tilde{z})$ does, where
$\tilde{x}=\lfloor\frac{x}{2^{a}}\rfloor$ and
$\tilde{z}=\lfloor\frac{z}{2^{a}}\rfloor.$ But we already discussed above that
$w(\tilde{x},2^{k+1-a}-2,\tilde{z})$ has a unique representation (as a
concatenation of not necessarily distinct Ulam words with one $1$) if and only
if the reductions $\tilde{x}^{\prime},\tilde{z}^{\prime}$ of
$\tilde{x},\tilde{z}$ modulo $2^{k+1-a}$ satisfy
$\tilde{x}^{\prime}+\tilde{z}^{\prime}\in\\{2^{k+1-a}-1,2^{k+1-a}\\}.$ But
observe that $x+z=2^{a}(\tilde{x}+\tilde{z})+2^{a}-1,$ and so if
$x^{\prime},z^{\prime}$ are the respective reductions of $x,z$ modulo
$2^{k+1},$ then either $x^{\prime}+z^{\prime}=2^{k+1}-1$ or
$x^{\prime}+z^{\prime}=2^{k+1}+2^{a}-1,$ as desired.

Now, in the special case that $x+z=2^{k+1}-2^{a}-1,$ we note that issues may
arise only if $w(x,z)$ is Ulam, as then we have the extra representation

$w(x,2^{k+1}-2^{a}-1,z)=w(x,z)*w(x,z).$

Then $w(x,z)$ is Ulam if and only if there are no carries in adding $x,z$ in
binary, i.e., if and only if the entries of $x+z$ that are $0$ are also $0$ in
both $x$ and $z.$ Note that the only $0$ in $x+z$ is in the $(a+1)$-th entry
from the right, so the only requirement on $x$ and $z$ is that their
$(a+1)$-th entry from the right is $0.$ Note also that in all other slots
exactly one of $x$ and $z$ has a $1$ in its respective entry (since $x+z$
does). If this is not the case, observe that $x+z\neq 2^{k+1}-1$ or
$2^{k+1}+2^{a}-1$ and so $w(x,2^{k+1}-2^{a}-1,z)$ is not Ulam. If, on the
other hand, $x$ has a $0$ in its $(a+1)$-th entry, then observe that we can in
fact still apply the same reduction as in the case when $x+z\neq
2^{k+1}-2^{a}-1.$ Therefore, the number of representations of
$w(x,2^{k+1}-2^{a}-1,z)$ as a concatenation of (not necessarily distinct) Ulam
words with one $1$ is equal to the same number for
$w(\tilde{x},2^{k-a+1}-2,\tilde{z}),$ where
$\tilde{x}=\lfloor\frac{x}{2^{a}}\rfloor$ and
$\tilde{z}=\lfloor\frac{z}{2^{a}}\rfloor.$ Observe that the condition on the
$(a+1)$-th entry from the right in the binary representations of $x$ and $z$
being $0$ is equivalent to the last digits of $\tilde{x}$ and $\tilde{z}$
being $0,$ i.e., that both are even. As above, we also know that in every
other slot exactly one of $\tilde{x}$ and $\tilde{z}$ has its entry equal to
$1.$ In particular, $\tilde{x}+\tilde{z}=2^{k-a+1}-2.$ But we know by our
above characterization that $w(\tilde{x},2^{k-a+1}-2,\tilde{z})$ has exactly
two representations as a concatenation of Ulam words with one $1$ (with one of
the two representations having equal words) whenever
$\tilde{x}+\tilde{z}=2^{k-a+1}-2$ and $\tilde{x}$ (hence also $\tilde{z}$) is
even. Thus, $w(x,2^{k+1}-2^{a}-1,z)$ also does. One of the representations is
$w(x,z)*w(x,z),$ hence, there is exactly one representation as a concatenation
of distinct Ulam words. In other words, when $x+z=2^{k+1}-2^{a}-1,$ we see
that $w(x,2^{k+1}-2^{a}-1,z)$ is Ulam if and only if $x,z$ have a $0$ in the
$(a+1)$-th entry from the right of their binary representation, i.e.,
$x\pmod{2^{a+1}}<2^{a},$ as desired.∎

######  Corollary 5.2 (Theorem 1.7).

Suppose that $2^{k}\leq y<2^{k+1}.$

  * •

The set $\operatorname{Ulam}[y]$ is biperiodic if and only if $y$ is not a
Zumkeller number, and in this case its biperiod is $2^{k+1}\times 2^{k+1}.$

  * •

If $y$ is a Zumkeller number, then $\operatorname{Ulam}[y]$ is eventually
biperiodic with biperiod $2^{k+1}\times 2^{k+1}$; moreover, the only
impurities are in the bottom-left block: $(x,z)$ satisfying $x,z<2^{k+1}.$

###### ?proofname?.

This is an immediate consequence of Lemmata 4.8 and 5.1. ∎

Visually, in these cases $\operatorname{Ulam}[y]$ is either a set of
checkerboard-like segments on one extra diagonal line inserted into an
infinite biperiodic array of squares with two diagonal segments each, or it is
one diagonal removed from an infinite periodic array with only one segment per
square (as is in the case of $y=2^{k+1}-1$), or it is that same diagonal
removed but some of the points in the two adjacent ones added (as is in the
case of $y=2^{k+1}-2$):

(a) $\operatorname{Ulam}[23]$

(b) $\operatorname{Ulam}[30]$

(c) $\operatorname{Ulam}[31]$

?figurename? 9: $\operatorname{Ulam}[y]$ for (a) $y=23,$ (b) $y=30,$ (c)
$y=31.$

##  6 Hierarchical and fractal descriptions

(a) $\operatorname{c-Ulam}[10]$

(b) $\operatorname{c-Ulam}[19]$

(c) $\operatorname{c-Ulam}[34]$

?figurename? 10: $\operatorname{c-Ulam}[y]$ for (a) $y=10,$ (b) $y=19,$ (c)
$y=34.$

We observe that these representations seem quite regular and periodic-looking.
At the same time, the coloring for $19,$ an odd number, seems much less dense
than the coloring for $10$ and $34.$ Looking through more of these images, we
begin to notice more of a pattern: the graphs $\operatorname{c-Ulam}[2^{d}y]$
and $\operatorname{c-Ulam}[2^{d}y+1],$ where $y$ is odd, are tiled by
$2^{d}\times 2^{d}$ blocks whose coloring is determined by the colorings of
corresponding squares in $\operatorname{c-Ulam}[y-1]$ and
$\operatorname{c-Ulam}[y].$ Precisely, we in fact have the general conversion
table shown in Table 2.

In fact, all of these tables are simply linear combinations of two tiles each
for $2^{d}y$ and $2^{d}y+1$—one grey square (with black and white squares
interspersed in the case of $2^{d}y+1$) and one fractal pattern. Corresponding
squares are summed and multiplied in the ‘caveman’ way as described in
Definition 1.10. We can therefore find an inductive algorithm to determine
$\operatorname{c-Ulam}[y]$ for any $y,$ by successively reducing the number of
$1$’s in its binary expansion. But first, we need to explicitly define these
blocks and prove that they take the desired form.

######  Definition 6.1.

For every positive integer $d,$ define labelings
$\operatorname{E_{1}}[d],\operatorname{E_{2}}[d],\operatorname{O_{1}}[d],\operatorname{O_{2}}[d]:\\{0,1,2,\dots,2^{d}-1\\}^{2}\to\\{0,1,2\\}$
as follows:

  * •

If $x+z\geq 2^{d}-1,$ let $\operatorname{E_{1}}[d](x,z)=0.$ Otherwise, suppose
that $e$ is the largest $e<d$ satisfying $x,z\pmod{2^{e+1}}<2^{e}$ (which must
exist). If it also satisfies $x\pmod{2^{e}}+z\pmod{2^{e}}<2^{e}-1,$ then
$\operatorname{E_{1}}[d](x,z)=2.$ Otherwise, $\operatorname{E_{1}}[d](x,z)=1.$

  * •

Let $\operatorname{E_{2}}[d](x,z)=1$ for all $x$ and $z.$

  * •

If $x+z\geq 2^{d}-2,$ let $\operatorname{O_{1}}[d](x,z)=0.$ Otherwise, if
$x+z$ is even, then $\operatorname{O_{1}}[d](x,z)=0$ if $x$ is odd and
$\operatorname{O_{1}}[d](x,z)=2$ if $x$ is even. Finally, if $x+z<2^{d}-2$ and
is odd, then once again define $e$ as in the case of $\operatorname{E_{1}}.$
If $x\pmod{2^{e}}+z\pmod{2^{e}}<2^{e}-1,$ then
$\operatorname{O_{1}}[d](x,z)=2.$ Otherwise, $\operatorname{O_{1}}[d](x,z)=1.$

  * •

If $x+z$ is even, then $\operatorname{O_{2}}[d](x,z)=0$ if $x$ is odd and
$\operatorname{O_{2}}[d](x,z)=2$ if $x$ is even. Otherwise,
$\operatorname{O_{2}}[d](x,z)=1.$

Recall that these labelings are visualized in Table 1. While
$\operatorname{E_{2}}$ and $\operatorname{O_{2}}$ have very simple
definitions, $\operatorname{E_{1}}$ and $\operatorname{O_{1}}$ seem at first
glance to be complicated and are fractal-like. However, they actually have
very simple descriptions in terms of $\operatorname{c-Ulam}$ labelings of
powers of $2$:

######  Lemma 6.2.

Define the ‘modified’ labelings
$\operatorname{c-Ulam}[2^{d}]^{\prime},\operatorname{c-Ulam}[2^{d}+1]^{\prime}:\\{0,1,2,\dots,2^{d}-1\\}^{2}\to\\{0,1,2\\}$
as follows. The value $\operatorname{c-Ulam}[2^{d}]^{\prime}(x,z)$ counts (in
the caveman style) representations

$w(x,2^{d},z)=w(x,a)*w(b,z)$

satisfying $a,b>0.$ Meanwhile, $\operatorname{c-Ulam}[2^{d}+1]^{\prime}(x,z)$
counts representations

$w(x,2^{d}+1,z)=w(x,a)*w(b,z)$

satisfying $a,b>1.$ Then we have

  1. 1.

$\operatorname{c-Ulam}[2^{d}]^{\prime}=\operatorname{E_{1}}[d]$ and

  2. 2.

$\operatorname{c-Ulam}[2^{d}+1]^{\prime}=\operatorname{O_{1}}[d].$

###### ?proofname?.

  1. 1.

Fix some representation

$w(x,2^{d},z)=w(x,a)*w(b,z)$

with $a,b>0.$ It is not hard to see that the number of $2$’s dividing $a$ is
the same as that for $b,$ i.e., we can write $a=2^{e}a^{\prime}$ and
$b=2^{e}b^{\prime},$ where $a^{\prime}$ and $b^{\prime}$ are both odd. Then
observe that $w(x,a)$ and $w(b,z)$ are both Ulam if and only if, respectively,
both $w(x^{\prime},a^{\prime})$ and $w(b^{\prime},z^{\prime})$ are, where
$x^{\prime}=\lfloor\frac{x}{2^{e}}\rfloor,z^{\prime}=\lfloor\frac{z}{2^{e}}\rfloor$
(since the last $e$ digits of both $a$ and $b$ are $0$ and cannot interfere
with the corresponding ones of $x$ and $z$). Now, both $a^{\prime}$ and
$b^{\prime}$ are odd, so both $x^{\prime}$ and $z^{\prime}$ must be even,
which is exactly equivalent to $x,z\pmod{2^{e+1}}<2^{e}.$ Assuming this, we
see that $w(x^{\prime},a^{\prime})$ and $w(b^{\prime},z^{\prime})$ are both
Ulam if and only if $w(x^{\prime\prime},a^{\prime\prime})$ and
$w(b^{\prime\prime},z^{\prime\prime})$ are, where

$x^{\prime\prime}=\frac{x^{\prime}}{2}=\left\lfloor\frac{x}{2^{e+1}}\right\rfloor,z^{\prime\prime}=\frac{z^{\prime}}{2}=\left\lfloor\frac{z}{2^{e+1}}\right\rfloor,a^{\prime\prime}=\frac{a^{\prime}-1}{2}=\left\lfloor\frac{a}{2^{e+1}}\right\rfloor,b^{\prime\prime}=\frac{b^{\prime}-1}{2}=\left\lfloor\frac{b}{2^{e+1}}\right\rfloor.$

Observe that
$a^{\prime\prime}+b^{\prime\prime}=\frac{a^{\prime}+b^{\prime}}{2}-1=\frac{a+b}{2^{e+1}}-1=2^{d-e-1}-1.$
Hence, $w(x,2^{d},z)$ has the representation if and only if both
$x,z\pmod{2^{e+1}}<2^{e}$ and we have the representation

$w(x^{\prime\prime},2^{d-e-1}-1,z^{\prime\prime})=w(x^{\prime\prime},a^{\prime\prime})*w(b^{\prime\prime},z^{\prime\prime}).$

Say, now, that $x_{i},a_{i},b_{i},z_{i}$ represent the $(i+1)$-th digit from
the right of the binary expansions of
$x^{\prime\prime},a^{\prime\prime},b^{\prime\prime},z^{\prime\prime},$
respectively. Then note that $x_{i}+a_{i}\leq 1,b_{i}+z_{i}\leq 1$ for all
$i.$ Additionally, we have $a^{\prime\prime}+b^{\prime\prime}=2^{d-e-1}-1,$
from which it is easy to conclude that $a_{i}+b_{i}=1$ for all $i<d-e-1.$
Thus, since $x_{i}+a_{i}+b_{i}+z_{i}\leq 2,$ we have $x_{i}+z_{i}\leq 1$ for
all $i,$ and therefore $w(x^{\prime\prime},z^{\prime\prime})$ is Ulam. Observe
that the representation is unique if and only if there is a unique choice of
$a^{\prime\prime},b^{\prime\prime}$ and $e.$ But observe that we have

$w(x^{\prime\prime},2^{d-e-1}-1,z^{\prime\prime})=w(x^{\prime\prime},z^{\prime\prime})*w(2^{d-e-1}-1-z^{\prime\prime},z^{\prime\prime})=w(x^{\prime\prime},2^{d-e-1}-1-x^{\prime\prime})*w(x^{\prime\prime},z^{\prime\prime}),$

so the representation is evidently only unique if
$z^{\prime\prime}=2^{d-e-1}-1-x^{\prime\prime}.$ Thus, $w(x,2^{d},z)$ has a
representation if there exists a value $e$ such that $x,z\pmod{2^{e+1}}<2^{e}$
and $w(x^{\prime\prime},z^{\prime\prime})$ is Ulam. If $e$ is unique and in
addition satisfies $x^{\prime\prime}+z^{\prime\prime}=2^{d-e-1}-1,$ then the
representation is unique.

We see that such an $e$ does not exist if $x+z\geq 2^{d}-1$; for if it did,
then we would have $x^{\prime\prime}+z^{\prime\prime}\leq 2^{d-e-1}-1$ and in
particular $x<2^{e}(x^{\prime}+1)=2^{e+1}x^{\prime\prime}+2^{e},$ i.e., $x\leq
2^{e+1}x^{\prime\prime}+2^{e}-1,$ and similarly $z\leq
2^{e+1}z^{\prime\prime}+2^{e}-1.$ Thus,

$x+z\leq
2^{e+1}(x^{\prime\prime}+z^{\prime\prime})+2^{e+1}-2=2^{d}-2<2^{d}-1.$

If, on the other hand, we do have $x+z<2^{d}-1,$ then as in the statement
choose the largest $e<d$ satisfying $x,z\pmod{2^{e+1}}<2^{e}.$ It is not hard
to see that we must have
$x^{\prime\prime}_{e}+z^{\prime\prime}_{e}=2^{d-e-1}-1,$ giving at least one
representation of $w(x,2^{d},z).$ In order for this representation to be
unique, for any other $f$ satisfying $x,z\pmod{2^{f+1}}<2^{f},$ we observe
that $w(x^{\prime\prime}_{f},z^{\prime\prime}_{f})$ must not be Ulam. Hence,
there must exist an index $I$ with $f<I<e$ such that $x_{I}=z_{I}=1.$ It is
not hard to see that these two conditions are equivalent to
$x\pmod{2^{e}}+z\pmod{2^{e}}\geq 2^{e}-1$; the forward direction is true
because if such an $I$ exists, then

$x\pmod{2^{e}}+z\pmod{2^{e}}\geq\sum\limits_{i=I}^{e-1}(x_{i}+z_{i})2^{i}\geq
2^{I+1}+\sum\limits_{i=I+1}^{e-1}2^{i}=2^{e}$

and the backward direction is true because if $x_{f}=z_{f}=0$ and
$x_{i}+z_{i}\leq 1$ for all $i$ in between $f$ and $e,$ then

$\displaystyle x\pmod{2^{e}}+z\pmod{2^{e}}$
$\displaystyle=\sum\limits_{i=0}^{e-1}(x_{i}+z_{i})2^{i}=\sum\limits_{i=0}^{f-1}(x_{i}+z_{i})2^{i}+\sum\limits_{i=f+1}^{e-1}(x_{i}+z_{i})2^{i}$
$\displaystyle\leq\sum\limits_{i=0}^{f-1}2^{i+1}+\sum\limits_{i=f+1}^{e-1}2^{i}=2^{f+1}-2+2^{e}-2^{f+1}=2^{e}-2.$

Note that the case $x\pmod{2^{e}}+z\pmod{2^{e}}=2^{e}-1$ is separate because
$x_{i}+z_{i}=1$ for all $i<e,$ so no $f<e$ satisfying $x_{f}=z_{f}=0$ exists.
Thus, in this case, $e$ is trivially unique.

Hence, $w(x,2^{d},z)$ has a representation as a concatenation of Ulam words if
and only if $x+z<2^{d}-1,$ and this representation is unique if and only if
the largest $e$ satisfying $x,z\pmod{2^{e+1}}<2^{e}$ also satisfies
$x\pmod{2^{e}}+z\pmod{2^{e}}\geq 2^{e}-1,$ as desired.

  2. 2.

Here, we simplify our casework by using Lemma 4.10. From this, we observe that
if $x+z$ is odd, then
$\operatorname{Ulam}[2^{d}+1](x,z)=\operatorname{Ulam}[2^{d}](x,z)$ unless
$d=1,$ in which case there are exceptions when $x,z<4.$ However, the periodic
blocks are always the same and, correspondingly, since the update step does
not affect the state of coordinates with odd sum, we know that
$\operatorname{c-Ulam}[2^{d}+1](x,z)=\operatorname{c-Ulam}[2^{d}](x,z)$ as
well. It is not hard to see that $\operatorname{E_{1}}[d]$ is simply the
description of $\operatorname{c-Ulam}[2^{d}]$ on the square
$\\{2^{d},2^{d}+1,\dots,2^{d+1}-1\\}$ and $\operatorname{O_{1}}[d]$ is simply
the description of $\operatorname{c-Ulam}[2^{d}+1]$ on the same square. Thus,
if $x+z$ is odd, then the description of $\operatorname{O_{1}}[d](x,z)$ is
exactly the same as that of $\operatorname{E_{1}}[d](x,z)$ (which is to be
expected). Thus, it remains to consider the case of $x+z$ being even.

Fix a representation

$w(x,2^{d}+1,z)=w(x,a)*w(b,z)$

with $a,b>1$ and $x+z\equiv 0\pmod{2}.$ Observe that $a+b=2^{d}+1,$ therefore,
exactly one of $a,b$ is odd. In particular, we cannot have both $x$ and $z$ be
odd, as otherwise one of $w(x,a)$ or $w(b,z)$ must not be Ulam. In particular,
observe that $\operatorname{O_{1}}[d](x,z)=0$ whenever $x$ and $z$ are both
odd. Since $x+z$ is even, we therefore have that $x$ and $z$ must both be
even.

If $a$ is odd, then observe that $w(x,a)$ is Ulam if and only if $w(x,a-1)$
is, so these representations are in bijection with those of

$w(x,2^{d},z)=w(x,a^{\prime})*w(b,z)$

with $a^{\prime},b,x,z$ all even, and $a^{\prime},b>0$ (since $b$ is even, we
must have $b>1$ automatically). These, in turn, are in bijection with those of

$w(x/2,2^{d-1},z/2)=w(x/2,a^{\prime}/2)*w(b/2,z/2)$

with $a^{\prime}/2,b/2>0,$ i.e., giving the labeled set
$\operatorname{E_{1}}[d-1].$

If, instead, $b$ is odd, then our representations are once again in bijection
with those of $\operatorname{E_{1}}[d-1].$ In other words, we see that
$\operatorname{O_{1}}[d](x,z)=\operatorname{E_{1}}[d-1](x/2,z/2)\widehat{+}\operatorname{E_{1}}[d-1](x/2,z/2).$
If $\frac{x}{2}+\frac{z}{2}\geq 2^{d-1}-1,$ or, equivalently, $x+z\geq
2^{d}-2,$ then we know that $\operatorname{E_{1}}[d-1](x/2,z/2)=0,$ and thus
$\operatorname{O_{1}}[d](x,z)=0.$ If, on the other hand, $x+z<2^{d}-2,$ then
we know that $\operatorname{E_{1}}[d-1](x/2,z/2)\geq 1$ and thus
$\operatorname{O_{1}}[d](x,z)\geq 2$ and thus is equal to $2.$

In particular, going through all of our cases, we see that if $x+z\geq
2^{d}-2,$ then $\operatorname{O_{1}}[d](x,z)=0.$ If $x+z<2^{d}-2$ and is even,
then if $x$ is odd, we have $\operatorname{O_{1}}[d](x,z)=0,$ and if $x$ is
even, then $\operatorname{O_{1}}[d](x,z)=2.$ Finally, if $x+z<2^{d}-2$ and is
odd, then $\operatorname{O_{1}}[d](x,z)=\operatorname{E_{1}}[d](x,z)$ and
hence has the same description as $\operatorname{E_{1}}[d](x,z)$ (as is stated
in the definition), as desired.∎

Now, we can inductively add $1$’s to the right of the binary expansion of $y$
as follows:

######  Theorem 6.3 (Theorem 1.11).

Suppose $y$ is odd and $d$ is a nonnegative integer. For any $x,z,$ suppose
that
$x^{\prime}=\lfloor\frac{x}{2^{d}}\rfloor,z^{\prime}=\lfloor\frac{z}{2^{d}}\rfloor,$
and $x^{\prime\prime}=x\pmod{2^{d}},z^{\prime\prime}=z\pmod{2^{d}}.$ Then

$\operatorname{c-Ulam}[2^{d}y](x,z)=\operatorname{c-Ulam}[y-1](x^{\prime},z^{\prime})\widehat{\cdot}\operatorname{E_{1}}[d](x^{\prime\prime},z^{\prime\prime})\widehat{+}\operatorname{c-Ulam}[y](x^{\prime},z^{\prime})\widehat{\cdot}\operatorname{E_{2}}[d](x^{\prime\prime},z^{\prime\prime}),$

or, concisely,

$\operatorname{c-Ulam}[2^{d}y]=\operatorname{c-Ulam}[y-1]\widehat{\otimes}\operatorname{E_{1}}[d]\widehat{+}\operatorname{c-Ulam}[y]\widehat{\otimes}\operatorname{E_{2}}[d].$

Similarly, we have

$\operatorname{c-Ulam}[2^{d}y+1](x,z)=\operatorname{c-Ulam}[y-1](x^{\prime},z^{\prime})\widehat{\cdot}\operatorname{O_{1}}[d](x^{\prime\prime},z^{\prime\prime})\widehat{+}\operatorname{c-Ulam}[y](x^{\prime},z^{\prime})\widehat{\cdot}\operatorname{O_{2}}[d](x^{\prime\prime},z^{\prime\prime}),$

in other words

$\operatorname{c-Ulam}[2^{d}y+1]=\operatorname{c-Ulam}[y-1]\widehat{\otimes}\operatorname{O_{1}}[d]\widehat{+}\operatorname{c-Ulam}[y]\widehat{\otimes}\operatorname{O_{2}}[d].$

Note that the starred addition and multiplication above are in the caveman
style.

###### ?proofname?.

######  Case 1.

Suppose we have a decomposition

$w(x,2^{d}y,z)=w(x,a)*w(2^{d}y-a,z).$

We have two cases (and these two cases are exactly the ones giving the two
summands); either $a\equiv 2^{d}y-a\equiv 0\pmod{2^{d}}$ or both are nonzero.
Regardless, define
$a^{\prime}=\lfloor\frac{a}{2^{d}}\rfloor,b^{\prime}=\lfloor\frac{2^{d}y-a}{2^{d}}\rfloor$
and $a^{\prime\prime}=a\pmod{2^{d}},b^{\prime\prime}=(2^{d}y-a)\pmod{2^{d}}.$
In the former case, observe that $a^{\prime\prime}=b^{\prime\prime}=0,$
whereas in the latter we have $b^{\prime\prime}=2^{d}-a^{\prime\prime}.$

######  Case 1.1.

Suppose first that $a^{\prime\prime}=b^{\prime\prime}=0.$ Then, as before,
$w(x,a)$ and $w(2^{d}y-a,z)$ are Ulam if and only if, respectively,
$w(x^{\prime},a^{\prime})$ and $w(b^{\prime},z^{\prime})$ are. Also, we see
that $a^{\prime}+b^{\prime}=\frac{a+b}{2^{d}}=y.$ Thus, representations of
$w(x,2^{d}y,z)$ with $a\equiv 0\pmod{2^{d}}$ are in correspondence with those
of

$w(x^{\prime},y,z^{\prime})=w(x^{\prime},a^{\prime})*w(b^{\prime},z^{\prime}).$

In particular, there are
$\operatorname{c-Ulam}[y](x^{\prime},z^{\prime})=\operatorname{c-Ulam}[y](x^{\prime},z^{\prime})\widehat{\cdot}\operatorname{E_{2}}[d](x^{\prime\prime},z^{\prime\prime})$-many
of them.

######  Case 1.2.

Now, suppose that $a^{\prime\prime},b^{\prime\prime}>0,$ so that
$b^{\prime\prime}=2^{d}-a^{\prime\prime}.$ Then observe that

$2^{d}y=a+b=(2^{d}a^{\prime}+a^{\prime\prime})+(2^{d}b^{\prime}+b^{\prime\prime})=2^{d}(a^{\prime}+b^{\prime})+2^{d},$

from which we get $a^{\prime}+b^{\prime}=y-1.$ Now, $w(x,a)$ and
$w(2^{d}y-a,z)$ are Ulam if and only if, respectively,
$w(x^{\prime},a^{\prime})$ and $w(x^{\prime\prime},a^{\prime\prime}),$ and
$w(b^{\prime},z^{\prime})$ and $w(b^{\prime\prime},z^{\prime\prime})$ are. But
then observe that we have the representations

$w(x^{\prime},y-1,z^{\prime})=w(x^{\prime},a^{\prime})*w(b^{\prime},z^{\prime});\quad
w(x^{\prime\prime},2^{d},z^{\prime\prime})=w(x^{\prime\prime},a^{\prime\prime})*w(b^{\prime\prime},z^{\prime\prime}).$

Thus, representations of $w(x,2^{d}y,z)$ with $a\not\equiv 0\pmod{2^{d}}$ are
in correspondence with pairs of representations of
$w(x^{\prime},y-1,z^{\prime})$ and
$w(x^{\prime\prime},2^{d},z^{\prime\prime}),$ where the latter satisfies
$0<a^{\prime\prime},b^{\prime\prime}.$ Hence, we have, by Lemma 6.2,
$\operatorname{c-Ulam}[y-1](x^{\prime},z^{\prime})\widehat{\cdot}\operatorname{E_{1}}[d](x^{\prime\prime},z^{\prime\prime})$
total representations of $w(x,2^{d}y,z)$ in this case.

In particular, in total there are

$\operatorname{c-Ulam}[2^{d}y](x,z)=\operatorname{c-Ulam}[y](x^{\prime},z^{\prime})\widehat{\cdot}\operatorname{E_{2}}[d](x^{\prime\prime},z^{\prime\prime})\widehat{+}\operatorname{c-Ulam}[y-1](x^{\prime},z^{\prime})\widehat{\cdot}\operatorname{E_{1}}[d](x^{\prime\prime},z^{\prime\prime})$

many representations of $w(x,2^{d}y,z)$ as a concatenation of Ulam words with
one $1,$ as desired.

######  Case 2.

Suppose, now, that we have a decomposition

$w(x,2^{d}y+1,z)=w(x,a)*w(2^{d}y-a+1,z).$

We have two cases; either $a\equiv 1-(2^{d}y-a+1)\equiv 0,1\pmod{2^{d}}$ or
both are nonzero and not equal to $1.$ Once again, we can define
$a^{\prime}=\lfloor\frac{a}{2^{d}}\rfloor,b^{\prime}=\lfloor\frac{2^{d}y-a+1}{2^{d}}\rfloor$
and
$a^{\prime\prime}=a\pmod{2^{d}},b^{\prime\prime}=(2^{d}y-a+1)\pmod{2^{d}}.$ In
the former case, observe that $a^{\prime\prime}=1-b^{\prime\prime}=0$ or $1,$
whereas in the latter we have $b^{\prime\prime}=2^{d}-a^{\prime\prime}+1.$

######  Case 2.1.

Suppose first that $a^{\prime\prime}=1-b^{\prime\prime}=0$ or $1.$ Observe, if
$a$ is odd, that $x$ must be even, and vice versa if $b$ is odd, then $z$ must
be even. In either case, $w(x,a)$ and $w(2^{d}y-a+1,z)$ are Ulam if and only
if $w(x^{\prime},a^{\prime})$ and $w(b^{\prime},z^{\prime})$ are, and we see
that $a^{\prime}+b^{\prime}=\frac{a+b-1}{2^{d}}=y.$ Hence, representations of
$w(x,2^{d}y+1,z)$ with $a\equiv 0\pmod{2^{d}}$ are in correspondence with
those of

$w(x^{\prime},y,z^{\prime})=w(x^{\prime},a^{\prime})*w(b^{\prime},z^{\prime}),$

and so are those of $w(x,2^{d}y+1,z)$ with $a\equiv 1\pmod{2^{d}}.$ In
particular, we observe that if $x,z$ are both odd, then there are no such
representations. If exactly one of $x,z$ is odd, then representations are in
correspondence with those of $w(x^{\prime},y,z^{\prime}),$ so there are
$\operatorname{c-Ulam}[y](x^{\prime},z^{\prime})$-many of them. if both $x$
and $z$ are even, then there are two pairs of correspondences with
representations of $w(x^{\prime},y,z^{\prime}),$ so there are
$\operatorname{c-Ulam}[y](x^{\prime},z^{\prime})\widehat{\cdot}2$ total
representations of $w(x,2^{d}y+1,z)$ with $a\equiv 0,1\pmod{2^{d}}.$ Combining
all three of these cases, we see exactly that there are
$\operatorname{c-Ulam}[y](x^{\prime},z^{\prime})\widehat{\cdot}\operatorname{O_{2}}[d](x,z)$
representations of $w(x,2^{d}y+1,z)$ in this case.

######  Case 2.2.

Suppose now that $a^{\prime\prime},b^{\prime\prime}>1$ and so
$b^{\prime\prime}=2^{d}-a^{\prime\prime}+1.$ Then observe that

$2^{d}y+1=a+b=(2^{d}a^{\prime}+a^{\prime\prime})+(2^{d}b^{\prime}+b^{\prime\prime})=2^{d}(a^{\prime}+b^{\prime})+2^{d}+1,$

from which we get $a^{\prime}+b^{\prime}=y-1.$ We observe that $w(x,a)$ and
$w(2^{d}y-a+1,z)$ are Ulam if and only if $w(x^{\prime},a^{\prime})$ and
$w(x^{\prime\prime},a^{\prime\prime}),$ and $w(b^{\prime},z^{\prime})$ and
$w(b^{\prime\prime},z^{\prime\prime})$ are. But we have the representations

$w(x^{\prime},y-1,z^{\prime})=w(x^{\prime},a^{\prime})*w(b^{\prime},z^{\prime});\quad
w(x^{\prime\prime},2^{d}+1,z^{\prime\prime})=w(x^{\prime\prime},a^{\prime\prime})*w(b^{\prime\prime},z^{\prime\prime}).$

Thus, representations of $w(x,2^{d}y+1,z)$ with $a\not\equiv 0,1\pmod{2^{d}}$
are exactly in correspondence with pairs of representations of
$w(x^{\prime},y-1,z^{\prime})$ and
$w(x^{\prime\prime},2^{d}+1,z^{\prime\prime})$ where the latter satisfies
$0,1<a^{\prime\prime},b^{\prime\prime}.$ Hence, by Lemma 6.2, we have
$\operatorname{c-Ulam}[y-1](x^{\prime},z^{\prime})\widehat{\cdot}\operatorname{O_{1}}[d](x^{\prime\prime},z^{\prime\prime})$
total representations of $w(x,2^{d}y+1,z)$ in this case.

In particular, in total there are

$\operatorname{c-Ulam}[2^{d}y+1](x,z)=\operatorname{c-Ulam}[y](x^{\prime},z^{\prime})\widehat{\cdot}\operatorname{O_{2}}[d](x^{\prime\prime},z^{\prime\prime})\widehat{+}\operatorname{c-Ulam}[y-1](x^{\prime},z^{\prime})\widehat{\cdot}\operatorname{O_{1}}[d](x^{\prime\prime},z^{\prime\prime})$

many representations of $w(x,2^{d}y+1,z)$ as a concatenation of Ulam words
with one $1,$ as desired.

The corresponding tensor product representations of
$\operatorname{c-Ulam}[2^{d}y]$ and $\operatorname{c-Ulam}[2^{d}y+1]$ are
trivial by definition of tensor products. ∎

Alternatively, we can in fact add $1$’s to the left of the binary expansion of
$y$ as well. However, for that, we need to use the whole structure of
$\operatorname{c-Ulam}[2^{k}]$ and $\operatorname{c-Ulam}[2^{k}+1],$ rather
than simply parts of it. As it turns out, however, the entire structure is
easy to deduce from
$\operatorname{E_{1}},\operatorname{E_{2}},\operatorname{O_{1}},\operatorname{O_{2}}$;
it is simply a linear combination of them. It is also useful to define ‘parts’
of a periodic block split into fourths:

######  Definition 6.4.

Say that $2^{k}\leq y<2^{k+1}.$ Then we can partition the periodic block of
$\operatorname{c-Ulam}[y]$ into four parts:
$\operatorname{c-Ulam}_{0}[y],\operatorname{c-Ulam}_{1}[y],\operatorname{c-Ulam}_{2}[y],\operatorname{c-Ulam}_{3}[y]:B_{k}\to\\{0,1,2\\},$
defined by

$\displaystyle\operatorname{c-Ulam}_{0}[y](x,z)$
$\displaystyle=\operatorname{c-Ulam}[y](x,z)$
$\displaystyle\operatorname{c-Ulam}_{1}[y](x,z)$
$\displaystyle=\operatorname{c-Ulam}[y](2^{k}+x,z)$
$\displaystyle\operatorname{c-Ulam}_{2}[y](x,z)$
$\displaystyle=\operatorname{c-Ulam}[y](x,2^{k}+z)$
$\displaystyle\operatorname{c-Ulam}_{3}[y](x,z)$
$\displaystyle=\operatorname{c-Ulam}[y](2^{k}+x,2^{k}+z).$

?figurename? 11: The four parts of $\operatorname{c-Ulam}[y],y=27$

We then deduce the following lemma about the parts of
$\operatorname{c-Ulam}[2^{k}]$ and $\operatorname{c-Ulam}[2^{k}+1].$

######  Lemma 6.5.

We have

$\displaystyle\operatorname{c-Ulam}_{0}[2^{k}]$
$\displaystyle=2\widehat{\cdot}\operatorname{E_{2}}[k]=\operatorname{E_{1}}[k]+2\widehat{\cdot}\operatorname{E_{2}}[k],$
$\displaystyle\operatorname{c-Ulam}_{1}[2^{k}]$
$\displaystyle=\operatorname{c-Ulam}_{2}[2^{k}]=\operatorname{E_{1}}[k]\widehat{+}\operatorname{E_{2}}[k],$
$\displaystyle\operatorname{c-Ulam}_{3}[2^{k}]$
$\displaystyle=\operatorname{E_{1}}[k].$

Similarly,

$\displaystyle\operatorname{c-Ulam}_{0}[2^{k}+1]$
$\displaystyle=2\widehat{\cdot}\operatorname{O_{2}}[k]=\operatorname{O_{1}}[k]+2\widehat{\cdot}\operatorname{O_{2}}[k],$
$\displaystyle\operatorname{c-Ulam}_{1}[2^{k}+1]$
$\displaystyle=\operatorname{c-Ulam}_{2}[2^{k}+1]=\operatorname{O_{1}}[k]\widehat{+}\operatorname{O_{2}}[k],$
$\displaystyle\operatorname{c-Ulam}_{3}[2^{k}+1]$
$\displaystyle=\operatorname{O_{1}}[k].$

###### ?proofname?.

The proof essentially follows from Theorem 6.3. Observe that we have

$\operatorname{c-Ulam}[2^{k}]=\operatorname{c-Ulam}[0]\widehat{\otimes}\operatorname{E_{1}}[k]\widehat{+}\operatorname{c-Ulam}[1]\widehat{\otimes}\operatorname{E_{2}}[k].$

It is not hard to see that $\operatorname{c-Ulam}[0]=1$ and

$\operatorname{c-Ulam}[1](x,z)=(x+1)\pmod{2}+(z+1)\pmod{2}.$

Thus, $\operatorname{E_{1}}[k]$ is added once to each of
$\operatorname{c-Ulam}_{0}[2^{k}],\operatorname{c-Ulam}_{1}[2^{k}],\operatorname{c-Ulam}_{2}[2^{k}],\operatorname{c-Ulam}_{3}[2^{k}],$
whereas $\operatorname{E_{2}}[k]$ is added twice to
$\operatorname{c-Ulam}_{0}[2^{k}],$ once to $\operatorname{c-Ulam}_{1}[2^{k}]$
and $\operatorname{c-Ulam}_{2}[2^{k}],$ and not at all to
$\operatorname{c-Ulam}_{3}[2^{k}],$ as desired. The proof for
$\operatorname{c-Ulam}[2^{k}+1]$ is similar. ∎

######  Theorem 6.6 (Theorem 1.12).

Suppose $2^{k}\leq y<2^{k+1}.$ Consider labelings $L,S:B_{k}\to\\{0,1,2\\}$
defined by

$L(x,z):=\operatorname{c-Ulam}_{1}[y](x,z)=\operatorname{c-Ulam}_{2}[y](x,z)$

and

$S(x,z):=\operatorname{c-Ulam}_{3}[y](x,z).$

For any $x,z<2^{\ell+1},$ let
$x^{\prime}=\left\lfloor\frac{x}{2^{k}}\right\rfloor,z^{\prime}=\left\lfloor\frac{z}{2^{k}}\right\rfloor,$
and $x^{\prime\prime}=x\pmod{2^{k}},z^{\prime\prime}=z\pmod{2^{k}}.$ Then

$\operatorname{c-Ulam}[2^{\ell}+y](x,z)=\operatorname{c-Ulam}[2^{\ell-k}](x^{\prime},z^{\prime})\widehat{\cdot}S(x^{\prime\prime},z^{\prime\prime})\widehat{+}\operatorname{c-Ulam}[2^{\ell-k}+1](x^{\prime},z^{\prime})\widehat{\cdot}L(x^{\prime\prime},z^{\prime\prime}),$

or equivalently,

$\operatorname{c-Ulam}[2^{\ell}+y]_{\big{|}_{B_{\ell+1}}}=\operatorname{c-Ulam}[2^{\ell-k}]\widehat{\otimes}S\widehat{+}\operatorname{c-Ulam}[2^{\ell-k}+1]\widehat{\otimes}L.$

###### ?proofname?.

First, we wish to better understand the labelings $L$ and $S.$ Observe first
that $S(x,z)$ exactly counts representations of $w(2^{k}+x,y,2^{k}+z)$ as a
concatenation of Ulam words $w(2^{k}+x,a)$ and $w(b,2^{k}+z).$ Note then that
$w(x,a)$ and $w(b,z)$ are also both Ulam, as we are simply decreasing the
number of $1$’s in the binary representations. Also note that both $2^{k}+x$
and $2^{k}+z$ have a $1$ entry in the $(k+1)$’th entry from the right, hence,
correspondingly, $a$ and $b$ must not. But $a+b=y<2^{k+1},$ from which we get
that $a,b<2^{k}.$ Alternatively, if $a,b<2^{k}$ and $w(x,a)$ and $w(b,z)$ are
both Ulam, then so are $w(2^{k}+x,a)$ and $w(b,2^{k}+z).$ Thus, $S$ exactly
counts representations of $w(x,y,z)$ as concatenations of Ulam words
$w(x,a)*w(b,z)$ with $a,b<2^{k}.$ Similarly, $L$ counts representations of
$w(x,y-2^{k},z)$ as concatenations of Ulam words $w(x,a)*w(b,z).$

Suppose we have a decomposition

$w(x,2^{\ell}+y,z)=w(x,a)*w(b,z).$

Define
$a^{\prime}=\lfloor\frac{a}{2^{k}}\rfloor,b^{\prime}=\lfloor\frac{b}{2^{k}}\rfloor$
and $a^{\prime\prime}=a\pmod{2^{k}},b^{\prime\prime}=b\pmod{2^{k}}.$ There are
two cases; either $a^{\prime\prime}+b^{\prime\prime}<2^{k}$ or
$a^{\prime\prime}+b^{\prime\prime}\geq 2^{k}.$ Observe in the former case that
$a^{\prime\prime}+b^{\prime\prime}=y-2^{k},$ whereas in the latter exactly one
of $a^{\prime\prime}+b^{\prime\prime}=y.$

######  Case 1.

If $a^{\prime\prime}+b^{\prime\prime}=y-2^{k},$ then we have

$2^{\ell}+y=a+b=(2^{k}a^{\prime}+a^{\prime\prime})+(2^{k}b^{\prime}+b^{\prime\prime})=2^{k}(a^{\prime}+b^{\prime})+y-2^{k},$

so $a^{\prime}+b^{\prime}=2^{\ell-k}+1.$ Now, $w(x,a)$ and $w(b,z)$ are Ulam
if and only if $w(x^{\prime},a^{\prime})$ and
$w(x^{\prime\prime},a^{\prime\prime}),$ and $w(b^{\prime},z^{\prime})$ and
$w(b^{\prime\prime},z^{\prime\prime})$ are. But then we have the
representations

$w(x^{\prime},2^{\ell-k}+1,z^{\prime})=w(x^{\prime},a^{\prime})*w(b^{\prime},z^{\prime});\quad
w(x^{\prime\prime},y-2^{k},z^{\prime\prime})=w(x^{\prime\prime},a^{\prime\prime})*w(b^{\prime\prime},z^{\prime\prime}).$

Thus, representations of $w(x,2^{\ell}+y,z)$ with
$a^{\prime\prime}+b^{\prime\prime}<2^{k}$ are exactly in correspondence with
pairs of representations of $w(x^{\prime},2^{\ell-k}+1,z^{\prime})$ and
$w(x^{\prime\prime},y-2^{k},z^{\prime\prime}).$ Thus, there are
$\operatorname{c-Ulam}[2^{\ell-k}+1](x^{\prime},z^{\prime})\widehat{\cdot}L(x^{\prime\prime},z^{\prime\prime})$
total representations of $w(x,2^{\ell}+y,z)$ in this case.

######  Case 2.

If $a^{\prime\prime}+b^{\prime\prime}=y,$ then we have

$2^{\ell}+y=a+b=(2^{k}a^{\prime}+a^{\prime\prime})+(2^{k}b^{\prime}+b^{\prime\prime})=2^{k}(a^{\prime}+b^{\prime})+y,$

so $a^{\prime}+b^{\prime}=2^{\ell-k}.$ Similarly to the previous case,
representations of $w(x,2^{\ell}+y,z)$ with
$a^{\prime\prime}+b^{\prime\prime}\geq 2^{k}$ are exactly in correspondence
with pairs of representations of $w(x^{\prime},2^{\ell-k},z^{\prime})$ and
$w(x^{\prime\prime},y,z^{\prime\prime}),$ where the latter additionally
satisfies $a^{\prime\prime},b^{\prime\prime}<2^{k}.$ Thus, there are
$\operatorname{c-Ulam}[2^{\ell-k}](x^{\prime},z^{\prime})\widehat{\cdot}S(x^{\prime\prime},z^{\prime\prime})$
total representations of $w(x,2^{\ell}+y,z)$ in this case.

In particular, in total there are

$\operatorname{c-Ulam}[2^{\ell}+y](x,z)=\operatorname{c-Ulam}[2^{\ell-k}+1](x^{\prime},z^{\prime})\widehat{\cdot}L(x^{\prime\prime},z^{\prime\prime})\widehat{+}\operatorname{c-Ulam}[2^{\ell-k}](x^{\prime},z^{\prime})\widehat{\cdot}S(x^{\prime\prime},z^{\prime\prime})$

representations of $w(x,2^{\ell}+y,z)$ as a concatenation of Ulam words with
one $1,$ as desired. The corresponding tensor product representation is simple
to deduce. ∎

While these two results do give an inductive way to see that
$\operatorname{c-Ulam}[y]$ possesses at least some sort of tiled structure,
they do not illuminate the full extent of this structure. We now present it.
However, in order to understand external structure, we first need to prove a
result regarding the interaction between the four equal parts dividing
$\operatorname{c-Ulam}[y].$

######  Lemma 6.7.

We have

  1. 1.

$\operatorname{c-Ulam}_{1}[y]=\operatorname{c-Ulam}_{2}[y],$

  2. 2.

$\operatorname{c-Ulam}_{2}[y]\geq
2\widehat{\cdot}\operatorname{c-Ulam}_{3}[y],$ and

  3. 3.

$\operatorname{c-Ulam}_{0}[y]=2\widehat{\cdot}\operatorname{c-Ulam}_{2}[y].$

Note also that $S_{y}=\operatorname{c-Ulam}_{3}[y]$ and
$L_{y}=\operatorname{c-Ulam}_{1}[y]=\operatorname{c-Ulam}_{2}[y]$ (due to
which the labels $S$ and $L$ make sense).

###### ?proofname?.

All of these results are deduced by constructing relevant injections or
bijections.

  1. 1.

The first equality
$\operatorname{c-Ulam}[y](2^{k}+x,z)=\operatorname{c-Ulam}[y](x,2^{k}+z)$ is
evident from the bijection of representations

$w(2^{k}+x,a)*w(b,z)\Longleftrightarrow\begin{cases}w(x,a)*w(b,2^{k}+z)&a,b<2^{k},\\\
w(x,2^{k}+a)*w(b-2^{k},2^{k}+z)&b\geq 2^{k}.\end{cases}$

  2. 2.

As for the containment, suppose we have a representation
$w(2^{k}+x,y,2^{k}+z)=w(2^{k}+x,a)*w(b,2^{k}+z)$ as a concatenation of Ulam
words. We wish to construct two representations of $w(x,y,2^{k}+z)$ using
this. First, we trivially have the representation $w(x,a)*w(b,2^{k}+z).$ As
for the second representation, however, we have to work harder. Say that the
binary expansions of $a,b$ are

$a=a_{k-1}\cdots a_{1}a_{0};\quad b=b_{k-1}\cdots b_{1}b_{0}.$

Then let $I$ be the largest index such that $a_{I}=b_{I}.$ Then observe that
we must in fact have $a_{i}=b_{i}=1,$ as assuming the contrary, we get

$2^{k}\leq
y=a+b=\sum_{i=0}^{k-1}(a_{i}+b_{i})2^{i}\leq\sum_{i=0}^{I-1}2^{i+1}+\sum_{i=I+1}^{k-1}2^{i}=2^{k}-2^{I+1}+2^{I+1}-2=2^{k}-2,$

a contradiction. In particular, we have $a_{I}=b_{I}=1$ and $a_{i}+b_{i}=1$
for all $i>I,$ so that

$\sum_{i=I}^{k-1}(a_{i}+b_{i})2^{i}=2^{I+1}+\sum_{i=I+1}^{k-1}2^{i}=2^{k}.$

Define $a^{\prime}=a\pmod{2^{I}},b^{\prime}=b\pmod{2^{I}},$ and then observe
that $a+b=a^{\prime}+b^{\prime}+2^{k}=y.$ From here it is easy for us to
deduce the validity of the additional representation

$w(x,y,2^{k}+z)=w(x,2^{k}+a^{\prime})*w(b^{\prime},2^{k}+z),$

and so we have $\operatorname{c-Ulam}[y](x,2^{k}+z)\geq
2\widehat{\cdot}\operatorname{c-Ulam}[y](2^{k}+x,2^{k}+z).$

  3. 3.

As for the final equality, suppose that $w(x,y,2^{k}+z)=w(x,a)*w(b,2^{k}+z)$
is a representation. Then we wish to construct two representations of
$w(x,y,z).$ Suppose then that $w(x,y,2^{k}+z)=w(x,a)*w(b,2^{k}+z)$ is a
representation as a concatenation of Ulam words. Then observe that if
$a,b<2^{k},$ then as before we have an additional representation
$w(x,y,2^{k}+z)=w(x,2^{k}+a^{\prime})*w(b^{\prime},2^{k}+z),$ and then,
correspondingly, we have two representations

$w(x,y,z)=w(x,a)*w(b,z)=w(x,2^{k}+a^{\prime})*w(b^{\prime},z).$

If $a\geq 2^{k},$ then we have two representations

$w(x,y,z)=w(x,a)*w(b,z)=w(x,a-2^{k})*w(2^{k}+b,z).$

Regardless, we have two representations of $w(x,y,z),$ as desired. Conversely,
suppose we have a representation of $w(x,y,z)=w(x,a)*w(b,z).$ If $b<2^{k},$
then this also gives a representation $w(x,y,2^{k}+z)=w(x,a)*w(b,2^{k}+z).$
If, however, $b\geq 2^{k},$ then $a=y-b<2^{k}$ so that we have the
representation $w(x,y,2^{k}+z)=w(x,2^{k}+a)*w(b-2^{k},2^{k}+z).$ Regardless,
we have at least one representation of $w(x,y,2^{k}+z).$ Thus,
$\operatorname{c-Ulam}[y](x,z)=2\widehat{\cdot}\operatorname{c-Ulam}[y](x,2^{k}+z),$
as desired.∎

We can now prove both general hierarchical structures.

######  Theorem 6.8 (Theorem 1.15).

Suppose that either

$y=1\underbrace{00\cdots 0}_{d_{s}-1}1\cdots 1\underbrace{0\cdots
00}_{d_{1}},$

or

$y=1\underbrace{00\cdots 0}_{d_{s}-1}1\cdots 1\underbrace{0\cdots
00}_{d_{1}-1}1,$

where $d_{i}\geq 1$ for all $i.$ Then $\operatorname{c-Ulam}[y]$ exhibits both
$i_{d_{1},d_{2},\dots,d_{s}}$ and $e_{d_{1},d_{2},\dots,d_{s}}$ hierarchical
structure.

###### ?proofname?.

First, we wish to define all relevant maps and sets for our hierarchical
structures. For both structures, let $T=\\{0,1,2\\}.$ For the external
structure, also define the trivial label $t=0$ and the full label $f=2.$

We first demonstrate the internal structure. Let

$I_{d}^{e}(a,b)=a\widehat{\cdot}\operatorname{E_{1}}[d]\widehat{+}b\widehat{\cdot}\operatorname{E_{2}}[d]$

and similarly

$I_{d}^{o}(a,b)=a\widehat{\cdot}\operatorname{O_{1}}[d]\widehat{+}b\widehat{\cdot}\operatorname{O_{2}}[d].$

Define also $c_{j}^{e}=\operatorname{c-Ulam}[y_{j}]$ and
$c_{j}^{o}=\operatorname{c-Ulam}[y_{j}+1],$ where

$y_{j}=1\underbrace{00\cdots 0}_{d_{s}-1}1\cdots 1\underbrace{0\cdots
00}_{d_{j}}$

is the ‘cut-off’ of $y$ at the $j$-th step. Finally, let
$c_{s+1}^{e}=\operatorname{c-Ulam}[0]$ and
$c_{s+1}^{o}=\operatorname{c-Ulam}[1].$ Now, we see that
$\operatorname{c-Ulam}[y]=c_{1}^{e}$ if $y$ is of the first form (even) and
$c_{1}^{o}$ otherwise. Moreover, for $j=1,\dots,s,$ we have, by Theorem 6.3,
that

$\displaystyle c_{j}^{e}(x,z)$
$\displaystyle=\operatorname{c-Ulam}[y_{j}](x,z)$
$\displaystyle=\operatorname{c-Ulam}[y_{j+1}](x^{\prime},z^{\prime})\widehat{\cdot}\operatorname{E_{1}}[d_{j}](x^{\prime\prime},z^{\prime\prime})\widehat{+}\operatorname{c-Ulam}[y_{j+1}+1](x^{\prime},z^{\prime})\widehat{\cdot}\operatorname{E_{2}}[d_{j}](x^{\prime\prime},z^{\prime\prime})$
$\displaystyle=I_{d_{j}}^{e}(\operatorname{c-Ulam}[y_{j+1}](x^{\prime},z^{\prime}),\operatorname{c-Ulam}[y_{j+1}+1](x^{\prime},z^{\prime}))(x^{\prime\prime},z^{\prime\prime})$
$\displaystyle=I_{d_{j}}^{e}(c_{j+1}^{e}(x^{\prime},z^{\prime}),c_{j+1}^{o}(x^{\prime},z^{\prime}))(x^{\prime\prime},z^{\prime\prime}),$

where $x^{\prime},z^{\prime}$ are all but the last $d_{j}$ digits of $x,z,$
respectively, and $x^{\prime\prime},z^{\prime\prime}$ are the last $d_{j}$
digits. In a similar fashion, we have

$c_{j}^{o}(x,z)=I_{d_{j}}^{o}(c_{j+1}^{e}(x^{\prime},z^{\prime}),c_{j+1}^{o}(x^{\prime},z^{\prime}))(x^{\prime\prime},z^{\prime\prime}).$

As for the external structure, define $I$ as follows. Let

$\displaystyle I(0,0)=4,I(0,1)=2,I(0,2)=0,$ $\displaystyle
I(1,0)=3,I(1,1)=2,I(1,2)=0,$ $\displaystyle I(2,0)=5,I(2,1)=2,I(2,2)=0.$

Now, define

$\displaystyle
L_{d,0}^{e}=2\widehat{\cdot}\operatorname{E_{2}}[d],L_{d,1}^{e}=L_{d,2}^{e}=\operatorname{E_{1}}[d]\widehat{+}\operatorname{E_{2}}[d],L_{d,3}^{e}=\operatorname{E_{1}}[d]$
$\displaystyle
L_{d,0}^{o}=2\widehat{\cdot}\operatorname{O_{2}}[d],L_{d,1}^{o}=L_{d,2}^{o}=\operatorname{O_{1}}[d]\widehat{+}\operatorname{O_{2}}[d],L_{d,3}^{o}=\operatorname{O_{1}}[d].$

Finally, let $c_{j}^{i}=\operatorname{c-Ulam}_{i}[y_{j}]$ for
$i\in\\{0,1,2,3\\},$ where we now define either

$y_{j}=1\underbrace{00\cdots 0}_{d_{j}-1}1\cdots 1\underbrace{0\cdots
00}_{d_{1}}$

or

$y_{j}=1\underbrace{00\cdots 0}_{d_{j}-1}1\cdots 1\underbrace{0\cdots
00}_{d_{1}-1}1.$

Then we first have that $c_{s}^{i}=\operatorname{c-Ulam}_{i}[y],$ and it is
easy to see that this can be rewritten in the form described in Definition
3.2. Now, Lemma 6.7 implies that
$c_{j}^{I(a,b)}=a\widehat{\cdot}\operatorname{c-Ulam}_{3}[y_{j}]\widehat{+}b\widehat{\cdot}\operatorname{c-Ulam}_{2}[y_{j}].$
In particular, we have, by Theorem 6.6 and Lemma 6.5, that

$\displaystyle c_{j}^{i}(x,z)$
$\displaystyle=\operatorname{c-Ulam}_{0}[y_{j}](x,z)$
$\displaystyle=\operatorname{c-Ulam}_{i}[2^{d_{j}}](x^{\prime\prime},z^{\prime\prime})\widehat{\cdot}\operatorname{c-Ulam}_{3}[y_{j-1}](x^{\prime},z^{\prime})\widehat{+}\operatorname{c-Ulam}_{i}[2^{d_{j}}+1](x^{\prime\prime},z^{\prime\prime})\widehat{\cdot}\operatorname{c-Ulam}_{2}[y_{j-1}](x^{\prime},z^{\prime})$
$\displaystyle=c_{j-1}^{I(\operatorname{c-Ulam}_{i}[2^{d_{j}}](x^{\prime\prime},z^{\prime\prime}),\operatorname{c-Ulam}_{i}[2^{d_{j}}+1](x^{\prime\prime},z^{\prime\prime}))}(x^{\prime},z^{\prime})$
$\displaystyle=c_{j-1}^{I(L_{d_{j},i}^{e}(x^{\prime\prime},z^{\prime\prime}),L_{d_{j},i}^{o}(x^{\prime\prime},z^{\prime\prime}))}(x^{\prime},z^{\prime}),$

as desired. ∎

Finally, we wish to impose fractal structures on the labelings
$\operatorname{c-Ulam}[y].$ The hierarchies demonstrate that
$\operatorname{c-Ulam}[y]$ is generated from a finite series of embeddings,
but we wish to extend this infinitely. To do so, we use the map $\tilde{U}$
from the $2$-adics to the set of all labelings of
$Q=\mathbb{N}\times\\{-1-\mathbb{N}\\},$ as described in the introduction. We
now prove that it is well-defined and continuous.

######  Theorem 6.9 (Theorem 1.16).

The map $\tilde{U}:\mathbb{Z}_{2}\to S$ is well-defined everywhere and
continuous at all $y\in\mathbb{Z}_{2}\backslash\mathbb{N}.$

###### ?proofname?.

To prove well-definedness, we need to show that
$\tilde{U}(\tilde{y})(x,-z)=\tilde{U}(y^{\prime})(x,-z)$ is independent of the
choice of $y^{\prime}.$ To this end, suppose that we have two
$y^{\prime},y^{\prime\prime}\geq x,z.$ Say without loss of generality that
$y^{\prime\prime}>y^{\prime},$ and that $2^{k}\leq y^{\prime}<2^{k+1}.$ In
particular, we know that $\tilde{y}\equiv y^{\prime}\equiv
y^{\prime\prime}\pmod{2^{k+1}}.$ In particular, we can write in binary

$\displaystyle y^{\prime}$ $\displaystyle=1y_{k-1}\cdots y_{1}y_{0},$
$\displaystyle y^{\prime\prime}$ $\displaystyle=1\underbrace{0\cdots
0}_{c_{\ell}-1}1\cdots 1\underbrace{0\cdots 0}_{c_{1}-1}1y_{k-1}\cdots
y_{1}y_{0}.$

By induction, it suffices to assume that $\ell=1,$ as we can continue adding
greater powers of $2$ while maintaining the condition $y\geq x,z.$ Thus, we
suppose that $y^{\prime\prime}=2^{k+c}+y.$ We now apply Theorem 6.6.
Precisely, we have

$\displaystyle\tilde{U}(y^{\prime\prime})(x,-z)=$
$\displaystyle\operatorname{c-Ulam}[y^{\prime\prime}](x,2^{k+c+1}-z)$
$\displaystyle=$
$\displaystyle\operatorname{c-Ulam}[2^{c}](x^{\prime},(2^{k+c+1}-z)^{\prime})\widehat{\cdot}S(x^{\prime\prime},(2^{k+c+1}-z)^{\prime\prime})\widehat{+}$
$\displaystyle\widehat{+}$
$\displaystyle\operatorname{c-Ulam}[2^{c}+1](x^{\prime},(2^{k+c+1}-z)^{\prime})\widehat{\cdot}L(x^{\prime\prime},(2^{k+c+1}-z)^{\prime\prime}),$

where

$x^{\prime}=\left\lfloor\frac{x}{2^{k}}\right\rfloor,(2^{k+c+1}-z)^{\prime}=\left\lfloor\frac{2^{k+c+1}-z}{2^{k}}\right\rfloor$

and

$x^{\prime\prime}=x\pmod{2^{k}},(2^{k+c+1}-z)^{\prime\prime}=(2^{k+c+1}-z)\pmod{2^{k}}=(-z)\pmod{2^{k}}.$

Noting $x,z\leq y<2^{k+1}$ and $z>0$ (noting that $(x,-z)\in Q$), we must now
split into cases.

######  Case 1.

If $x<2^{k}$ and $z\leq 2^{k},$ then
$x^{\prime}=0,(2^{k+c+1}-z)^{\prime}=2^{c+1}-1,$ and
$x^{\prime\prime}=x,(2^{k+c+1}-z)^{\prime\prime}=2^{k}-z.$ But it is easy to
see that
$\operatorname{c-Ulam}[2^{c}](0,2^{c+1}-1)=\operatorname{c-Ulam}[2^{c}+1](0,2^{c+1}-1)=1$
and thus we simply have, by Lemma 6.7,

$\displaystyle\tilde{U}(y^{\prime\prime})(x,-z)$
$\displaystyle=S(x,2^{k}-z)\widehat{+}L(x,2^{k}-z)=L(x,2^{k}-z)$
$\displaystyle=\operatorname{c-Ulam}[y^{\prime}](x,2^{k+1}-z)=\tilde{U}(y^{\prime})(x,-z),$

as desired.

######  Case 2.

If $x<2^{k}$ and $z>2^{k},$ then
$x^{\prime}=0,(2^{k+c+1}-z)^{\prime}=2^{c+1}-2,$ and
$x^{\prime\prime}=x,(2^{k+c+1}-z)^{\prime\prime}=2^{k+1}-z.$ It is again easy
to see that
$\operatorname{c-Ulam}[2^{c}](0,2^{c+1}-2)=\operatorname{c-Ulam}[2^{c}+1](0,2^{c+1}-2)=2$
and thus we have, once again by Lemma 6.7,

$\displaystyle\tilde{U}(y^{\prime\prime})(x,-z)$
$\displaystyle=2\widehat{\cdot}S(x,2^{k+1}-z)\widehat{+}2\widehat{\cdot}L(x,2^{k+1}-z)=2\widehat{\cdot}L(x,2^{k+1}-z)$
$\displaystyle=2\widehat{\cdot}\operatorname{c-Ulam}_{2}[y^{\prime}](x,2^{k+1}-z)=\operatorname{c-Ulam}(_{0})[y^{\prime}](x,2^{k+1}-z)=\tilde{U}(y^{\prime})(x,-z),$

as desired.

######  Case 3.

If $x\geq 2^{k}$ and $z\leq 2^{k},$ then
$x^{\prime}=1,(2^{k+c+1}-z)^{\prime}=2^{c+1}-1,$ and
$x^{\prime\prime}=x-2^{k},(2^{k+c+1}-z)^{\prime\prime}=2^{k}-z.$ But
$\operatorname{c-Ulam}[2^{c}](1,2^{c+1}-1)=1$ and
$\operatorname{c-Ulam}[2^{c}+1](1,2^{c+1}-1)=0$ and thus we have

$\displaystyle\tilde{U}(y^{\prime\prime})(x,-z)$
$\displaystyle=S(x-2^{k},2^{k}-z)=\operatorname{c-Ulam}[y^{\prime}](x,2^{k+1}-z)=\tilde{U}(y^{\prime})(x,-z),$

as desired.

######  Case 4.

If $x\geq 2^{k}$ and $z>2^{k},$ then
$x^{\prime}=1,(2^{k+c+1}-z)^{\prime}=2^{c+1}-2,$ and
$x^{\prime\prime}=x-2^{k},(2^{k+c+1}-z)^{\prime\prime}=2^{k+1}-z.$ But now
$\operatorname{c-Ulam}[2^{c}](1,2^{c+1}-2)=\operatorname{c-Ulam}[2^{c}+1](1,2^{c+1}-2)=1$
and thus we have

$\displaystyle\tilde{U}(y^{\prime\prime})(x,-z)$
$\displaystyle=S(x-2^{k},2^{k+1}-z)\widehat{+}L(x-2^{k},2^{k+1}-z)=L(x-2^{k},2^{k+1}-z)$
$\displaystyle=\operatorname{c-Ulam}[y^{\prime}](x,2^{k+1}-z)=\tilde{U}(y^{\prime})(x,-z),$

as desired.

Thus, in all cases we have
$\tilde{U}(y^{\prime\prime})(x,-z)=\tilde{U}(y^{\prime})(x,-z),$ from which we
conclude that $\tilde{U}(\tilde{y})$ is well-defined for any $2$-adic integer
$\tilde{y}.$

Now, continuity at any $y\in\mathbb{Z}_{2}\backslash\mathbb{N}$ is evident;
for any $\varepsilon>0,$ choose $y^{\prime}$ such that $2^{k}\leq
y^{\prime}<2^{k+1}$ and $2^{k}>\frac{1}{\varepsilon},$ and $\tilde{y}\equiv
y^{\prime}\pmod{2^{k+1}}.$ Then for any $Y\in\mathbb{Z}_{2}$ such that
$\left\|Y-y\right\|_{2}\leq\frac{1}{2^{k+1}},$ we have $Y\equiv y\equiv
y^{\prime}\pmod{2^{k+1}}$ and thus for all $x,\left|z\right|\leq 2^{k},$
definitionally,
$\tilde{U}(Y)(x,z)=\tilde{U}(y^{\prime})(x,z)=\tilde{U}(y)(x,z).$ In
particular, the distance
$\rho(\tilde{U}(y),\tilde{U}(Y))\leq\frac{1}{2^{k}}<\varepsilon,$ as desired.
∎

##  7 Surprising results

We conclude by showing the power of the general reductive theorems of Section
6 in proving several unexpected deterministic properties of Ulam words with
two $1$’s.

######  Theorem 7.1.

Suppose $2^{k}\leq y<2^{k+1},$ and let $\tilde{x}$ and $\tilde{z}$ be the
reductions of $x$ and $z,$ respectively, modulo $2^{k+1}.$

  1. 1.

If $y$ is not a Zumkeller number, then $(x,z)\in\operatorname{Ulam}[y]$ only
if $x+z\geq 2^{k+1}-1.$

  2. 2.

If $y$ is not a Zumkeller number, then $(x,z)\in\operatorname{Ulam}[y]$ only
if $2^{k+1}-1\leq\tilde{x}+\tilde{z}\leq 2^{k+2}-y-2.$ If $y$ is a Zumkeller
number, then this is true unless $x+z\in\\{y,y+1,y+2\\}.$

  3. 3.

If $y\not\in\\{2^{k+1}-1,2^{k+1}-2\\},$ then $(x,z)\in\operatorname{Ulam}[y]$
for all $x+z\equiv-1\pmod{2^{k+1}}.$ If $y=2^{k+1}-1$ or $y=2^{k+1}-2,$ then
the same result holds except when $x+z=2^{k+1}-1.$

  4. 4.

For all $y,$ we have $(x,z)\in\operatorname{Ulam}[y]$ whenever either
$\tilde{x}+\tilde{z}=2^{k+2}-y-2$ or $\tilde{x}+\tilde{z}=2^{k+2}-y-3,$
whichever is odd.

All of these results follow from relatively simple arguments by induction, as
we will now show.

###### ?proofname?.

In the context of $\operatorname{c-Ulam}[y]$ for a given $y,$ let
$\tilde{x},\tilde{z}$ always denote the reductions of $x$ and $z$ modulo
$2^{k+1},$ the first power of $2$ greater than $y.$

  1. 1.

First, since $y$ is not a Zumkeller number, we know that
$(x,z)\in\operatorname{Ulam}[y]$ if and only if
$\operatorname{c-Ulam}[y](x,z)=1$ and $x+z\equiv 1\pmod{2}.$ We now prove that
this modified fact, in fact, simply the condition
$\operatorname{c-Ulam}[y](x,z)=1,$ implies $x+z\geq 2^{k+1}-1$ by induction
for all $y.$ This evidently implies the conclusion.

The base cases $y=2^{k}$ follow from a simple calculation; if $x+z<2^{k+1}-1,$
then if $x,z<2^{k},$ we have by Lemma 6.5 that

$\operatorname{c-Ulam}[2^{k}](x,z)=\operatorname{c-Ulam}_{0}[2^{k}](x,z)=2\widehat{\cdot}\operatorname{E_{2}}[k](x,z)\neq
1$

and otherwise exactly one of $x,z$ is still less than $2^{k}$; say it is $x,$
so that

$\operatorname{c-Ulam}[2^{k}](x,z)=\operatorname{c-Ulam}_{2}[2^{k}](x,z-2^{k})=\operatorname{E_{1}}[k](x,z-2^{k})\widehat{+}\operatorname{E_{2}}[k](x,z-2^{k}).$

But $x+z-2^{k}<2^{k}-1,$ and thus $\operatorname{E_{1}}[k](x,z-2^{k})\geq 1$
and $\operatorname{E_{2}}[k](x,z-2^{k})=1,$ so
$\operatorname{c-Ulam}[2^{k}](x,z)=2.$ Thus, regardless,
$\operatorname{c-Ulam}[2^{k}](x,z)\neq 1$ if $x+z<2^{k+1}-1.$

Now, suppose $\operatorname{c-Ulam}[Y](x,z)=1,$ implies $x+z\geq 2^{K+1}-1$
for all $Y<y,$ where $K=\left\lfloor\log_{2}(Y)\right\rfloor,$ and assume that
$y$ is not a power of $2.$ Note that if $y$ is odd, then
$\operatorname{c-Ulam}[y](x,z)=1$ only if $\operatorname{c-Ulam}[y-1](x,z)=1$
and then we proceed by induction. Thus, we can assume without loss of
generality that $y$ is even. Consider any $x,z$ such that $x+z<2^{k+1}-1.$ We
can write $y=2^{d}y^{\prime}$ for some odd $y^{\prime}$ and $d>0.$ Then, by
Theorem 6.3, we have

$\operatorname{c-Ulam}[y](x,z)=\operatorname{c-Ulam}[y^{\prime}-1](x^{\prime},z^{\prime})\widehat{\cdot}\operatorname{E_{1}}[d](x^{\prime\prime},z^{\prime\prime})\widehat{+}\operatorname{c-Ulam}[y^{\prime}](x^{\prime},z^{\prime})\widehat{\cdot}\operatorname{E_{2}}[d](x^{\prime\prime},z^{\prime\prime}),$

where
$x^{\prime}=\lfloor\frac{x}{2^{d}}\rfloor,z^{\prime}=\lfloor\frac{z}{2^{d}}\rfloor,$
and $x^{\prime\prime}=x\pmod{2^{d}},z^{\prime\prime}=z\pmod{2^{d}}.$ Since
$x+z<2^{k+1}-1,$ we have

$x^{\prime}+z^{\prime}\leq\frac{x}{2^{d}}+\frac{z}{2^{d}}<\frac{2^{k+1}-1}{2^{d}}<2^{k-d+1}.$

Since $2^{k-d}\leq y^{\prime}<2^{k-d+1},$ we know according to our inductive