\documentclass{article}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage[english]{babel}

%                            ---------- o ----------

\newcommand{\set}[1]{\ensuremath{\left\{ #1 \right\}}}
\newcommand{\abs}[1]{\ensuremath{\left| #1 \right|}}
\newcommand{\coset}[1]{\ensuremath{\left[ #1 \right]}}
\newcommand{\floor}[1]{\ensuremath{\left\lfloor #1 \right\rfloor}}
\newcommand{\field}[1]{\ensuremath{\mathbb{#1}}}
\newcommand{\R}{\field{R}}
\newcommand{\T}{\field{T}}
\newcommand{\Z}{\field{Z}}
\newcommand{\Zp}{\Z^+}

%                            ---------- o ----------

\begin{document}
\sloppy

%                            ---------- o ----------

\author{Mateusz Kwa\'snicki}
\title{The solution of M-D problem}
\maketitle

%                            ---------- o ----------

\section{Problem description}

%                            ---------- o ----------

Let $p, q$ be any integer numbers greater that $1$. We define the \emph{multiply-and-divide (M-D) sequence} $(a_n)$ for the multiplier $p$ and divisor $q$ recursively as follows. Begin with $a_1 = 1$ and take $a_{n+1}$ equal to either $\floor{a_n / q}$ ($\floor{x}$ denotes floor of $x$, the largest integer not exceeding $x$) if this number is positive and has not yet occured in the sequence or $p a_n$ otherwise.

For instance, if $p = 3$ and $q = 2$, the corresponding M-D sequence is $1, 3, 9, 4, 2, 6, 18, 54, 27, 13, 39, 19, 57, 28, 14, 7, 21, \dots$.

Given $p, q$, the M-D problem is to determine whether every positive integer occurs exactly once in the M-D sequence. In this paper we prove that the answer is positive if and only if $\log_q p$ is irrational. This condition is equivalent to $p^n \ne q^m$ unless $n = m = 0$. In particular if $p$ and $q$ are relatively prime, every positive integer occurs exactly once in the M-D sequence.

The M-D problem originated in \emph{Crux Mathematicorum}, volume 26 (2000), problem 2248.

Note that the 'only if' part is clear: if $\log_q p$ is rational, then $q^n = p^m$ for some relatively prime $n, m > 0$. Hence $q^{1/m} = p^{1/n}$ is integer greater than $1$; denote it by $d$. Clearly if $(a_n)$ is the M-D sequence for $p$ and $q$, then $a_n = d^{k_n}$ for some nonnegative integer $k_n$. In particular there are positive integer numbers (such as $d+1$) which do not occur in the M-D sequence. The rest of this article is dedicated to the 'if' part of the statement.

%                            ---------- o ----------

\section{Notation}

%                            ---------- o ----------

We denote sets of integer numbers, positive integer numbers and real numbers by $\Z$, $\Zp$, $\R$ respectively. The quotient group of additive (topological) groups $\R$ and $\Z$ (which is isomorphic to $\left[ 0, 1 \right)$ with addition 'modulo 1') will be denoted by $\T$. Elements of $\T$ are cosets $\coset{a} = a + \Z = \set{a + n : n \in \Z}$, where $a \in \R$. Let $\kappa : \R \rightarrow \T$ be the canonical homomorphism defined by $\kappa(a) = \coset{a}$. We recall that a subset $U$ of $\T$ is open if and only if $\kappa^{-1}(U)$ is an open subset of $\R$ (with usual topology). Moreover, if $V$ is any open subset of $\R$ then $\kappa(V)$ is open in $\T$, that is $\kappa$ is an open mapping. In fact, define $U = \kappa(V)$, $W = \kappa^{-1}(U)$. Then:
\begin{equation*}
\begin{split}
W & = \set{a : \coset{a} \in U} =
\set{a : \exists_{b \in U} \ a \in \coset{b}} = \\
& =
\set{a : \exists_{b \in U} \exists_{n \in \Z} \ a = b + n} =
\set{a : \exists_{n \in \Z} \ a \in V + n} = \\
& =
\bigcup_{n \in \Z} (V + n)
\end{split}
\end{equation*}
is open since every $(V + n) = \set{v + n : v \in V}$ is open. Hence $U$ is open.

We denote natural logarithm of $x$ by $\ln x$ and logarithm of $x$ in base $y$ by $\log_y x$.

%                            ---------- o ----------

\section{Formal definition of M-D sequence}

%                            ---------- o ----------

Take any $p, q > 1$ such that $\log_q p$ is irrational and denote the corresponding M-D sequence $(a_n)$. Define:
\begin{equation*}
\begin{array}{l}
A_n = \set{0} \cup \set{a_m : m \le n}, \\
A = \set{a_m : m \in \Zp}, \\
B = \Zp \backslash A.
\end{array}
\end{equation*}
The M-D sequence $(a_n)$ is thus defined by:
\begin{equation} \label{eq:MDdef}
\begin{array}{ll}
a_1 = 1, \\
a_{n+1} = p a_n & \quad \text{if } \floor{a_n / q} \in A_n, \\
a_{n+1} = \floor{a_n / q} & \quad \text{if } \floor{a_n / q} \notin A_n.
\end{array}
\end{equation}
We need to prove two statements:
\begin{gather}
a_n = a_m \text{ implies } n = m, \label{eq:first} \\
B = \emptyset. \label{eq:second}
\end{gather}

%                            ---------- o ----------

\section{Two properties of $A_n$, $A$ and $B$}

%                            ---------- o ----------

Fix any positive $n$ and assume that $\floor{a_n / q^k} \in A_n$ for some $k \in \Zp$. If $\floor{a_n / q^k} = 0$, then $\floor{a_n / q^{k+1}} = 0 \in A_n$. If $\floor{a_n / q^k} \ne 0$, then $\floor{a_n / q^k} = a_m$ for some $m \le n$; $m$ cannot be equal to $n$, since $\floor{a_n / q^k} < a_n$. Thus $m < n$. It follows that either $\floor{a_m / q} \in A_m \subset A_n$ or $\floor{a_m / q} = a_{m+1} \in A_n$. Hence $\floor{a_n / q^{k+1}} = \floor{a_m / q} \in A_n$. By an induction argument we get:
\begin{equation} \label{eq:order}
\text{If } \floor{a_n / q} \in A_n, \text{ then } \floor{a_n / q^k} \in A_n \text{ for any } k \in \Zp.
\end{equation}
Now take any $a \in A$. Then $a = a_n$ for some $n$. Either $\floor{a_n / q} = a_{n+1} \in A$ or $\floor{a_n / q} \in A_n \subset A \cup \set{0}$. Hence $\floor{a / q} \in A$ or $\floor{a / q} = 0$. By induction we get $\floor{a / q^k} \in A$ or $\floor{a / q^k} = 0$. Writing $b = \floor{a / q^k}$ we get:
\begin{equation} \label{eq:tree}
\text{If } b \in B, \text{ then } q^k b + l \in B \text{ for any } k \in \Zp, 0 \le l < q^k.
\end{equation}

%                            ---------- o ----------

\section{Simple floor law}

%                            ---------- o ----------

Let $p a = \floor{p x}$, where $x \in \R$, $a \in \Z$ and $p \in \Zp$. Then:
\begin{equation*}
a = \floor{a} = \floor{\frac{\floor{p x}}{p}} = \floor{\frac{px}{p}} = \floor{x}.
\end{equation*}
Hence:
\begin{equation} \label{eq:floorlaw}
p a = \floor{p x} \text{ implies } a = \floor{x},
\end{equation}
$x \in \R$, $a \in \Z$, $p \in \Zp$.

%                            ---------- o ----------

\section{Topological dynamics lemma}

%                            ---------- o ----------

The following is a simple version of a general topological dynamics result on rotations on compact topological groups:
\begin{quotation}
Let $a$ be an irrational number, $U \subset \T$ a nonempty open set. Then there exists $N \in \Zp$ such that for every $x \in \R$ there exists $n$, $0 \le n \le N$, such that $\coset{x + n a} \in U$.
\end{quotation}
Fix $x \in \R$ and let $A = \set{\coset{x + n a} : n \ge 0}$. Then $A$ is dense in $\T$ (see any book on topological dynamics). Hence $\coset{x + na} \in U$ for some $n$ and so $\coset{x} \in \bigcup_{n = 0}^{\infty} (U - \coset{n a})$. Since $x$ was arbitrary, $\bigcup_{n = 0}^{\infty} (U - \coset{n a}) = \T$. By compactness of $\T$ there exist $N \in \Zp$ such that $\bigcup_{n = 0}^N (U - \coset{n a}) = \T$. Take any $x \in \R$. Then, for some $n$, $0 \le n \le N$, we have $\coset{x + n a} \in U$.

%                            ---------- o ----------

\section{Proof of \eqref{eq:first}}

%                            ---------- o ----------

Assume on the contrary that $a_i = a_j$ for some $i \ne j$. Let $n$ be the smallest number such that $a_n = a_m$ for some $m$, $0 < m < n$. Clearly $a_n \in A_{n-1}$. Hence $a_n = p a_{n-1}$ ($a_n = \floor{a_{n-1} / q}$ if and only if $\floor{a_{n-1} / q} \notin A_{n-1}$). Let $i \le m$ be such that:
\begin{equation*}
a_m = \floor{a_{m - 1} / q},
a_{m - 1} = \floor{a_{m - 2} / q}, \dots,
a_{i + 1} = \floor{a_i / q},
a_i = p a_{i - 1}.
\end{equation*}
(Note that such $i$ exists, since $a_2 = p a_1$.) Take $k = m - i$. Then:
\begin{equation*}
p a_{n - 1} = a_n = a_m = \floor{a_i / q^k} = \floor{p a_{i - 1} / q^k}.
\end{equation*}
Hence, by \eqref{eq:floorlaw}, $a_{n-1} = \floor{a_{i-1} / q^k}$. Now $a_i = p a_{i-1}$ implies $\floor{a_{i-1} / q} \in A_{i - 1}$. From property \eqref{eq:order} it follows that:
\begin{equation*}
a_{n - 1} = \floor{a_{i - 1} / q^k} \in A_{i - 1}.
\end{equation*}
In other words, $a_{n - 1} = a_j$ for some $j \le i - 1 < n - 1$. This contradicts the choice of $n$. Hence our assumption was false and so we proved \eqref{eq:first}. Note that we did not use irrationality of $\log_q p$.

%                            ---------- o ----------

\section{Proof of \eqref{eq:second}}

%                            ---------- o ----------

Again, assume contrary to \eqref{eq:second} that $B$ is nonempty. Let $a$ be any element of $B$. We will show that $q^t a + s \notin B$ for some $t, s \in \Zp$, $0 \le s < q^t$, which contradicts property \eqref{eq:tree}. The key observation is that $b = q^t a + s$ if and only if $\log_q a - \log_q b$ is nearly an integer or, in other words, the distance between $\coset{\log_q a}$ and $\coset{\log_q b}$ in $\T$ is very small. Hence it is sufficient to show that the set of cosets $\coset{\log_q a_n}$ may not be separated from $\coset{\log_q a}$ for all $n$. It will turn out that the sequence $\coset{\log_q a_n}$ has much in common with irrational rotations, well studied transformations on $\T$.

Relation \eqref{eq:first} implies that $\lim_{n \rightarrow \infty} a_n = \infty$. It follows that there are infinitely many $n$ such that $a_{n+1} = p a_n$; let $k_1, k_2, \dots$ be increasing sequence of all those $n$. Hence:
\begin{equation} \label{eq:subsequence}
a_{k_{n+1}} = \floor{\frac{a_{k_n+1}}{q^{k_{n+1} - k_n - 1}}}, \quad a_{k_n+1} = p a_{k_n}.
\end{equation}
Let $b_n = \log_q a_n$, $\alpha = \log_q p$; $\alpha$ is irrational. Define:
\begin{equation*}
\epsilon_n = \log_q \frac{a_{k_n+1}}{q^{k_{n+1} - k_n - 1}} - \log_q a_{k_{n+1}} =
b_{k_n+1} - b_{k_{n+1}} - k_{n+1} + k_n + 1.
\end{equation*}
Relations \eqref{eq:subsequence} and $\floor{x} \le x < \floor{x}+1$ for $x \in \R$ imply that:
\begin{equation} \label{eq:epsilon}
\begin{split}
0 \le \epsilon_n & < \log_q (a_{k_{n+1}} + 1) - \log_q a_{k_{n+1}} = \\
& =
\log_q \left(\frac{a_{k_{n+1}}+1}{a_{k_{n+1}}} \right) < \frac{1}{a_{k_{n+1}} \ln q}.
\end{split}
\end{equation}
By definition of $\epsilon_n$ and \eqref{eq:subsequence}:
\begin{equation} \label{eq:cosets}
\begin{array}{l}
\coset{b_{k_{n+1}}} = \coset{b_{k_n+1} - \epsilon_n}, \\
\coset{b_{k_n+1}} = \coset{\log_q (p a_{k_n})} = \coset{b_{k_n} + \alpha}.
\end{array}
\end{equation}
This is exactly what we needed: $\coset{b_{k_{n+1}}}$ is very close to $\coset{b_{k_n+1}}$, which is an irrational rotation of $b_{k_n}$. Hence we can apply topological dynamics methods. Before we proceed with some technical details, let us recall that we are looking for $a_m$ such that $a_m = q^t a + s$ for some $t, s \in \Zp$, $0 \le s < q^t$, which is equivalent to $\log_q a_m \in (\log_q a + t, \log_q (a + 1) + t)$.

%                            ---------- o ----------
\bigskip

Define:
\begin{equation*}
\begin{array}{l}
\delta = \log_q (a + \frac{1}{2}) - \log_q a, \\
V = \left(\log_q (a + \frac{1}{2}), \log_q (a + 1)\right), \\
U = \kappa(V).
\end{array}
\end{equation*}
Since $U$ is a nonempty open subset of $\T$ and $\alpha$ is irrational, a topogical dynamics lemma implies that there exists $L \in \Zp$ such that for every $x \in \R$ we have $\coset{x + l \alpha} \in U$ for some $l$, $0 \le l \le L$.

Let $M$ be large enough so that $L < M \delta \ln q$. Since $\lim_{n \rightarrow \infty} a_n = \infty$, there exists $N$ such that $a_n > M$ for $n \ge N$. Fix any $n$ such that $k_n \ge N$. For some $l$, $0 \le l \le L$, we have $\coset{b_{k_n} + l \alpha} \in U$. Equivalently, for some $i \in \Z$:
\begin{equation*}
b_{k_n} + l \alpha + i \in V.
\end{equation*}
By definition of $V$:
\begin{equation} \label{eq:partialestimate}
\begin{array}{l}
\log_q (a + \frac{1}{2}) < b_{k_n} + l \alpha + i < \log_q (a + 1)
\end{array}
\end{equation}
Let $m = n + l$. Using \eqref{eq:cosets} and simple induction argument we get:
\begin{equation*}
\coset{b_{k_m}} = \coset{b_{k_n} + l \alpha - \epsilon_n - \epsilon_{n+1} - \dots - \epsilon_{m-1}}.
\end{equation*}
Again this is equivalent to:
\begin{equation*}
b_{k_m} = b_{k_n} + l \alpha - \epsilon_n - \epsilon_{n+1} - \dots - \epsilon_{m-1} + j
\end{equation*}
for some $j \in \Z$. Recall that if $n \le \nu < m$, then $k_{\nu+1} > k_n \ge N$ and so $a_{k_{\nu+1}} > M$. According to \eqref{eq:epsilon} we get $0 \le \epsilon_\nu < (a_{k_{\nu+1}} \ln q)^{-1} < (M \ln q)^{-1}$, so that:
\begin{equation*}
b_{k_n} + l \alpha + j - \frac{l}{M \ln q} < b_{k_m} \le b_{k_n} + l \alpha + j.
\end{equation*}
But $M$ was defined so that $l / (M \ln q) \le L / (M \ln q) < \delta$. Hence:
\begin{equation*}
b_{k_n} + l \alpha + j - \delta < b_{k_m} \le b_{k_n} + l \alpha + j.
\end{equation*}
Together with \eqref{eq:partialestimate} and the definition of $\delta$ this leads us to:
\begin{equation*}
\begin{array}{l}
\log_q (a + \frac{1}{2}) + j - i - (\log_q(a + \frac{1}{2}) - \log_q a) < b_{k_m} < \log_q (a+1) + j - i.
\end{array}
\end{equation*}
Finally we get:
\begin{equation*}
\log_q a + j - i < b_{k_m} < \log_q (a + 1) + j - i.
\end{equation*}
In terms of $a_\nu$ this means:
\begin{equation*}
q^{j - i} a < a_{k_m} < q^{j - i} (a + 1).
\end{equation*}
It follows that $j - i > 0$ and $a_{k_m} = q^t a + s$ for $t = i - j$ and some $s$ such that $0 < s < q^t$. Contradiction with \eqref{eq:tree}.

This proves that $B$ is empty and completes our solution.

%                            ---------- o ----------

\end{document}
