\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\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,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}

\begin{center}
\vskip 1cm{\LARGE\bf Running Modulus Recursions}
\vskip 1cm
\large
Bruce Dearden and Jerry Metzger\\
University of North Dakota\\
Department of Mathematics\\
Witmer Hall Room 313\\
101 Cornell Street Stop 8376\\
Grand Forks ND 58202-8376\\
USA\\
\href{mailto:bruce.dearden@und.ed}{\tt bruce.dearden@und.edu}\\
\href{mailto:jerry.metzger@und.edu}{\tt jerry.metzger@und.edu}\\
\end{center}

\vskip .2in

\begin{abstract}
Fix integers $b\geq 2$ and $k\geq 1$. Define the sequence $\{z_n\}$ recursively by taking $z_0$ to be any integer, and for $n\geq 1$, taking
  $z_n$ to be the  least nonnegative residue of $bz_{n-1}$ modulo $(n+k)$. Since the modulus 
increases by $1$ when stepping from one
term to the next, such a definition  will be called a {\it running modulus recursion} or {\it rumor} for short. While
the terms of such sequences appear to bounce around irregularly, empirical evidence suggests the terms will eventually be zero.  We prove this is so when one additional assumption is made, and we conjecture that this additional
condition is always met.
\end{abstract}

\section{Introduction}
Fix integers $b\geq 2$ and $k\geq 1$. Define the sequence $\{z_n\}$ recursively by taking $z_0$ to be any integer, and for $n\geq 1$, $z_n = {bz_{n-1}\bmod {(n+k)}}$,
the least nonnegative residue of $bz_{n-1}$ modulo $(n+k)$. 
Since the modulus increases by $1$ when stepping from one
term to the next, a sequence generated in this fashion  will be called 
{\it running modulus recursion} or {\it rumor} for short. 

Since only the eventual behavior of  rumors is of interest,
we may as well assume $0\leq z_0 \leq k$: 
using the same $b$ parameter, the sequence with $z_0^{\prime}={z_0\bmod{(k+1)}}$, and, 
for $n\geq 1$, $z_n^{\prime} = {bz_{n-1}^{\prime}\bmod{(n+k)}}$,
differs from the original sequence only in the first term.


The terms of such sequences appear to bounce around irregularly, at least for a while, but empirical evidence 
suggests that eventually a $0$ term will occur in the sequence, and of course, if $0$ occurs in the sequence,
all following terms will also be $0$.

For example, with $z_0 = 1$, and for $n\geq 1$, $z_n ={3z_{n-1}\bmod{(n+11)}}$, the sequence begins
\[
1,3,9,13,9,11,16,12,17,11,12,14,19,9,2,6,18,26,20,0,\ldots.
\]
For this example, $z_{19}$ is the first $0$ term.

While there are many tantalizing patterns, the location of the first $0$ does not seem to obey any simple
general rule. For example, for $k\geq 1$, let  $s_{b,k}$ denote the index of the first $0$ in the rumor 
defined by $z_0=1$, and $z_{n} = {bz_{n-1}\bmod{(n+k)}}$. The sequence
$\{s_{2,k}\}$ begins 
\[
1,2,5,10,3,18,7,24,23,22,13,4,19,18,9,6,15,374,13,12,11,370,369,\ldots.
\]

This erratic behavior continues, 
 as evidenced by the few additional values given in the tables below.

 \medskip


\begin{minipage}{2.3in}
    \begin{tabular}{c|c|c|c}
      \hline
  $z_0$ & $b$ & $k$ & first $0$ term, $s_{2,k}$ \\
\hline\hline
  1 & 2 & 68 & 324 \\
  1 & 2 & 69 & 12161 \\
  1 & 2 & 70 &  322 \\
  1 & 2 & 71 &  25 \\
\hline
    \end{tabular}
  \end{minipage}
  \begin{minipage}{2.3in}
    \begin{tabular}{c|c|c|c}
