# Surjectivity of a Binary Analog of the Enots Wolley Sequence

###### Abstract

It is an open conjecture that the Enots Wolley sequence is surjective onto the
set of positive integers with a binary weight of at least 2. In this paper,
this property is proved for an analog of the Enots Wolley sequence which
operates on the binary representation of a number rather than the prime
factorization.

The Binary Enots Wolley Sequence

Nathan Nichols
Milwaukee, Wisconsin
United States
<EMAIL_ADDRESS>

##  1 Introduction

The Yellowstone permutation is sequence A098550 in the OEIS. It was defined
and studied by Applegate et al. who proved the key property that every
positive integer appears as a term [1, 6]. The Enots Wolley sequence A336957
is closely related to the Yellowstone permutation. It is still an open
question whether or not every eligible number appears in the Enots Wolley
sequence [3, 4].

This paper is concerned with a variation of the Enots Wolley sequence which
operates on the binary representation of a number rather than the prime
factorization. This variation (sequence A338833) is called the Binary or Set
Theoretic Enots Wolley sequence [2]. For this variation, the property that
every number with a binary weight of at least two appears in the sequence is
proved. The exact definition of the Binary Enots Wolley sequence is as
follows:

######  Definition 1.

For $n\geq 1$, the Binary Enots Wolley sequence $a(n)$ is defined as the
lexicographically earliest infinite sequence of distinct positive integers
with the property that $a(n)$ is the any number $m$ not yet in the sequence
such that the binary expansions of $m$ and $a(n-1)$ have a $1$ in the same
position, but the positions of the $1$s in the binary expansions of $m$ and
$a(n-2)$ are disjoint.

The remaining definitions and theorems in this section have direct analogs for
the Enots Wolley sequence [3].

######  Definition 2.

Let $k$ be a positive integer. Let ${\operatorname{supp}}(k)$, the support of
$k$, denote the set of positions of $1$s in the binary expansion of $k$. Thus
${\operatorname{supp}}(15)=\\{0,1,2,3\\}$ and
${\operatorname{supp}}(1)=\\{0\\}$.

######  Definition 3.

For a positive integer $k$, the characteristic function
${\operatorname{char}}_{k}(i):\mathbb{N}\to\\{0,1\\}$ is

$\begin{split}{\operatorname{char}}_{k}(i):=\begin{cases}1&{\operatorname{supp}}(k)\cap{\operatorname{supp}}(i)\neq\emptyset,\\\
0&\textrm{otherwise}.\\\ \end{cases}\end{split}$ (1)

######  Definition 4.

The truth table of ${\operatorname{char}}_{k}(i)$ is the sequence
$({\operatorname{char}}_{k}(i))_{i>0}$.

######  Definition 5.

For a positive integer $k$, let ${s_{2}}(k)$ denote the number of $1$s in the
binary expansion of $k$ (the binary weight of $k$.)

The following theorem serves as a more useful form of Definition 1:

######  Theorem 1.

For $n>2$, $a(n)$ is the smallest number $m$ not yet in the sequence such
that:

  1. i)

${\operatorname{supp}}(m)\cap{\operatorname{supp}}(a(n-1))$ is nonempty,

  2. ii)

${\operatorname{supp}}(m)\cap{\operatorname{supp}}(a(n-2))$ is empty, and

  3. iii)

the set ${\operatorname{supp}}(m)\setminus{\operatorname{supp}}(a(n-1))$ is
nonempty.

###### Proof.

Conditions (i) and (ii) are already part of Definition 1. Condition (iii) is a
consequence of (i) and (ii) because if (iii) fails for some term $a(n)$, there
is no way for property (ii) to hold for the term $a(n+1)$. This proves that if
the Binary Enots Wolley exists, then it must satisfy properties (i)-(iii).

The Binary Enots Wolley sequence is defined in Definition 1 as the
lexicographically earliest sequence in some set $S$ of sequences. To prove the
Binary Enots Wolley sequence exists, it suffices to show that the set $S$ is
not empty. Here is one example of a sequence of binary numbers $e_{i}\in S$:

$\begin{matrix}[l]&e_{1}=1111\\\ &e_{2}=001111\\\ &e_{3}=00001111\\\
&e_{4}=0000001111\\\ &\vdots\par\end{matrix}$

