\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}
\usepackage{verbatim}
\usepackage{enumerate}
\usepackage{tikz}
\usepackage{forest}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
Variants of Base 3 Over 2
}
\vskip 1cm
\large
Matvey Borodin, Hannah Han, Kaylee Ji, Alexander Peng, David Sun, Isabel Tu, Jason Yang, William Yang, Kevin Zhang, and Kevin Zhao \\
PRIMES STEP \\
Department of Mathematics\\
MIT\\
77 Massachusetts Avenue \\
Cambridge, MA 02139 \\
USA \\
\href{mailto: primes.step@gmail.com}{\tt primes.step@gmail.com}\\
\ \\
Tanya Khovanova \\
Department of Mathematics\\
MIT\\
77 Massachusetts Avenue \\
Cambridge, MA 02139 \\
USA \\
\href{mailto: tanyakh@yahoo.com}{\tt tanyakh@yahoo.com}
\end{center}
\vskip .2 in
\begin{abstract}
We conjecture that the sequence of even non-negative integers represented in base $\frac{3}{2}$ and then evaluated in base 3 is the same as the sequence of first terms of the infinite number of sequences that represent a greedy partition of non-negative integers into 3-free sequences. We also discuss some new sequences related to base $\frac{3}{2}$.
\end{abstract}
\section{Introduction}
Consider a real number $x$. The string $x_nx_{n-1}\cdots x_1x_0.x_{-1}\cdots$ is the representation of $x$ in base $\beta$ if $x = \sum_{i=-\infty}^nx_i\beta^i$.
A traditional non-integer base $\beta > 1$ was explored by R\'{e}nyi
\cite{R} and Parry \cite{P}; it represents numbers using non-negative
integer digits not exceeding $\beta$. Every nonnegative real number has
a representation in such a base. For example, such a representation can
be found by using a greedy algorithm that maximizes the digits $x_i$ from
left to right. In base $\beta$,
integers are typically represented as infinite strings.
Another approach for a rational base $\frac{b}{a}$ was suggested by Propp \cite{JP} and described as the division algorithm in \cite{AFS}. It was also called \textit{exploding dots} and popularized by Tanton \cite{JT}. For a rational base $\frac{b}{a}$ it allows using $\{0,1,\ldots,b-1\}$. The advantage of this approach is that integers can be represented by finite strings. These bases were thoroughly studied by Akiyama et al.~\cite{AFS} and by Frougny and Klouda \cite{FK}.
In this paper, we are interested in base $\frac{3}{2}$, which represents integers using digits 0, 1, and 2. We also consider sequence \seqnum{A256785} in the
{\it On-Line Encyclopedia of Integer Sequences} (OEIS) \cite{OEIS}, which uses digits 0 and 1, and symbol H to represent integers.
Surprisingly, we were able to connect these bases with another sequence, \seqnum{A265316} that is defined as follows. Consider a greedy way to divide non-negative integers into an infinite set of sequences not containing a 3-term arithmetic progression. Then \seqnum{A265316} is formed by taking the first number in each of these sequences. Now consider the following sequence: Take even numbers written in base $\frac{3}{2}$ using exploding dots with digits 0, 1, and 2, and interpret the result in ternary. This yields \seqnum{A265316}.
Here is how this paper is arranged. In Section~\ref{sec:explodingdots} we introduce exploding dots. In Section~\ref{sec:base32}, we describe a particular case of exploding dots called the $2 \leftarrow 3$ machine, which corresponds to base $\frac{3}{2}$. This base uses digits 0, 1, and 2 in their representations. In Section~\ref{sec:base15} we introduce some new sequences related to base $\frac{3}{2}$. And also, the sequence of our main interest which is a sequence of even non-negative integers written in base $\frac{3}{2}$ and then evaluated in base 3, which conjecturally is the same as sequence \seqnum{A265316}.
In Section~\ref{sec:mysteryseq} we define sequence \seqnum{A265316} using greedy partitioning of integers into 3-free sequences and discuss its connections to base $\frac{3}{2}$. We do not completely prove the fact that these sequences are the same, but we exhibit several common properties for both sequences.
\section{Exploding dots}\label{sec:explodingdots}
Here we explain exploding dots. We start with a row of boxes that can be extended to the left. We label the boxes from right to left. The rightmost box is labeled zero. The second one to the right is box 1, the third to the right is box 2, and so on.
We also have an integer $b$ that is our base. Consider integer $N$. To find its value in base $b$, we place $N$ dots in box 0. Now we allow ``explosions''. As soon as there are $b$ dots in box $k$, they ``explode''. That means we remove $b$ dots from box $k$ and add one dot in the box to the left numbered $k+1$. We continue exploding until nothing can explode anymore, meaning each box has no more than $b$ dots. This process is also called a $1 \leftarrow b$ machine. At the end, we write the number of dots in each box from left to right, dropping the leading zeros. The result is the representation of integer $N$ in base $b$.
For example, to calculate 5 in base 2, we start with 5 dots in the rightmost box, box 0. We can represent this state of our machine as 5. Since we have more than two dots, each pair of dots explodes, adding a dot to the box directly to the left. As there are two pairs, we add two dots to box 1 and remove 4 dots from box 0. We can represent the result as 21: one dot in the rightmost box and two dots in the box to the left. Now there are two dots together in box 1; therefore, we have another ``explosion'', which results in base-2 representation of 5 as $101$. This example is represented in Figure~\ref{fig:base2}.
\begin{figure}[ht]
\centering
\includegraphics[scale=0.7]{ExplodingDotsBase2.eps}
\caption{Exploding dots show how to represent 5 in base 2}\label{fig:base2}
\end{figure}
We denote the representation of $N$ in base $b$ as $(N)_b$ and the evaluation of string $w$ written in base $b$ as $[w]_b$. From our previous example we have that $(5)_2 = 101$ and $[101]_2 = 5$.
The exploding dots machines are easily generalized to rational bases. The $a \leftarrow b$ machine is a machine where each time there are at least $b$ dots in a box, there is an explosion. An explosion in box $k$ removes $b$ dots from box $k$ and adds $a$ dots to box $k+1$. To represent an integer $N$, we start with $N$ dots in box zero. After the process is complete, that is, all boxes have fewer than $b$ dots, we read the number of dots from left to right starting with the left most non-empty box. The result is $(N)_\frac{b}{a}$. See \cite{AFS,JP,JT} for more information on rational bases. We number the digits of this representation similar to the way we number boxes, from right to left, resulting in $d_k d_{k-1}\cdots d_1d_0$. As we mentioned we denote this string as $(N)_\frac{3}{2}$.
For example, to calculate 5 in base $\frac{3}{2}$, we start with 5 dots in the rightmost box, box 0. We can represent this state of our machine as 5. Since we have more than three dots we have an explosion: the number of dots in the rightmost box decreases by 3 and we add 2 dots to the box on the left. As the result we get $(5)_\frac{3}{2}= 22$. This example is represented in Figure~\ref{fig:base3over2}.
\begin{figure}[ht]
\centering
\includegraphics[scale=0.6]{ExplodingDotsBase3Over2.eps}
\caption{Exploding dots show how to represent 5 in base $\frac{3}{2}$.}\label{fig:base3over2}
\end{figure}
More formally, we express a non-negative integer $N$ in base $\frac{3}{2}$ recursively. The last digit $d_0$ is the remainder of $N$ modulo 3. The rest of the digits, $d_k d_{k-1}\cdots d_1$, is $\left(\frac{2(N-d_0)}{3}\right)_\frac{3}{2}$.
\section{Base $\frac{3}{2}$}\label{sec:base32}
The $2 \leftarrow 3$ machine is a machine where three dots explode and generate two new dots in the box on the left. More formally, we define how a positive integer $N$ is written in base $\frac{3}{2}$ recursively. Integers 1 and 2 are written as themselves. Represent $N$ as $N = 3N_1 + r$, where $r \in \{0,1,2\}$. Then $N$ is represented as a concatenation of the representation of $2N_1$ and $r$.
For example, number 7 in base $\frac{3}{2}$ becomes 211.
The first several integers written in base $\frac{3}{2}$ form sequence \seqnum{A024629} in the OEIS \cite{OEIS}: \[0, 1, 2, 20, 21, 22, 210, 211, 212, 2100, \ldots.\]
Here are a few observations for how integers are represented in base $\frac{3}{2}$ \cite{JP,JT}:
\begin{itemize}
\item Every integer representation only uses the digits 0, 1, and 2.
\item Every integer greater than 1 has its representation starting with 2.
\item Every integer greater than 7 has its representation starting with 21, followed by either 0 or 2.
\item The last digit of integer representations repeats in a cycle of 3, the last two digits repeat in a cycle of 9, and so on: the last $k$ digits repeat in a cycle of $3^k$.
\item Removing one or several last digits of an integer in this base gives another integer in the base.
\end{itemize}
It is interesting to note that base $\frac{6}{4}$ is different from base $\frac{3}{2}$. For example, numbers in base $\frac{6}{4}$ can have 5 as a digit, while numbers in base $\frac{3}{2}$ can not. For this reason, it is important not to reduce the fraction to simplest terms in this definition of the base. In particular, it is important to call this base `base $\frac{3}{2}$', not base 1.5.
The digits in base $\frac{3}{2}$ represent how the integer $N$ can be decomposed into powers of $\frac{3}{2}$ as the following lemma shows \cite{JP}.
\begin{lemma}
If $(N)_\frac{3}{2} = d_kd_{k-1}\cdots d_1d_0$, then
\[N = \sum_{i=0}^k d_i\frac{3^i}{2^i}.\]
\end{lemma}
\section{Sequences related to base $\frac{3}{2}$}\label{sec:base15}
Another definition of base $\frac{3}{2}$ is given in sequence \seqnum{A256785} in the OEIS \cite{OEIS} and in \cite{AFS,FK}. This base uses three symbols: 0, 1, and H. The symbol H represents 0.5. The letter H was likely chosen because of the word ``\textbf{h}alf''. This base was also studied by Akiyama et al.~\cite{AFS}, and Frougny and Klouda \cite{FK}.
Here are a few rational numbers using these three symbols in \textit{ascending} order of the number values:
\[\text{0, H, H0, 1, H00, HH, 10, H0H, H000, H1, HH0, 1H, H01, H00H, 100, }
\ldots.\]
We denote the terms of this sequence as $A_n$ for $n \ge 0$. The corresponding values are
\[0, 0.5, 0.75, 1, 1.125, 1.25, 1.5, 1.625, 1.6875, 1.75, 1.875, 2, 2.125, 2.1875, 2.25,
\ldots.\]
Correspondingly, we denote the terms of this sequence of values as $(A_n)$.
It is natural to ask how to write this sequence: that is, why is it possible to find the next number in value in an infinite set of numbers? The smallest number with $j$ symbols is H00$\cdots$0: it has $j-1$ zeros and the value of $0.5\cdot 1.5^{j-1}$. Since this value increases as $j$ increases, to find all numbers that are less than $0.5\cdot 1.5^{j-1}$, we only need to have a finite check of all the numbers with less than $j$ symbols.
Clearly, not all of these numbers are integers. The indices of integers in this sequence are
\[0, 3, 11, 25, 46, 77, 117, 169, 232, 308, 401, 508, 631, 771, 929, 1108, 1308, \ldots,\]
which is now sequence \seqnum{A320035}.
The first few natural numbers written in this base are
\[1 =1, \ 2 = 1\text{H}, \ 3 = 1\text{H}0, \ 4 = 1\text{H}1, \ 5 = 1\text{H}0\text{H}, \ 6 = 1\text{H}10, 7 = 1\text{H}11.\]
One interesting feature of this base is that an $i$-symbol number might be smaller than a $j$-symbol number where $i > j$.
There is another convenient order to write these numbers in, which we call the \textit{base} order. Consider numbers that use only zeros and two other digits $a < b$. Write the numbers in the increasing order. Replace $a$ by H, and $b$ by 1. In this order, the numbers with more symbols will go after the numbers with fewer symbols. We denote the terms of this sequence in the base order by $B_n$:
\[\text{0, H, 1, H0, HH, H1, 10, 1H, 11, H00, H0H, H01, HH0, HHH, HH1, }\ldots.\]
The corresponding values are
\[0, 0.5, 1, 0.75, 1.25, 1.75, 1.5, 2, 2.5, 1.125, 1.625, 2.125, 1.875, 2.375, 2.875, \ldots.\]
We denote the terms of this sequence of values as $(B_n)$.
The indices of integers in the base ordered sequence are:
\[0, 2, 7, 21, 23, 64, 69, 71, 193, 207, \ldots.\]
This is the beginning of the sequence \seqnum{A265316}, which is not related to any base. We discuss this unexpected connection in Section~\ref{sec:mysteryseq}.
Meanwhile, we want to introduce some remarkable sequences that show the connection between the ascending order and the base order. The first sequence shows the permutation to transform the numbers in ascending order to the base order. In other words, our sequence $a(n)$ is such that $a(n) = k$, if $(A_k)=(B_n)$. This is always possible because the sequences $(A_n)$ and $(B_n)$ contain the same numbers, just in a different order. This sequence is now \seqnum{A320274}:
\[0, 1, 3, 2, 5, 9, 6, 11, 17, 4, 7, 12, 10, 15, 23, 19, 27, 37, 14, 21, 29, 25, 34, 46,
\ldots.\]
Similarly, we can define sequence $b(n)$ such that $b(n) = k$ if $(B_k)=(A_n)$. This is now sequence \seqnum{A320273}:
\[0, 1, 3, 2, 9, 4, 6, 10, 27, 5, 12, 7, 11, 28, 18, 13, 30, 8, 81, 15, 29, 19,
\ldots.\]
The two sequences above are permutations of non-negative integers. Therefore, they contain every number. By definition, they are inverses of each other.
Writing numbers in base $\frac{3}{2}$ using 0, H, and 1 is very similar to writing numbers using 0, 1, and 2. The following theorem \cite{FK} provides the isomorphism.
\begin{theorem}
Every number in base $\frac{3}{2}$ written using 0, H, and 1 equals the number with 2 times its value in base $\frac{3}{2}$ except with the digits 0, H, 1 replaced by 0, 1, 2 correspondingly.
\end{theorem}
For example, 2 in the first base is 1H. That means 4 in base $\frac{3}{2}$ is 21.
From now on we look not only at integers in base $\frac{3}{2}$, but also all finite strings containing three digits 0, 1, and 2. These numbers are called $\frac{3}{2}$-\textit{integers}.
Using the isomorphism above we know that sequence \seqnum{A320035} is the indices of even integers in the sequence of $\frac{3}{2}$-integers written in ascending order in base $\frac{3}{2}$. The sequence for all integers in base $\frac{3}{2}$ is now sequence \seqnum{A320272}:
\[0, 1, 3, 6, 11, 17, 25, 34, 46, 60, 77, 96, 117, \ldots.\]
Interestingly, if we use the base order, then the indices of integers in $\frac{3}{2}$-integers form sequence \seqnum{A261691}:
\[0, 1, 2, 6, 7, 8, 21, 22, 23, 63, 64, 65, 69, 70, 71, 192, 193, 194, 207, 208, \ldots.\]
The indices of even integers form every other term in \seqnum{A261691}:
\[0, 2, 7, 21, 23, 64, 69, 71, 193, 207, \ldots.\]
As we mentioned, this sequence is one of our main interests.
In other words, this is the sequence of non-negative even integers written in base $\frac{3}{2}$ and then interpreted in base 3.
\section{The mysteries of sequence \seqnum{A265316}}\label{sec:mysteryseq}
\subsection{The definition of \seqnum{A265316}}
Now we go back to sequence \seqnum{A265316}, which appeared above as indices of even integers when numbers containing digits 0, 1, and 2 are written in the base order and interpreted in base $\frac{3}{2}$. We call this sequence the \textit{Stanley cross-sequence}. The first few members are
\[0, 2, 7, 21, 23, 64, 69, 71, 193, 207, 209, 214, \ldots.\]
Before providing the formal definition of the sequence, we need to give a few other definitions. A \textit{3-free} sequence is an integer sequence with no three elements forming an arithmetic progression. Given the start of a sequence of non-negative integers, the \textit{Stanley sequence} is the lexicographically smallest 3-free sequence with the given start \cite{OS}. The simplest Stanley sequence is the one that starts with 0, 1. It is sequence \seqnum{A005836} in the OEIS \cite{OEIS}:
\[0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, \ldots.\]
Now we are ready to give a description of sequence \seqnum{A265316} from the OEIS \cite{OEIS}.
\begin{enumerate}
\item Consider the simplest Stanley sequence: 0, 1, 3, 4, 9, 10 and so on. We denote this sequence $S_0$. This sequence can be described as the non-negative integers that do not contain the digit 2 in their ternary representation.
\item Then we use the leftover integers (i.e., those that are not in the above sequence) and build a new minimal 3-free sequence. The new sequence is 2, 5, 6, 11, 14 and so on. This sequence is now sequence \seqnum{A323398} in the OEIS. We denote this new sequence $S_1$.
\item Then we exclude this sequence too and continue building a new greedy 3-free sequence $S_2$: 7, 8, 16, 17, 19, 20, 34, and so on. This sequence is now sequence \seqnum{A323418} in the OEIS.
\item We continue this procedure to the new sequence $S_3$: 21, 22, 24, 25, 48, 49, 51, and so on, which is now sequence \seqnum{A323419} in the OEIS.
\item R\'{e}nyi \cite{R} proved that 3-free sequences have density zero. Therefore, we can build an infinite number of such sequences. The first number of each of these sequences forms sequence \seqnum{A265316}, which is the subject of this section. In other words, \seqnum{A265316}$(n)$ is the first term of $S_n$.
\end{enumerate}
\subsection{Greedy 3-free sequences in base $\frac{3}{2}$}
We now want to repeat the procedure of building 3-free sequences in base $\frac{3}{2}$, using all finite strings containing three digits 0, 1, and 2, that is, all $\frac{3}{2}$-integers.
It is widely known \cite{OS} that the lexicographically first 3-free sequence, that is, the simplest Stanley sequence, consists of the numbers that are represented in base 3 without twos.
Our situation is somewhat similar. $\frac{3}{2}$-integers interpreted in base $\frac{3}{2}$ have different values when interpreted in base 3. Also, there are two different natural orders on all strings written with 0, 1, and 2. One is the value order if they are interpreted in base 3 or 10 (which we called the base order), and the other one is when they are evaluated in base $\frac{3}{2}$. The second order is different from the first. For example, $10 > 2$ in the first order and $10 < 2$ in the second. The first order is the base order we described before. However, the numbers without twos will be ordered the same way in both orders.
We want to show that the lexicographically first 3-free sequence in $\frac{3}{2}$-integers is the same sequence independently of which order we choose, base 3 value or base $\frac{3}{2}$ value.
\begin{lemma}
The sequence of $\frac{3}{2}$-integers in base $\frac{3}{2}$ that does not contain twos in their base $\frac{3}{2}$ interpretations is a 3-free sequence. Moreover, this sequence is the lexicographically first 3-free sequence in both orders: whether we interpret $\frac{3}{2}$-integers in base 3 or base $\frac{3}{2}$.
\end{lemma}
\begin{proof} The first part of the proof is similar to the corresponding proof for the Stanley sequence starting with 0, 1.
Any $\frac{3}{2}$-integer $x$ that has a digit 2 in base $\frac{3}{2}$ can be written in the form $2b-a$, where $a$ and $b$ are $\frac{3}{2}$-integers without a two in their $\frac{3}{2}$ representation and $b>a$. For example, $x=[20211022021220]_\frac{3}{2} = 2\cdot [10111011011110]_\frac{3}{2} - [00011000001000]_\frac{3}{2}$.
We can choose $(b)_\frac{3}{2}$ by changing twos in $(x)_\frac{3}{2}$ to ones; we can choose $(a)_\frac{3}{2}$ by changing twos in $(x)_\frac{3}{2}$ to zeros. Notice that $a,b < x$ in both orders: whether we interpret $a$, $b$, and $x$ as numbers in base 3 or base $\frac{3}{2}$.
Next, no three different $\frac{3}{2}$-integers without a 2 in their base $\frac{3}{2}$ representation can be in an arithmetic progression. To see why, suppose they were in such a progression. Let the numbers be $a$, $b$, and $2b-a$. If $(a)_\frac{3}{2}$ and $(b)_\frac{3}{2}$ are without a 2, then $(2b)_\frac{3}{2}$ is all 2s and 0s, and $(2b)_\frac{3}{2}$ would need all its 2s digits lined up with all of $(a)_\frac{3}{2}$'s ones for $(2b-a)_\frac{3}{2}$ to not have a 2 remaining after subtraction. But then $a$ and $b$ are the same number, leading to a contradiction. This is the same argument as in base 10. As there are no carries in the argument, the argument works in any base 3 or greater.
We showed that the sequence of $\frac{3}{2}$-integers without twos in base $\frac{3}{2}$ is a 3-free sequence. Now we need to show that it is lexicographically first in both orderings.
The sequence starts with 0 and 1 in both cases.
We continue by induction. Assume by induction that the first $n$ numbers are the $\frac{3}{2}$-integers without a 2 in base $\frac{3}{2}$, the $n$-th number being $y$. We know that the smallest number $z$ such that $z > y$ and $(z)_\frac{3}{2}$ does not have a 2 does not form a 3-free sequence with the previously found numbers, and we must prove it is of the smallest value in both orderings. Suppose it is not of minimal value, and the next term is instead a number $x$ between $y$ and $z$. Then $(x)_\frac{3}{2}$ must contain a 2. As we saw before, $x$ can be represented as $2b-a$, where integers $b$ and $a$ are such that $(b)_\frac{3}{2}$ and $(a)_\frac{3}{2}$ do not have a 2. As $a, b 1$, does not belong to $\mathcal{S}_0$. Integer $n$ must contain a two in its base $\frac{3}{2}$ representation. In fact, it starts with 2. If adding $(a_i)_\frac{3}{2}$ and $(n)_\frac{3}{2}$ does not generate a carry, the result must contain a 2, as $n$ has at least one 2. If there is a carry, the result must contain a 2. Indeed, consider the left-most carry performed during addition. The carry is always an even number. For the carry to be the last, the carry must be a 2, and the digit it is being added to must be 0. Therefore, the result contains a 2.
That means that in $\mathcal{S}_0$ no two numbers differ by an integer more than 1. Suppose $\mathcal{S}_k$ and $\mathcal{S}_j$ overlap, where $i \neq j$. That means there are two numbers $a_{i_1}$ and $a_{i_2}$ in $\mathcal{S}_0$ such that $a_{i_1} + 2k = a_{i_2} +2j$. That means $a_{i_1}$ and $a_{i_2}$ differ by $|2j-2k|$, a contradiction.
\item Every $\frac{3}{2}$-integer belongs to one of the sequences. This can be proven by showing that every $\frac{3}{2}$-integer in its base $\frac{3}{2}$ representation turns into a string with only 1 and 0 by repeatedly subtracting 2. Indeed, if a number contains a 2 in its base $\frac{3}{2}$ representation, then we can always subtract a 2 from it and get a positive $\frac{3}{2}$-integer. We continue subtracting 2 while we have a 2 in base $\frac{3}{2}$ representation of the number. As this process is finite we have to end with a $\frac{3}{2}$-integer consisting only of ones and zeros in its base $\frac{3}{2}$ representation.
\item We know that $\mathcal{S}_0$ is lexicographically first. We proceed by induction. Suppose for $j \leq k$ that sequence $\mathcal{S}_j$ is lexicographically first by value in the set
$\cup_{i \geq j} \mathcal{S}_i$. Consider the lexicographically first sequence $F$ in the set $\cup_{i \geq k} \mathcal{S}_i$. Notice that every element in $F$ has to contain a 2 in its base $\frac{3}{2}$ representation. That means if we subtract a 2 from every element of $F$, we get $\frac{3}{2}$-integers in the set $\cup_{i \geq k-1} \mathcal{S}_i$. It has to be lexicographically first, so it has to equal $\mathcal{S}_k$. Thus, sequence $F$ has to equal $\mathcal{S}_{k+1} =\mathcal{S}_{k} + 2$.
\end{enumerate}
\end{proof}
Let us prove one more property about sequences $\mathcal{S}_i$ written in base $\frac{3}{2}$ that we shall need later. We say that a set of numbers with digits 0, 1, and 2 satisfies the \textit{two-out-of-three property} if the following holds:
\begin{itemize}
\item The last digit of every number in the set written in base $\frac{3}{2}$ uses two out of three possible digits.
\item Numbers in the set that end with the same string $x$ when written in base $\frac{3}{2}$ can only have exactly two possibilities for a digit before $x$, and both possibilities are realized.
\end{itemize}
\begin{lemma}
Sequences $\mathcal{S}_n$ when written in base $\frac{3}{2}$ satisfy the two-out-of three property for all $n \geq 0$.
\end{lemma}
\begin{proof}
Sequence $\mathcal{S}_0$ consists of strings with only zeros and ones when written in base $\frac{3}{2}$. Thus, it satisfies the two-out-of three property. Sequence $\mathcal{S}_n$ is constructed by adding the same number $2n$ to all elements of $\mathcal{S}_0$.
Now we start from the last digit of elements of $\mathcal{S}_n$ when written in base $\frac{3}{2}$ and use induction. The last digit has two possibilities: the last digit of $2n$ and the last digit of $2n+1$, both when written in base $\frac{3}{2}$. Assume, by the induction hypothesis, that all the strings in $(\mathcal{S}_n)_\frac{3}{2}$ that end with the same $m$ digits have only two possibilities for the preceding digit. Now we want to show that the same is true for $m+1$. Consider numbers in $(\mathcal{S}_n)_\frac{3}{2}$ that end with the same string of $m+1$ digits. When we subtract $2n$ from all these numbers we get a set of numbers with a fixed string of length $m+1$ at the end. Before subtracting, we could only have 0 or 1 as a digit. Now when we add $2n$ back to these numbers, we have exactly two possibilities for the digit before the given string of length $m+1$. Both possibilities are realized.
\end{proof}
\subsection{Sequences $\mathcal{S}_i$ in base 3}
Let us first recall a well-known fact about 3-term integer arithmetic progressions.
\begin{lemma}
The last digits of a 3-term arithmetic progression written in base 3 are either all the same or all different.
\end{lemma}
Before proceeding, we need the following statement about sequences $\mathcal{S}_i$.
\begin{lemma}
For any $k \geq 0$, sequence $\mathcal{S}_k$ written in base $\frac{3}{2}$ and then interpreted in base 3 is 3-free.
\end{lemma}
\begin{proof}
Suppose sequence $\mathcal{S}_k$ written in base $\frac{3}{2}$ and then interpreted in base 3 contains an arithmetic progression $a,b,c$. There are only two possibilities for the last digit in base $\frac{3}{2}$. That means $a,b,c$ have the same last digit in base 3. We subtract this digit and divide the resulting numbers by 3, creating the numbers $a',b',c'$ that are numbers $a,b,c$ without the last digit when written in base 3. They have to form an arithmetic progression. By the two-out-of-three property, as the last digit is fixed, there are only two possibilities for the digit before it, which is now the last digit in the new progression $a',b',c'$. It follows that the last digit in $(a')_3$, $(b')_3$, $(c')_3$ is the same for all three numbers. By continuing in the same fashion, we obtain that the numbers $a$, $b$, and $c$ are equal to each other, leading to a contradiction.
\end{proof}
The following statement, which we were not able to prove, is the last step that is needed for our conjecture: each sequence $\mathcal{S}_n$ is lexicographically first 3-free sequence on the available numbers in base 3 order.
Now we state our main conjecture.
\begin{conjecture}
For any $k \geq 0$, sequence $\mathcal{S}_k$ written in base $\frac{3}{2}$ but interpreted in base 3 is sequence $S_k$.
\end{conjecture}
\begin{corollary}
The Stanley cross-sequence can be defined as follows: Take even numbers, write them in base $\frac{3}{2}$, and interpret the resulting string as numbers written in ternary.
\end{corollary}
Let us now describe the sequences $\mathcal{S}_i$, for $i = 1,2,3$ more explicitly.
\subsection{Examples}
We can easily describe the first few sequences $\mathcal{S}_i$ in terms of their representation in base $\frac{3}{2}$:
\begin{itemize}
\item $\mathcal{S}_0$ consists of numbers written with 0 and 1: 0, 1, 10, 11, 100, and so on.
\item $\mathcal{S}_1$ consists of numbers that contain exactly one 2 that might be followed by zeros: 2, 12, 20, 102, 112, 120, 200, and so on.
\item $\mathcal{S}_2$ consists of numbers such that the last digit is 1 or 2 and the rest is a substring from $\mathcal{S}_1$: 21, 22, 121, 122, 201, 202, and so on.
\item $\mathcal{S}_3$ consists of numbers such that the last two digits are from the set $\{10,11,20,21\}$ and the rest is a substring from $\mathcal{S}_1$. Equivalently, we can say that $\mathcal{S}_3$ has 0 and 1 as the last digit and the rest as $\mathcal{S}_2$: 210, 211, 220, 221, 1210, 1211, and so on.
\end{itemize}
\section{Acknowledgments}
This research was done by the PRIMES STEP junior group under the mentorship of Dr.~Tanya Khovanova. PRIMES STEP is a program based at MIT for students in grades 6-9 to try research in mathematics.
We are grateful to PRIMES STEP program and its director, Dr.~Slava Gerovitch, for giving us the opportunity to do this research. We also thank our anonymous reviewer for great comments.
\begin{thebibliography}{99}
\bibitem{AFS} S.~Akiyama, C.~Frougny, and J.~Sakarovitch, Powers of rationals modulo 1 and rational base number systems, {\it Israel J.~Math.}, \textbf{168} (2008), 53--91.
\bibitem{PSS} B.~Chen, R.~Chen, J.~Guo, T.~Khovanova, S.~Lee, N.~Malur, N.~Polina, P.~Sahoo, A.~Sakarda, N.~Sheffield, and A.~Tipirneni, On base 3/2 and its sequences, 2018. Available at \url{https://arxiv.org/abs/1808.04304}.
\bibitem{FK} C.~Frougny and K.~Klouda, Rational base number systems for $p$-adic numbers, \textit{RAIRO Theor.~Inform.~Appl.}, \textbf{46}, (2019), 87--106.
\bibitem{JP} J.~Propp, How do you write one hundred in base 3/2? \url{https://mathenchant.wordpress.com/2017/09/17/how-do-you-write-one-hundred-in-base-32/}, accessed in April 2018.
\bibitem{JT} J.~Tanton, {\it Companion Guide to Exploding Dots}, James Tanton, 2013.
\bibitem{GPS} J.~Gerver, J.~Propp, and J.~Simpson, Greedily partitioning
the natural numbers into sets free of arithmetic progression, {\it
Proc.~Amer.~Math.~Soc.}, \textbf{102} (1988). 765--772.
\bibitem{K} A.~J.~Kempner, Anormal systems of numeration, \textit{Amer.~Math.~Monthly}, \textbf{43} (1936), 610--617.
\bibitem{OS} A.~M.~Odlyzko and R.~P.~Stanley. Some curious sequences
constructed with the greedy algorithm. Bell Laboratories internal
memorandum, 1978.
\bibitem{P} W.~Parry, On the $\beta$-expansions of real numbers, \textit{Acta Math.~Acad.~Sci.~Hung.}, \textbf{11} (1960), 401--416.
\bibitem{R} A.~R\'{e}nyi, Representations for real numbers and their ergodic properties, \textit{Acta Math.~Acad.~Sci.~Hung.}, \textbf{8} (1957), 477--493.
\bibitem{OEIS} N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, published electronically at \url{https://oeis.org}, 2018.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}: Primary 11B99; Secondary 11P99.
\noindent \emph{Keywords:} fractional base, 3-free sequence.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A005836},
\seqnum{A024629},
\seqnum{A244040},
\seqnum{A256785},
\seqnum{A261691},
\seqnum{A265316},
\seqnum{A320035},
\seqnum{A320272},
\seqnum{A320273},
\seqnum{A320274},
\seqnum{A322298},
\seqnum{A323398},
\seqnum{A323418}, and
\seqnum{A323419}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received March 27 2019;
revised version received April 3 2019; January 27 2020; February 16 2020;
February 18 2020.
Published in {\it Journal of Integer Sequences}, February 20 2020.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}