\hline
$z_0$ & $b$ & $k$ & first $0$ term, $s_{3,k}$ \\
\hline \hline
  1 & 3 & 68 & 784 \\
  1 & 3 & 69 & 783 \\
  1 & 3 & 70 & 782 \\
  1 & 3 & 71 & 10 \\
  \hline     
    \end{tabular}
  \end{minipage}

\section{Eventual Behavior: Condition and Conjecture}
We show that the initial value $z_0$  of a rumor may be naturally written in terms
of a series expansion related to the base-$b$ expansion of a related real number $\zeta_0$.
Under the additional condition that $\zeta_0$ is rational we show that
the rumor is eventually zero. First we establish the natural expansion of $z_0$
relative to the base-$b$ and basic properties of its coefficients.

\begin{lemma}\label{lem:d_n}
Let $b\geq 2$ and $k\geq 1$. Suppose $z_0$ is any integer and, for $n\geq 1$, let
$z_n = {bz_{n-1}\bmod {(n+k)}}$. For $n\geq 1$, let $d_n = \left\lfloor \frac{bz_{n-1}}{n+k} \right\rfloor$ 
so that $z_n = bz_{n-1} - d_n(n+k)$. Then

\begin{enumerate}
 \item[(a)]
$\displaystyle
\sum_{n\geq 1} \frac{d_n(n+k)}{b^n} = z_0,
$

\item[(b)] For $n\geq 2$, $0\leq d_n\leq b-1$,

\item[(c)] $d_n<b-1$ infinitely often,

\item[(d)] $z_n$ is eventually $0$ iff $d_n$ is eventually $0$.
\end{enumerate}
\end{lemma}

\begin{proof}

(a) Since
\[
\frac{z_{n-1}}{b^{n-1}} - \frac{z_n}{b^n} = \frac{d_n(n+k)}{b^n},
\]
we have the telescoping sum 
\[
\sum_{1\leq n \leq j} \frac{d_n(n+k)}{b^n} = \frac{z_0}{b^0} - \frac{z_j}{b^j}.
\]
The last term on the right goes to $0$ as $j\rightarrow\infty$ since $0\leq z_j <(j+k)$
and $b\geq 2$.


(b) For $n\geq 2$, $0\leq z_{n-1}<n-1+k$, and so
\[
0\leq d_n= \left\lfloor \frac{bz_{n-1}}{n+k} \right\rfloor\leq \frac{bz_{n-1}}{n+k}\leq \frac{b(n+k)-b}{n+k} = b - \frac{b}{n+k} < b.
\] 

(c) Suppose $d_n = b-1$ for all $n\geq n_0$ for some $n_0$.
Then, since $z_{n-1} < n+k-1$, 
\[
z_n = bz_{n-1}-(b-1)(n+k) < bz_{n-1} - (b-1)z_{n-1} = z_{n-1}.
\]
So $\{z_n\}$ would be an eventually strictly decreasing sequence of nonnegative integers.


(d) Suppose $d_n$ is eventually $0$. Then for large enough $n$,
\[
z_n = bz_{n-1}-0(n+k) = bz_{n-1},
\]
which means $z_n$ grows like a constant times $b^n$. Since $z_n<n+k$, that implies $z_n$ is
eventually $0$. The converse is obvious.
\end{proof}

\bigskip

We now turn to the main result of this note.


\begin{theorem}\label{thm:cond} Let $b\geq 2$ and $k\geq 1$ be integers.  Let $\{z_n\}$ be the integer sequence with 
initial term $z_0$,  and for $n\geq 1$, 
  $z_n= {bz_{n-1}\bmod{(n+k)}}$, the least nonnegative residue of $bz_{n-1}$ modulo $(n+k)$. Let 
 $d_n = \left\lfloor \frac{bz_{n-1}}{n+k} \right\rfloor$.
 If $\displaystyle \zeta_0=\sum_{n\geq 1}\frac{d_n}{b^n}$ is rational, then $z_n$
 is eventually zero.
\end{theorem}

\begin{proof}