It remains to be shown that $a(n)$ is the smallest number $m$ satisfying
properties (i)-(iii). If it were possible to construct a sequence in $S$ term-
by-term by always choosing $a(n)$ to be the least number $m$ satisfying
conditions (i)-(iii), then this “greedy” strategy would produce the
lexicographically earliest sequence in $S$. Hence, it suffices to show that
this greedy strategy does not lead to any dead ends. For this, observe that
there will always be atleast one possible choice for $a(n)$ if $a(n-1)$ and
$a(n-2)$ satisfy conditions (i)-(iii). ∎

An immediate implication of Theorem 1 is that only numbers with a binary
weight of at least $2$ can appear in the sequence. See Figure 1 for a table of
the first terms of the Enots Wolley and Binary Enots Wolley sequences.

######  Definition 6.

Let $m$ be a positive integer such that ${s_{2}}(m)\geq 2$. Say that $m$ is a
candidate for the $n$th term if properties (i), (ii), and (iii) of Theorem 1
hold.

######  Theorem 2.

If $n$ is the least positive integer such that
$v\in{\operatorname{supp}}(a(n))$, the term $a(n)$ has a binary weight of $2$.

###### Proof.

Suppose $n$ is the least positive integer such that
$v\in{\operatorname{supp}}(a(n))$ and let $S$ be the set of all candidates for
the $n$th term. By Theorem 1, the term $a(n)$ is the least element of $S$
which does not appear in the first $n-1$ terms of the sequence.

Define $T$ to be the set of elements of ${\operatorname{supp}}(a(n-1))$ that
are not also contained in ${\operatorname{supp}}(a(n-2))$. By Theorem 1, for
every $m\in S$ there is at least one element of $T$ contained in
${\operatorname{supp}}(m)$. The least element of $S$ involving $2^{v}$ is
$2^{v}+2^{w}$ where $w$ is the least element of $T$. Because $2^{v}$ does not
appear in the first $n-1$ terms of the sequence, neither does the number
$2^{v}+2^{w}$. Thus, $a(n)=2^{v}+2^{w}$. ∎

######  Definition 7.

If $a(n)=2^{v}+2^{w}$ is the first term of the sequence such that
$v\in{\operatorname{supp}}(a(n))$, say that $2^{v}$ is introduced by $2^{w}$.

23571113171923121311411511611721811911101111121211131114111521162117111811192120212111221123112411251126112731281129113011131111321133113431Enots
Wolley

1248163264112113114115116117118119111101111111211131114111151116111171111811191120111211112211231124111251112611271112811129111301113111132113311341111Binary
Enots Wolley

Figure 1: The prime factorizations of the first 34 terms of the Enots Wolley
sequence and the binary expansions of the first 34 terms of the binary Enots
Wolley sequence. A blank square indicates a multiplicity of zero or a
coefficient of zero (respectively.)

##  2 Surjectivity of the Binary Enots Wolley sequence

######  Theorem 3.

Let $k$ be a positive integer such that ${s_{2}}(k)\geq 2$. Let $S(k)$ be a
set of positive integers $i$ such that $k$ is a candidate for $a(i)$. If there
are $k$ or more elements of $S$, then $k$ must appear in the sequence.

###### Proof.

If $k$ is a candidate for the $i$th term but $a(i)\neq k$, it must be that
$a(i)=k^{\prime}$ where $k^{\prime}$ is another candidate for the $i$th term
that is less than $k$. Because there are only $k-1$ positive integers
$k^{\prime}$ less than $k$ and each can only appear in the sequence once, this
situation can only occur for at most $k-1$ choices of $i\in S(k)$ before $k$
must be the least candidate that has not already occurred in the sequence. ∎

######  Lemma 1.

For all non-negative integers $m$, the truth table of
${\operatorname{char}}_{2^{m}}$ has infinitely many occurrences of $01$.

###### Proof.

Since the truth table of a power of two cannot have any occurrences of $111$,
it must only be shown that there is no $i^{\prime}$ such that $i>i^{\prime}$
implies ${\operatorname{char}}_{2^{m}}(i)=0$. Assume that this is the case.
Let $2^{a}$ be the highest bit that has occurred in the sequence before the
$(i^{\prime})$th term. Let $2^{b}$ be a sufficiently large power of two so
that $b-a>N$ where $N$ is some large number (for instance, $N=100$.) Let $n$
be the least positive integer such that $b\in{\operatorname{supp}}(a(n))$. It
is now necessary to make the following three definitions:

  1. -

$U:=$ The bit that introduces $2^{b}$ in the $n$th term.

  2. -

$V:=$ A power of $2$ distinct from $U$ such that $2^{a}<V<2^{b}$.

  3. -

$W:=2^{m}$.