Suppose $\{z_n\}$ and $\{d_n\}$ are constructed as described in the statement of the theorem. 

Notice that for any $m\geq 0$, we can generate the tail $\{z_n\}_{n\geq m}$ of the sequence $\{z_n\}$
as a rumor. To do that we set $z_0^\prime = z_m$, and, for $n\geq 1$, let $z_n^\prime = {bz_{n-1}^\prime\bmod{(n+k+m)}}$. 
Refer to this operation as {\it restarting} the sequence $\{z_n\}$ ({\it at $m$}).

Now suppose $\displaystyle w = \sum_{n\geq 1}\frac{d_n}{b^n}$ is rational. Since, by Lemma~\ref{lem:d_n}(b), $0\leq d_n\leq b-1$ for $n\geq 2$,
we can, after restarting $\{z_n\}$ at $2$ if necessary, view  $\displaystyle \sum_{n\geq 1}\frac{d_n}{b^n}$ as the
base{-}$b$ expansion of $w$. Because $w$ is rational, that expansion will be eventually periodic. Again, restarting
$\{z_n\}$ at some index if necessary, we may as well assume that expansion of $w$ is purely periodic. Let $p$ be the minimal period length of that expansion. 

From Lemma~\ref{lem:d_n}(a) we see
\begin{align*}
z_0 
& = \sum_{m\geq 1} \frac{d_m(m+k)}{b^m} = \sum_{j\geq 0}\sum_{1\leq n\leq p}\frac{d_{pj+n}(pj+n+k)}{b^{pj+n}}\\
& = \sum_{1\leq n\leq p}\sum_{j\geq 0}\frac{d_{pj+n}(pj+n+k)}{b^{pj+n}}\\
& = \sum_{1\leq n \leq p}\left(\frac{d_np}{b^n}\sum_{j\geq 0}\frac{j}{(b^p)^j}+ \frac{nd_n}{b^n}\sum_{j\geq 0}\frac{1}{(b^p)^j}+ \frac{kd_n}{b^n}\sum_{j\geq 0}\frac{1}{(b^p)^j}\right)\\
& = \sum_{1\leq n \leq p}\left(\frac{d_np}{b^n}\frac{\frac{1}{b^p}}{(1-\frac{1}{b^p})^2}+ \frac{nd_n}{b^n}
\frac{1}{1-\frac{1}{b^p}}+ \frac{kd_n}{b^n}\frac{1}{1-\frac{1}{b^p}}\right)\\
& = \sum_{1\leq n \leq p}\left(\frac{d_np}{b^n}\frac{b^p}{(b^p-1)^2}+ \frac{nd_n}{b^n}
\frac{b^p}{b^p-1}+ \frac{kd_n}{b^n}\frac{b^p}{b^p-1}\right)\\
& = \frac{pb^p}{(b^p-1)^2}\sum_{1\leq n \leq p}\frac{d_n}{b^n} +
\frac{b^p}{b^p-1}\sum_{1\leq n \leq p}\frac{nd_n}{b^n} +
\frac{kb^p}{b^p-1}\sum_{1\leq n \leq p}\frac{d_n}{b^n}.
\end{align*}
Multiplying both sides of
\[
z_0 = 
\frac{pb^p}{(b^p-1)^2}\sum_{1\leq n \leq p}\frac{d_n}{b^n} +
\frac{b^p}{b^p-1}\sum_{1\leq n \leq p}\frac{nd_n}{b^n} +
\frac{kb^p}{b^p-1}\sum_{1\leq n \leq p}\frac{d_n}{b^n}
\]
by $b^p-1$  gives