It will be shown that unless all of the $N-1$ choices of $V$ are present in
$a(n-2)$, the number $U+V+W$ is a smaller unused candidate for $a(n)$ than
$U+2^{b}$. For one, the number $U+V+W$ is less than $2^{b}+U$ because
$V+W<2^{b}$. The other parts of this claim follow from the following
properties of the three bits $U$, $V$ and $W$:

  1. \- $U$:

Ensures properties (i) and (iii) for $U+V+W$ to be a candidate for the $n$th
term hold.

  2. \- $V$:

Because $W$ has never occurred together with $V$, this ensures $U+V+W$ has not
appeared in the first $n-1$ terms of the sequence.

  3. \- $W$:

Ensures that if $a(n)=U+V+W$, then ${\operatorname{char}}_{2^{m}}(n)=1$
(contradicting the assumption that ${\operatorname{char}}_{2^{m}}(n)=0$.)

This proves that as long as $V$ isn’t barred from appearing in the term $a(n)$
by property (ii), the number $U+V+W$ is a smaller candidate for $a(n)$ that
does not appear in the first $n-1$ terms of the sequence. In the case that all
possible choices of $V$ are present in $a(n-2)$, it is possible to construct
an alternative value of $a(n-2)$ that produces a lexicographically earlier
sequence as follows:

Because $b-a<N$, there are $N-1$ possible choices for $V$. Hence, if all
possible choices of $V$ are present in $a(n-2)$, then $a(n-2)$ must have a
binary weight of at least $N-1$. Since none of the bits that are possible
choices for $V$ have yet appeared in the sequence in a term together with
$2^{m}$, it is possible to erase one of the bits that are possible choices for
$V$ and replace it with $2^{m}$ in $a(n-2)$ to obtain a smaller unused
candidate for the $(n-2)$nd term. ∎

######  Lemma 2.

Let $k=2^{p}+2^{q}$ be a positive integer with ${s_{2}}(k)=2$. If there are an
infinite number of occurrences of $01$ in the truth table of
${\operatorname{char}}_{k}(i)$, then $k$ must appear in the sequence.

###### Proof.

Let $S$ be an infinite set of positive integers such that
${\operatorname{char}}_{k}(j)=0$ and ${\operatorname{char}}_{k}(j+1)=1$ for
all $j\in S$. For each $j\in S$, properties (i) and (ii) of Theorem 1 always
hold for $k$ to be a candidate for the $(j+2)$nd term. If property (iii) for
$k$ to be a candidate for the $(j+2)$nd term also happens to hold for an
infinite number of positions $j\in S$, then $k$ is a candidate an infinite
number of times and therefore must appear in the sequence by Theorem 3. In
this case, there is nothing to prove.

If property (iii) for $k$ to be a candidate for the $(j+2)$nd term holds only
for a finite number of $j\in S$, it must be that ${\operatorname{supp}}(k)$ is
a subset of ${\operatorname{supp}}(a(j+1))$ an infinite number of times. Thus,
all but finitely many of the $j\in S$ correspond to instances of the following
pattern, where each of the $m_{0},m_{1},m_{2},m_{3}$ have supports disjoint
with ${\operatorname{supp}}(k)$ and $d$ is some positive integer such that
${\operatorname{supp}}(d)$ is a (possibly empty) subset of
${\operatorname{supp}}(k)$:

$\begin{split}\begin{matrix}&\ &(A)&\ &(B)&\ &(C)&\ &(D)&\ \\\
\cdots&\to&m_{0}&\to&m_{1}+k&\to&m_{2}+d&\to&m_{3}&\to\ \cdots\\\
\end{matrix}\end{split}$ (2)

This means that almost every time there is a $1$ after a run of $0$s in the
truth table of ${\operatorname{char}}_{k}(i)$, all bits of $k$ must be present
in the term corresponding to the leading $1$ (i.e., in position $(B)$.) Note
that the term in position $(D)$ must have support disjoint with
${\operatorname{supp}}(k)$. This implies that there can be almost no
occurrences of $111$ in truth table of ${\operatorname{char}}_{k}(i)$.

Let $P_{i}$ and $Q_{i}$ denote the set of distinct positive integers appearing
in the first $i$ terms of the sequence that contain $p$ (but not $q$) and $q$
(but not $p$) in their supports (respectively.) Define $P(i):=|P_{i}|$ and
$Q(i):=|Q_{i}|$ to be the sizes of these sets. Likewise, let $PQ(i):=|PQ_{i}|$
denote the number of distinct positive integers appearing in the first $i$
terms of the sequence which contain both $p$ and $q$ in their supports.

The pattern (2) implies that after a finite number of terms, at least half of
the new $1$s in the truth table of ${\operatorname{char}}_{k}$ contribute to
$PQ_{i}$, and the rest of the new $1$s contribute to either $P_{i}$ or
$Q_{i}$. Because every bit must appear infinitely many times by Lemma 1, it
must be that there exists $i^{\prime}$ such that $i>i^{\prime}$ implies
$PQ(i)>P(i)$ or $PQ(i)>Q(i)$. In other words, the function $PQ(i)$ grows
faster than at least one of $P(i)$ or $Q(i)$.

On the other hand, every time pattern (2) occurs, both $m_{1}+2^{p}$ and
$m_{1}+2^{q}$ are smaller candidates than $m_{1}+k$ for the term in position
$(B)$. If the smallest unused candidate for position $(B)$ happens to be
$m_{1}+k$, then it must be the case that both $m_{1}+2^{p}$ and $m_{1}+2^{q}$
have already occurred in the sequence. This implies there exists $i^{\prime}$
such that $i>i^{\prime}$ implies $Q(i)\geq PQ(i)$ and $P(i)\geq PQ(i)$, which
is a contradiction of the other lower bound for $PQ(i)$ from the previous
paragraph. Hence, our original assumption that property (iii) for $k$ to be a
candidate for the $(j+2)$nd term holds only a finite number of times after an
occurrence of $01$ in the truth table of ${\operatorname{char}}_{k}$ is false.
By Theorem 3, this implies that $k$ must occur in the sequence. ∎

######  Theorem 4.

Let $k$ be a positive integer such that ${s_{2}}(k)\geq 2$. If there are an
infinite number of occurrences of $01$ in the truth table of
${\operatorname{char}}_{k}(i)$, then $k$ must appear in the sequence.

###### Proof.

(Outline.) In the case that ${s_{2}}(k)>2$, the proof of Lemma 2 breaks down
in the fourth paragraph (starting with “Let $P_{i}$ and $Q_{i}$…”) The proof
from the fourth paragraph onward can be adapted to the case that
${s_{2}}(k)>2$ by observing that every $m_{1}+s$ where
${\operatorname{supp}}(s)$ is a non-empty proper subset of
${\operatorname{supp}}(k)$ is a smaller candidate for position $(B)$. Thus,
occurrences of terms whose support contains ${\operatorname{supp}}(k)$ must be
even more rare than in the case of ${s_{2}}(k)=2$. Yet, the proof of Lemma 2
still leads to the situation where at least half of all but finitely many $1$s
in the truth table of ${\operatorname{char}}_{k}$ correspond to terms that
contain all of ${\operatorname{supp}}(k)$ in their support. ∎

######  Lemma 3.

Let $k=2^{p}+2^{q}$ be a positive integer with ${s_{2}}(k)=2$. Then, there is
no positive integer $i^{\prime}$ such that $i>i^{\prime}$ implies
${\operatorname{char}}_{k}(i)=1$.

###### Proof.

Suppose that there exists $i^{\prime}$ such that $i>i^{\prime}$ implies
${\operatorname{char}}_{k}(i)=1$. Using Iverson bracket notation, define a
function $f:\mathbb{N}_{>i^{\prime}}\to\\{0,1\\}\times\\{0,1\\}$ as

$\begin{split}f(m):=(\biggr{[}p\in{\operatorname{supp}}\
a(m)\biggr{]},\biggr{[}q\in{\operatorname{supp}}\ a(m)\biggr{]})\end{split}$
(3)

In the sequence $(f(i))_{i\geq i^{\prime}}$, there cannot be any occurrence of
$(0,0)$ because $f(j)=(0,0)$ implies ${\operatorname{char}}_{k}(j)=0$. There
also cannot be any occurrences of $(1,1)$ because $f(j)=(1,1)$ implies
$f(j+2)=(0,0)$. The patterns $(1,0),(0,1),(1,0)$ and $(0,1),(1,0),(0,1)$ also
cannot occur in the sequence $(f(i))_{i\geq i^{\prime}}$ because they violate
property (ii) of Theorem 1. So, the only possibility is that $(f(i))_{j\geq
i^{\prime}}$ follows the pattern $(1,0),(1,0),(0,1),(0,1)$ modulo 4 (after
some suitable offset.)