\begin{align*}
z_0 (b^p-1)&= 
\frac{p\sum_{1\leq n\leq p}d_nb^{p-n}}{b^p-1} +
\sum_{1\leq n \leq p}nd_n b^{p-n} +
k\sum_{1\leq n \leq p}d_nb^{p-n}
\end{align*}
Since the terms $z_0(b^p-1)$, $\sum_{1\leq n \leq p}nd_n b^{p-n}$, and  $k\sum_{1\leq n \leq p}d_nb^{p-n}$
are integers, it must be that $\frac{p\sum_{1\leq n\leq p}d_nb^{p-n}}{b^p-1}$ is also an integer,
and so
$b^p-1$ must divide $p\sum_{1\leq n\leq p}d_nb^{p-n}$. 
From Lemma~\ref{lem:d_n}(c), $d_n<b-1$ for at least one $n$ with $1\leq n \leq p$, and so 
$\sum_{1\leq n\leq p}d_nb^{p-n}<\sum_{1\leq n \leq p}(b-1)b^{p-n} = b^p-1$.  It follows that 
either (1) $\sum_{1\leq n \leq p}d_nb^{p-n} =0$, and hence $p=1$, and $d_1=0$ or 
(2) $\sum_{1\leq n \leq p}d_nb^{p-n}>0$,
and hence $\gcd(p, b^p-1)>1$ and $p>1$. To complete the proof,
we will show case (1) must be correct, and so, by  Lemma~\ref{lem:d_n}(d), the (original) sequence $\{z_n\}$ is
eventually $0$.  To that end,  we assume $\gcd(p, b^p-1) = s>1$ (and consequently $p>1$) 
and derive  a contradiction.

Let $r$ be the order of $b$ modulo $s$, so that $r\leq  \varphi(s)$ where $\varphi$ is
Euler's phi function. Since $b^p\equiv 1\, (\rm{mod\ } s)$, 
it follows that $r$ divides $p$.  

 Now $s>1$ and  $s|p$, and so it follows that $r<p$ since $r\leq \varphi(s)<s\leq p$.
Since $r$ is a divisor of $p$, but strictly less than $p$, we have $p=mr$ for some integer $m > 1$. Moreover, there is an integer $a$,  with $1\leq a < b^r - 1$, such that $s a=b^r-1$.  By telescoping we see
\[
 s\left[a+ a b^r + a b^{2r} + \cdots + a b^{(m-1)r}\right] = b^p -1.
\]
It follows that 
\[
 u = \frac{b^p - 1}{s} = a+ a b^r + a b^{2r} + \cdots + a b^{(m-1)r}
\]
has periodic base{-}$b$ digits with a period length $r$. 

Now $u= \frac{b^p - 1}{s}$ and $\frac{p}{s}$  are relatively prime, while
 
\[
u = \frac{b^p - 1}{s}\quad \hbox{ divides } \quad \frac{p}{s}\sum_{1\leq n \leq p } d_n b^{p-n}. 
\]
So for some $v>0$, we have that
\[
 v u  = \sum_{1 \leq n \leq p} d_n b^{p-n} < b^p - 1 = s u.
\]
That implies  $0 < v <s$ and consequently $0 < va < sa=b^r -1$.

Hence, the integer $va$ has base{-}$b$ expansion involving only powers of $b$ less than $r$. Consequently 
\[
 \sum_{1 \leq n \leq p}d_nb^{p-n}=vu =v\left[a+ ab^r + ab^{2r} + \cdots + ab^{(m-1)r}\right]
\]
has periodic  base{-}$b$ digits with period length $r$. It follows that the base{-}$b$ expansion $\sum_{n\geq 1}\frac{d_n}{b^n}$ is periodic with a period $r<p$,  which violates the choice of $p$ as
the minimal period length and the proof is complete.
\end{proof}

Without regard to the rationality condition,   our data shows that, in every tested instance, a rumor as in Theorem~\ref{thm:cond}
is eventually zero. Thus, we have been led to postulate the following conjecture.
\begin{conjecture} With the notation as in Theorem~\ref{thm:cond}, 
 $\displaystyle \sum_{n\geq 1}\frac{d_n}{b^n}$  is rational,  and hence every such  rumor
 is eventually $0$.
\end{conjecture}

\section{Rumors and the Josephus Problem}
Rumors are related to the Josephus problem variation as described by Graham, Knuth, and Patashnik {\cite {GKP}} and
Jensen {\cite {J}}.
Arrange the integers $0$ to $n-1$ in a circle. Beginning at $0$, delete every second remaining number until only one number remains. That last remaining value is denoted by $J_n$. Taking $J_0=0$, it is easy to see that the numbers $J_n$ obey the running modulus recursion

\begin{align*}
J_0&=0\\
J_n &= {(J_{n-1} +2)\bmod{n}}\, \hbox{ for } n\geq 1. 
\end{align*} 

Generalizing that rumor leads to consideration of rumors of the form

\begin{align*}
x_0 & = \hbox{ some nonnegative integer}\\
x_n &={(bx_{n-1} + c)\bmod{n}} \, \hbox{ for } n\geq 1 
\end{align*}
where $b,c$ are positive integers.

Such generalized Josephus rumors exhibit a  number of unexpected behaviors, most of which
are supported presently by empirical evidence only. The most remarkable observation is that, for certain
pairs $b,c$, all such sequences appear to synchronize  in the sense described in the following conjecture.

\begin{conjecture}\label{conj:jos} For the sequence $\{x_n\}$ given above, if $c = j(b-1)+1$ for some $j\geq 2$,
then eventually $x_n = n-j+1$. 
\end{conjecture}

So when $b$ and $c$ are related as in the conjecture, it appears the sequence eventually becomes a sequence of consecutive integers. In this case we say the rumor sequence eventually {\it walks}. In particular then, for any initial term, $x_0$,  as long as $c = j(b-1)+1$, any two such sequences  will eventually synchronize in the sense that eventually corresponding terms will differ by a fixed
constant, and for a fixed $j\geq 2$ for any two $b\geq 2$ and any $x_0$, the sequences are eventually identical.

On the other hand, if $b$ and
$c$ are not related as described, it appears the sequence never walks, and in fact the terms
show no easily discernible  pattern at all.

When  a sequence does walk, the point at which the walk begins is surprisingly
variable, which may partly explain the difficulty  establishing the conjecture.
For example, the rumor
\begin{align*}
x_0 & = 0\\
x_n &= {(2x_{n-1} + 291)\bmod{n}} \, \hbox{ for } n\geq 1 
\end{align*}
begins walking at term number  $570$.

On the other hand, the rumor
\begin{align*}
x_0 & = 0\\
x_n &= {(2x_{n-1} + 292)\bmod{n}} \, \hbox{ for } n\geq 1 
\end{align*}
begins walking at term number $69 921 608 358$,
while
\begin{align*}
x_0 & = 0\\
x_n &= {(2x_{n-1} + 293)\bmod{n}} \, \hbox{ for } n\geq 1 
\end{align*}
begins walking at term number $13942$.


The rumor given by $x_0=0$ and $x_n= {(2x_{n-1}+c)\bmod{n}}$ for $n\geq 1$ 
will eventually walk for all $c\geq 3$ according to Conjecture~\ref{conj:jos}.  
For $3\leq c\leq 23$, the walks begin at 

\[
1,2,8,32,6,8,38,38,48,16,384,174,24,34,16,120,26,26,680,680,5600,\ldots
\]

\section{Acknowledgements}
The authors would like to thank the referee for the many comments that improved both the content and style of this paper.

\begin{thebibliography}{10}
\bibitem{GKP} 
R{.} Graham, D{.} Knuth, O{.} Patashnik, {\it  Concrete Mathematics, 2$^{nd}$ ed.}, Addison-Wesley, 1994.

\bibitem{J}
B{.} Jensen, The Running Modulus,  Master's Independent Study, University of North Dakota, 2000.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:  
Primary 11B37; Secondary 11B50.

\noindent {\it Keywords}: recurrence sequence, recurrence relation modulo $m$, Josephus problem, running modulus recursion




\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 2 2009;
revised version received January 12 2010.
Published in {\it Journal of Integer Sequences}, January 14 2010.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}