Recall that whenever a new bit $2^{a}$ appears in the sequence for the first
time, it must occur in a number of the form $2^{a}+2^{b}$. If a new bit were
introduced in position $0$ or position $2$ of the pattern
$(1,0),(1,0),(0,1),(0,1)$, it would be impossible for the support of the term
where the new bit is introduced to intersect with the support of the preceding
term. Thus, new bits can only be introduced in positions $1$ or $3$. Here is a
diagram illustrating what happens when a new bit $B$ is introduced in position
$1$ (a blank indicates that bit is not specified, a 1 indicates that column’s
bit is present in the support, a 0 indicates it is absent:)

$\begin{matrix}[l]&\ &pq&\cdots&B\\\ &0:\ &10&\ &\ \\\ &1:\ &10000&\cdots
0000&1\\\ &2:\ &01&\ &1\\\ &3:\ &01&\ &\\\ \end{matrix}$

Let $m$ be any positive integer not appearing in the first $i^{\prime}$ terms
of the sequence such that ${s_{2}}(m)\geq 2$ and
${\operatorname{supp}}(m)\cap{\operatorname{supp}}(k)=\emptyset$. Out of the
infinitely many terms where a new bit $2^{B}$ is introduced, it is almost
always the case that $B\notin{\operatorname{supp}}(m)$. This implies that
there are an infinite number of $0$s in the truth table of
${\operatorname{char}}_{m}$. By Lemma 1, the number of $1$s occurring in the
truth table of ${\operatorname{char}}_{m}$ is also infinite. Thus, there are
an infinite number of occurrences of $01$ in the truth table of
${\operatorname{char}}_{m}$. By Lemma 2, this implies that $m$ appears in the
sequence at some point after the $i^{\prime}$th term. Since
${\operatorname{supp}}(m)$ is disjoint from ${\operatorname{supp}}(k)$, this
is a contradiction of the assumption that ${\operatorname{char}}_{k}(i)=1$ for
all $i>i^{\prime}$. ∎

######  Theorem 5.

Every positive integer $n$ with ${s_{2}}(n)\geq 2$ appears in the sequence.

###### Proof.

Let $k$ be a positive integer with ${s_{2}}(k)=2$. An implication of Lemma 1
is that there is no positive integer $i^{\prime}$ such that $i>i^{\prime}$
implies ${\operatorname{char}}_{k}(i)=0$. An implication of Lemma 3 is that
there is no $i^{\prime}$ such that $i>i^{\prime}$ implies
${\operatorname{char}}_{k}(i)=1$. This proves that there there are infinite
occurrences of $01$ in the truth table of ${\operatorname{char}}_{k}$. By
Theorem 4, the term $k$ must appear in the sequence.

By the previous paragraph, for any positive integer $n$ with ${s_{2}}(n)\geq
2$ there are infinitely many positive integers $x$ with ${s_{2}}(x)=2$ and
${\operatorname{supp}}(x)\ \cap\ {\operatorname{supp}}(n)\neq\emptyset$
appearing in the sequence. There are also infinitely many positive integers
$y$ with ${s_{2}}(y)=2$ and
${\operatorname{supp}}(y)\cap{\operatorname{supp}}(n)=\emptyset$ appearing in
the sequence. This implies that there are infinitely many occurrences of $01$
in the truth table of ${\operatorname{char}}(n)$. By Theorem 4, $n$ must
appear in the sequence. ∎

## References

  * [1] David Applegate, Hans Havermann, Bob Selcoe, Vladimir Shevelev, N. Sloane, and Reinhard Zumkeller, The Yellowstone Permutation, Journal of Integer Sequences 18 (2015).
  * [2] Nathan Nichols, Sequence A338833 in The On-Line Encyclopedia of Integer Sequences, 2020.
  * [3] Scott R. Shannon and N. J. A. Sloane, Sequence A336957 in The On-Line Encyclopedia of Integer Sequences, 2020.
  * [4] N. J. Sloane, Conant’s Gasket, Recaman Variations, the Enots Wolley Sequence, and Stained Glass Windows, 2020.  Rutgers Experimental Mathematics Seminar.
  * [5] Neil J. A. Sloane and The OEIS Foundation Inc., The on-line encyclopedia of integer sequences, 2022.
  * [6] Reinhard Zumkeller, Sequence A098550 in The On-Line Encyclopedia of Integer Sequences, 2004.

2020 _Mathematics Subject Classification_ : Primary 11B83. Secondary 11B75.

_Keywords_ : Enots Wolley, Yellowstone Permutation, permutation of the
nonpowers of 2.

(Concerned with sequences A098550, A336957, A338833.)