\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}

\usepackage{caption}
\usepackage{rotating}


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

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\DeclareMathOperator{\lcm}{lcm}

\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 Rumor Arrays}
\vskip 1cm
\large
Bruce Dearden, Joel Iiams, 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.edu}{\tt bruce.dearden@und.edu}\\
\href{mailto:joel.iiams@und.edu}{\tt joel.iiams@und.edu}\\
\href{mailto:jerry.metzger@und.edu}{\tt jerry.metzger@und.edu}\\
\end{center}

\vskip .2in

\begin{abstract}
 Rumor sequences are generated recursively as follows: fix nonnegative integers $b$, $c$,  and  let $z_{0}=0$. 
For $n\geq 1$, define $z_{n}= (bz_{n-1}+c) \mod{n}$,
where the least nonnegative residue modulo $n$ is taken.  There have been a few papers dealing with the behavior of rumor sequences, but they all concern that behavior when the value of $c$ is fixed.  It turns out that if, for a given value of $b$, the rumor sequences for $c=0,1,2,\ldots$ are written down, one below the other,  some
interesting and unexpected patterns appear in the columns of that array. These patterns are investigated, proving some, and, based on computer generated data, we make two conjectures.

 \end{abstract}

\section{Introduction}

Rumor sequences are generated recursively as follows: fix nonnegative integers $b$, $c$,  and  let $z_{0}=0$. 
For $n\geq 1$, define $z_{n}= (bz_{n-1}+c) \mod{n}$,
where the least nonnegative residue modulo $n$ is taken. The construction of such sequences is very natural and such sequences exhibit some unexpected behavior, so it is not surprising that the notion of a rumor sequence has been independently rediscovered and mentioned in the literature several times. The earliest reference 
we can find is  Borwein and Loring  \cite[p.\ 379]{bl}, where they investigate a question raised by Erd\H{o}s \cite{er}  in 1975 and again by Erd\H{o}s and Graham \cite[p.\ 62]{erg} in 1980. It seems next to have appeared in Vantieghem \cite{va} in 1996, and, most recently,  in 2010, where Dearden and Metzger \cite{dm} coined the term {\it rumor} (for running modulus recursion). In that note, the general notion of a rumor sequence is considered: a sequence constructed recursively, with each new term computed using a modulus $1$ more than that used for the previous term.  Almost surely there are other papers that mention this idea, but, because there has been no common (catchy) name for such sequences, locating them has proved difficult.

The papers we are aware of consider various aspects of the behavior of rumor sequences, but they all concern the behavior when the value of $c$ is fixed.  It turns out that if, for a given value of $b$, the rumor sequences for $c=0,1,2,\ldots$ are written down, one below the other,  some
interesting and unexpected patterns appear in the columns of that {\it rumor array}.  In this paper we will investigate these patterns, proving some, and, based on computer experimentation, we make two conjectures.

Using $RA_{b}$ to denote the rumor array generated with parameter $b$, two such arrays,  $RA_{2}$ and $RA_{6}$, 
are shown in the  tables included here.

\setlength{\arraycolsep}{3.5pt}
\begin{sidewaysfigure}
\begin{center}
\[\begin{array}{rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr}
 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &
0 \\
 1 & 0 & 1 & 0 & 1 & 3 & 1 & 3 & 7 & 6 & 3 & 7 & 3 & 7 & 1 & 3 & 7 & 15 & 13 & 8 & 17 & 14 & 7 & 15 & 7 & 15 & 5 & 11 & 23 & 18 & 7 & 15 & 31 & 30
& 27 & 20 & 5 \\
 2 & 0 & 0 & 2 & 2 & 1 & 4 & 3 & 0 & 2 & 6 & 3 & 8 & 5 & 12 & 11 & 8 & 1 & 4 & 10 & 2 & 6 & 14 & 7 & 16 & 9 & 20 & 15 & 4 & 10 & 22 & 15 & 0 & 2
& 6 & 14 & 30 \\
 3 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 &
30 & 31 & 32 & 33 & 34 & 35 \\
 4 & 0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29
& 30 & 31 & 32 & 33 & 34 \\
 5 & 0 & 1 & 1 & 3 & 1 & 1 & 0 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28
& 29 & 30 & 31 & 32 & 33 \\
 6 & 0 & 0 & 0 & 2 & 0 & 0 & 6 & 2 & 1 & 8 & 0 & 6 & 5 & 2 & 10 & 10 & 9 & 6 & 18 & 2 & 10 & 4 & 14 & 10 & 1 & 8 & 22 & 22 & 21 & 18 & 11 & 28 &
29 & 30 & 31 & 32 \\
 7 & 0 & 1 & 0 & 3 & 3 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 &
27 & 28 & 29 & 30 & 31 \\
 8 & 0 & 0 & 2 & 0 & 3 & 2 & 5 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 &
26 & 27 & 28 & 29 & 30 \\
 9 & 0 & 1 & 2 & 1 & 1 & 5 & 5 & 3 & 6 & 1 & 0 & 9 & 1 & 11 & 1 & 11 & 14 & 1 & 11 & 11 & 10 & 7 & 0 & 9 & 2 & 13 & 8 & 25 & 1 & 11 & 0 & 9 & 27
& 29 & 32 & 1 \\
 10 & 0 & 0 & 1 & 0 & 0 & 4 & 4 & 2 & 5 & 0 & 10 & 6 & 9 & 0 & 10 & 14 & 4 & 0 & 10 & 10 & 9 & 6 & 22 & 6 & 22 & 2 & 14 & 10 & 1 & 12 & 3 & 16 &
9 & 28 & 31 & 0 \\
 11 & 0 & 1 & 1 & 1 & 3 & 5 & 0 & 3 & 8 & 7 & 3 & 5 & 8 & 13 & 7 & 9 & 12 & 17 & 7 & 5 & 0 & 11 & 10 & 7 & 0 & 11 & 6 & 23 & 28 & 7 & 25 & 29 & 3
& 17 & 10 & 31 \\
 12 & 0 & 0 & 0 & 0 & 2 & 4 & 6 & 0 & 3 & 8 & 6 & 0 & 12 & 8 & 13 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22
& 23 & 24 & 25 & 26 \\
 13 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 7 & 0 & 3 & 8 & 5 & 10 & 5 & 8 & 13 & 5 & 5 & 4 & 1 & 15 & 21 & 9 & 7 & 2 & 17 & 20 & 25 & 5 & 23 & 28 & 5 & 23
& 25 & 28 & 33 \\
 14 & 0 & 0 & 2 & 2 & 3 & 2 & 4 & 6 & 8 & 0 & 3 & 8 & 4 & 8 & 0 & 14 & 8 & 12 & 0 & 14 & 0 & 14 & 19 & 4 & 22 & 6 & 26 & 10 & 5 & 24 & 0 & 14 & 9
& 32 & 8 & 30 \\
 15 & 0 & 1 & 2 & 3 & 1 & 5 & 4 & 7 & 2 & 9 & 0 & 3 & 8 & 3 & 6 & 11 & 3 & 3 & 2 & 19 & 11 & 15 & 22 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19
& 20 & 21 & 22 & 23 \\
 16 & 0 & 0 & 1 & 2 & 0 & 4 & 3 & 6 & 1 & 8 & 10 & 0 & 3 & 8 & 2 & 4 & 7 & 12 & 2 & 0 & 16 & 4 & 1 & 18 & 2 & 20 & 2 & 20 & 27 & 10 & 5 & 26 & 2
& 20 & 21 & 22 \\
 17 & 0 & 1 & 1 & 3 & 3 & 5 & 6 & 5 & 0 & 7 & 9 & 11 & 0 & 3 & 8 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18
& 19 & 20 & 21 \\
 18 & 0 & 0 & 0 & 2 & 2 & 4 & 5 & 4 & 8 & 4 & 4 & 2 & 9 & 8 & 4 & 10 & 4 & 8 & 15 & 8 & 13 & 0 & 18 & 6 & 5 & 2 & 22 & 6 & 1 & 20 & 27 & 8 & 1 &
20 & 23 & 28 \\
 19 & 0 & 1 & 0 & 3 & 0 & 1 & 0 & 3 & 7 & 3 & 3 & 1 & 8 & 7 & 3 & 9 & 3 & 7 & 14 & 7 & 12 & 21 & 15 & 1 & 21 & 9 & 10 & 11 & 12 & 13 & 14 & 15 &
16 & 17 & 18 & 19 \\
 20 & 0 & 0 & 2 & 0 & 0 & 2 & 3 & 2 & 6 & 2 & 2 & 0 & 7 & 6 & 2 & 8 & 2 & 6 & 13 & 6 & 11 & 20 & 14 & 0 & 20 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15
& 16 & 17 & 18 \\
 21 & 0 & 1 & 2 & 1 & 3 & 3 & 6 & 1 & 5 & 1 & 1 & 11 & 4 & 1 & 8 & 5 & 14 & 13 & 9 & 19 & 17 & 11 & 20 & 13 & 22 & 13 & 20 & 5 & 2 & 25 & 9 & 7 &
2 & 25 & 1 & 23 \\
 22 & 0 & 0 & 1 & 0 & 2 & 2 & 5 & 0 & 4 & 0 & 0 & 10 & 3 & 0 & 7 & 4 & 13 & 12 & 8 & 18 & 16 & 10 & 19 & 12 & 21 & 12 & 19 & 4 & 1 & 24 & 8 & 6 &
1 & 24 & 0 & 22 \\
 23 & 0 & 1 & 1 & 1 & 0 & 5 & 5 & 1 & 7 & 7 & 4 & 7 & 11 & 3 & 14 & 3 & 12 & 11 & 7 & 17 & 15 & 9 & 18 & 11 & 20 & 11 & 18 & 3 & 0 & 23 & 7 & 5 &
0 & 23 & 34 & 19 \\
 24 & 0 & 0 & 0 & 0 & 4 & 2 & 0 & 0 & 6 & 6 & 3 & 6 & 10 & 2 & 13 & 2 & 11 & 10 & 6 & 16 & 14 & 8 & 17 & 10 & 19 & 10 & 17 & 2 & 28 & 20 & 2 & 28
& 14 & 18 & 25 & 2 \\
 25 & 0 & 1 & 0 & 1 & 2 & 5 & 0 & 1 & 0 & 5 & 2 & 5 & 9 & 1 & 12 & 1 & 10 & 9 & 5 & 15 & 13 & 7 & 16 & 9 & 18 & 9 & 16 & 1 & 27 & 19 & 1 & 27 & 13
& 17 & 24 & 1
\end{array}\]
\caption*{$RA_{2}$: $z_{n}= 2z_{n-1}+c \mod n$, $c = 0,1,\ldots25$. Leftmost column gives $c$.}
\end{center}
\end{sidewaysfigure}
 
\begin{sidewaysfigure}
\begin{center}
\[
\begin{array}{rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr}
 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &
0        \\
 1 & 0 & 1 & 1 & 3 & 4 & 1 & 0 & 1 & 7 & 3 & 8 & 1 & 7 & 1 & 7 & 11 & 16 & 7 & 5 & 11 & 4 & 3 & 19 & 19 & 15 & 13 & 25 & 11 & 9 & 25 & 27 & 3 & 19
& 13 & 9 & 19         \\
 2 & 0 & 0 & 2 & 2 & 4 & 2 & 0 & 2 & 5 & 2 & 3 & 8 & 11 & 12 & 14 & 6 & 4 & 8 & 12 & 14 & 2 & 14 & 17 & 8 & 0 & 2 & 14 & 2 & 14 & 26 & 3 & 20 & 23
& 4 & 26 & 14         \\
 3 & 0 & 1 & 0 & 3 & 1 & 3 & 0 & 3 & 3 & 1 & 9 & 9 & 5 & 5 & 3 & 5 & 16 & 9 & 0 & 3 & 0 & 3 & 21 & 9 & 7 & 19 & 9 & 1 & 9 & 27 & 10 & 31 & 24 & 11
& 34 & 27       \\
 4 & 0 & 0 & 1 & 2 & 1 & 4 & 0 & 4 & 1 & 0 & 4 & 4 & 2 & 2 & 1 & 10 & 13 & 10 & 7 & 6 & 19 & 8 & 6 & 16 & 0 & 4 & 1 & 10 & 6 & 10 & 2 & 16 & 1 &
10 & 29 & 34        \\
 5 & 0 & 1 & 2 & 1 & 1 & 5 & 0 & 5 & 8 & 3 & 1 & 11 & 6 & 13 & 8 & 5 & 1 & 11 & 14 & 9 & 17 & 19 & 4 & 5 & 10 & 13 & 2 & 17 & 20 & 5 & 4 & 29 & 14
& 21 & 26 & 17        \\
 6 & 0 & 0 & 0 & 2 & 3 & 0 & 6 & 2 & 0 & 6 & 9 & 0 & 6 & 0 & 6 & 10 & 15 & 6 & 4 & 10 & 3 & 2 & 18 & 18 & 14 & 12 & 24 & 10 & 8 & 24 & 26 & 2 & 18
& 12 & 8 & 18        \\
 7 & 0 & 1 & 1 & 1 & 3 & 1 & 6 & 3 & 7 & 9 & 6 & 7 & 10 & 11 & 13 & 5 & 3 & 7 & 11 & 13 & 1 & 13 & 16 & 7 & 24 & 21 & 25 & 17 & 22 & 19 & 28 & 15
& 31 & 23 & 5 & 1        \\
 8 & 0 & 0 & 2 & 0 & 3 & 2 & 6 & 4 & 5 & 8 & 1 & 2 & 7 & 8 & 11 & 10 & 0 & 8 & 18 & 16 & 20 & 18 & 1 & 14 & 17 & 6 & 17 & 26 & 19 & 2 & 20 & 0 &
8 & 22 & 0 & 8        \\
 9 & 0 & 1 & 0 & 1 & 0 & 3 & 6 & 5 & 3 & 7 & 7 & 3 & 1 & 1 & 0 & 9 & 12 & 9 & 6 & 5 & 18 & 7 & 5 & 15 & 24 & 23 & 12 & 25 & 14 & 3 & 27 & 11 & 9
& 29 & 8 & 21        \\
 10 & 0 & 0 & 1 & 0 & 0 & 4 & 6 & 6 & 1 & 6 & 2 & 10 & 5 & 12 & 7 & 4 & 0 & 10 & 13 & 8 & 16 & 18 & 3 & 4 & 9 & 12 & 1 & 16 & 19 & 4 & 3 & 28 & 13
& 20 & 25 & 16        \\
 11 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 &
30 & 31 & 32 & 33 & 34 & 35        \\
 12 & 0 & 0 & 0 & 0 & 2 & 0 & 5 & 2 & 6 & 8 & 5 & 6 & 9 & 10 & 12 & 4 & 2 & 6 & 10 & 12 & 0 & 12 & 15 & 6 & 23 & 20 & 24 & 16 & 21 & 18 & 27 & 14
& 30 & 22 & 4 & 0        \\
 13 & 0 & 1 & 1 & 3 & 1 & 1 & 5 & 3 & 4 & 7 & 0 & 1 & 6 & 7 & 10 & 9 & 16 & 1 & 0 & 13 & 7 & 11 & 10 & 1 & 19 & 23 & 16 & 25 & 18 & 1 & 19 & 31 &
1 & 19 & 22 & 1        \\
 14 & 0 & 0 & 2 & 2 & 1 & 2 & 5 & 4 & 2 & 6 & 6 & 2 & 0 & 0 & 14 & 2 & 9 & 14 & 3 & 12 & 2 & 4 & 15 & 8 & 12 & 8 & 8 & 6 & 21 & 20 & 10 & 10 & 8
& 28 & 7 & 20        \\
 15 & 0 & 1 & 0 & 3 & 3 & 3 & 5 & 5 & 0 & 5 & 1 & 9 & 4 & 11 & 6 & 3 & 16 & 3 & 14 & 19 & 3 & 11 & 12 & 15 & 5 & 19 & 21 & 1 & 21 & 21 & 17 & 21
& 9 & 1 & 21 & 33        \\
 16 & 0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 &
29 & 30 & 31 & 32 & 33 & 34        \\
 17 & 0 & 1 & 2 & 1 & 3 & 5 & 5 & 7 & 5 & 7 & 4 & 5 & 8 & 9 & 11 & 3 & 1 & 5 & 9 & 11 & 20 & 5 & 1 & 23 & 5 & 21 & 8 & 9 & 13 & 5 & 16 & 17 & 20
& 1 & 23 & 11        \\
 18 & 0 & 0 & 0 & 2 & 0 & 0 & 4 & 2 & 3 & 6 & 10 & 6 & 2 & 2 & 0 & 2 & 13 & 6 & 16 & 14 & 18 & 16 & 22 & 6 & 4 & 16 & 6 & 26 & 0 & 18 & 2 & 30 &
0 & 18 & 21 & 0        \\
 19 & 0 & 1 & 1 & 1 & 0 & 1 & 4 & 3 & 1 & 5 & 5 & 1 & 12 & 7 & 1 & 9 & 5 & 13 & 2 & 11 & 1 & 3 & 14 & 7 & 11 & 7 & 7 & 5 & 20 & 19 & 9 & 9 & 7 &
27 & 6 & 19        \\
 20 & 0 & 0 & 2 & 0 & 0 & 2 & 4 & 4 & 8 & 8 & 2 & 8 & 3 & 10 & 5 & 2 & 15 & 2 & 13 & 18 & 2 & 10 & 11 & 14 & 4 & 18 & 20 & 0 & 20 & 20 & 16 & 20
& 8 & 0 & 20 & 32        \\
 21 & 0 & 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28
& 29 & 30 & 31 & 32 & 33        \\
 22 & 0 & 0 & 1 & 0 & 2 & 4 & 4 & 6 & 4 & 6 & 3 & 4 & 7 & 8 & 10 & 2 & 0 & 4 & 8 & 10 & 19 & 4 & 0 & 22 & 4 & 20 & 7 & 8 & 12 & 4 & 15 & 16 & 19
& 0 & 22 & 10        \\
 23 & 0 & 1 & 2 & 3 & 1 & 5 & 4 & 7 & 2 & 5 & 9 & 5 & 1 & 1 & 14 & 11 & 4 & 11 & 13 & 1 & 8 & 5 & 7 & 17 & 0 & 23 & 26 & 11 & 2 & 5 & 22 & 27 & 20
& 7 & 30 & 23        \\
 24 & 0 & 0 & 0 & 0 & 4 & 0 & 3 & 2 & 0 & 4 & 4 & 0 & 11 & 6 & 0 & 8 & 4 & 12 & 1 & 10 & 0 & 2 & 13 & 6 & 10 & 6 & 6 & 4 & 19 & 18 & 8 & 8 & 6 &
26 & 5 & 18        \\
 25 & 0 & 1 & 1 & 3 & 3 & 1 & 3 & 3 & 7 & 7 & 1 & 7 & 2 & 9 & 4 & 1 & 14 & 1 & 12 & 17 & 1 & 9 & 10 & 13 & 3 & 17 & 19 & 27 & 13 & 13 & 10 & 21 &
19 & 3 & 8 & 1        
\end{array}\]
\caption*{$RA_{6}$: $z_{n}= 6z_{n-1}+c \mod n$, $c = 0,1,\ldots25$. Leftmost column gives $c$.}
\end{center}
\end{sidewaysfigure}
 
% \clearpage

The entry in row $c$ and  column $n$ of $RA_b$ will be denoted by $z_{b,c,n}$. So $z_{b,c,0}=0$ for all $b,c$.
For $n\geq 1$, compute 
\[
z_{b,c,n}\equiv b z_{b,c,n-1} +c\pmod n,
\]
taking the least nonnegative residue modulo $n$,
so that  
\[
b z_{b,c,n-1} +c = n q_n + z_{b,c,n},
\]
where 
\[
q_n=\lfloor (b z_{b,c,n} + c)/ n\rfloor.
\] 
The rows of $RA_b$ are rumor (running modulus recursion) sequences as described in Dearden and Metzger  \cite{dm}. 

Rumor sequences appear to be related, at least tangentially, to a number of familiar mathematical topics. For example, 
as pointed out by Borwein and Loring \cite{bl}, conjectures concerning rumor sequences are reminiscent of the Collatz  $3x+1$ Conjecture.  In Dearden and Metzger \cite{dm},  certain rumor sequences are shown to be related to a variation of the Josephus problem as presented in Graham, Knuth, and Patashnik \cite[p.\ 8] {gkp}.  Finally,  Dearden, Iiams, and Metzger  \cite{dim} contrast  the behavior of certain functions related to rumor sequences 
with properties of the Takagi function. 

Studying extended versions of tables $RA_2$ and $RA_6$, and similar tables for other values $b$ immediately suggests a number of simple sounding conjectures. First, the columns are periodic, though the minimal period is not completely obvious, and second, within each period of column $n$, the values $0,1,2,\ldots,n-1$ appear to follow no recognizable pattern, but are nevertheless equidistibuted. Empirical evidence supports these conjectures, but complete proofs have turned out to be elusive. 

In this paper we prove several theorems related to these two conjectures. In particular, in the next section we show that columns of $RA_{b}$ are periodic, and in a few simple cases, we will determine the minimal period of some columns.

A Mathematica {.}cdf (Computable Document Format) application,  RumorArray.cdf \cite{ra}, is available for experimentation. With the free CDF Player available from Wolfram's Mathematica site at (\url{http://www.wolfram.com/cdf-player}), RumorArray.cdf can be used to quickly generate rumor arrays with parameter values $1\leq b,c,n \leq 100$. 



\section{Columns are periodic}

For integers $k$,  $1\leq k \leq n$, the value of $\lcm( k,k+1,\ldots,n)$, the least common multiple of the integers $k, k+1, \dots, ,n$,  will occur frequently. The shorthand symbol ${}_kL_n$ will be used to denote that value.

In this section we give the easy proof that that columns of $RA_b$ are periodic.   Empirical evidence suggests that the full truth about the columns is given in the following conjecture.

\begin{conjecture}
\label{periodconj}
The minimal period of the $n$th column in $RA_b$  is ${}_kL_n$, where $k$ is the largest divisor of $b$ not exceeding $n$.
\end{conjecture}


For any $b$ and large enough $n$, clearly the period ${}_kL_n$ of the periodicity conjecture will
equal ${}_1L_n$, so, if the conjecture is true, then  the period given in the next theorem 
will be the minimal period of the $n$th column for all sufficiently large $n$.  It is not hard to 
show that for a given $k \geq 3$, the least value of $n\geq k$ such that ${}_kL_n ={}_1L_n$
is  two times the largest prime power less than $k$, or, in other words, two times the values 
of the sequence  \seqnum{A031218} of OEIS. 
\begin{theorem}
For each integer $b\geq 2$ the $n$th column of $RA_b$ is periodic with period ${}_1L_n$.
\end{theorem}

\begin{proof}
The column for $n=1$ is identically $0$, and so it is $1${-}periodic.  
Suppose the $(n-1)$st column is  ${}_1L_{n-1}$ periodic. Since ${}_1L_{n-1}$ divides ${}_1L_{n}$, the $(n-1)$st 
column is $t ={}_1L_{n}$ periodic. So, for any integer $c\geq 0$,   
\[
z_{b,c+t,n}\equiv  b z_{b,c+t,n-1}+(c+t) \equiv b z_{b,c,n-1} + c \equiv  z_{b,c,n} \pmod{n}.
\]
Consequently $z_{b,c+t,n} = z_{b,c,n}$.
\end{proof}

Such a  simple inductive proof of Conjecture \ref{periodconj} does not seem likely since the minimal periods of the columns
do not always increase as we move across the array. For example, with $b = 6$, column $n=5$ has minimal period $60$ while column $6$ has period $6$.



In the next two theorems, a few special cases are considered where the column entries follow a particularly simple pattern and the minimal period of the column can be easily  determined.



\begin{theorem}
\label{divb1}
If $n$ divides $b$, then the $n$th column of $RA_{b}$ has minimal period $n$. One complete period
has the form
$0,1,2,\ldots n-1$.
\end{theorem}

\begin{proof} If $n$ divides $b$, then the recursive formula reduces to 
$z_{b,n,c}\equiv bz_{b,c,n-1}+c \equiv c \pmod n$. As $c$ takes  on the values $0,1,2,\ldots$ in order, the
residues modulo $n$ repeat the pattern $0,1,2,\ldots,n-1$. 
\end{proof}




\begin{theorem}
\label{divb2}
If $b = (n-1)(mn+1)$ for integers $m\geq 1$ and $n\geq 2$, then $n$th column of $RA_{b}$ has minimal period $n(n-1)$. One complete period has the form 
\[
0,0,\ldots,0,n-1,n-1,\ldots,n-1,n-2,n-2,\ldots,n-2,\ldots,1,1,\ldots,1]
\]           
where each value occurs $n-1$ times.
\end{theorem}

\begin{proof}
Suppose $b$ has the form $(n-1)(mn+1)$ for some integers $m\geq 1$ and $n\geq 2$. Since $n-1$ divides $b$, the $(n-1)$st column of $RA_{b}$ is $0,1,2,\ldots,n-2,0,1,\ldots,n-2,\ldots$.  For  $0\leq c < n(n-1)$, write $c = r + q(n-1)$ with $0\leq r <n-1$ so that $z_{b,c,n-1} = r$. As $c$ ranges from $0$ to 
$n(n-1)-1$, the 
quotients, $q$, will form the sequence $$0,0,\ldots 0,1,1,\ldots,1,2,2,\ldots,2,\ldots,n-1,n-1,\ldots,n-1.$$
So
\begin{eqnarray*}
z_{b,c,n}  &\equiv &  b z_{b,c,n-1}+c\pmod n  \\
               &\equiv & (n-1)(mn+1) r +c \pmod n \\
               &\equiv &  (n-1)(mn+1)(c-q(n-1))+c\pmod n  \\
               &\equiv &  -(c+q)+c \pmod n  \\
               &\equiv &  -q \pmod n \\
\end{eqnarray*}
That shows $z_{b,c,n}= 0$ if $q=0$, and $z_{b,c,n}= n-q$ otherwise, giving the promised period.
\end{proof}


For example, $b = 8855$ has the form $(n-1)(mn+1)$ for six values of $n$: 

\begin{align*}
8855 & = (2-1)(4427 \times 2+1)\\
8855 &= (6-1)(295 \times 6+1)\\
8855 &= (8-1)(158 \times 8+1)\\
8855 &= (12-1)(67 \times 12+1)\\
8855 &= (24-1)(16 \times 24+1)\\
8855 &= (36-1)(7 \times 36+1).\\
\end{align*}
\vskip -10pt

So the theorem above completely describes columns $2,6,8,12,24$, and $36$ of $RA_{8855}$. 

For a given $b$,
 the number of columns of $RA_{b}$ described by this theorem is the number of factorizations of $b$ as $de$ with $d<e$ and $d+1$ dividing $e-1$. 

\section{Equidistribution of columns}

Extensive empirical evidence, using tables such as $RA_{2}$ and $RA_{6}$ included here, suggests that for any $b\geq 1$,  within 
one period of column $n$, the values $0,1,\dots,n-1$ each occur the same number of times.  This observation can be 
rendered as follows.

Consider the group $G = {\mathbb Z}_{1}\times {\mathbb Z}_{2}\times \cdots \times{\mathbb Z}_{n}$, where
${\mathbb Z}_{m}$ denotes the additive group of integers modulo $m$. Fix an integer $b\geq 1$. Define a bijection $s_{b}:G\to G$ by
$s_{b}(a_{0},a_{1},\ldots,a_{n}) = (z_{0},z_{1},\ldots,z_{n})$ where $z_{0}= a_{0}$, and, assuming $z_{0},z_{1},\ldots,z_{j-1}$
have been computed, $z_{j}\equiv bz_{j-1}+a_{j} \pmod j$. The function $s_{b}$ is a generalized version of the rule for generating a rumor sequence.
For each integer $k$, let $e(k) = (k\mod 1, k \mod 2, \ldots, k\mod n)\in G$, and let $K$ be the subgroup 
$\{ e(k) \, | \, 0\leq k < {}_{1}L_{n} \}$ of $G$. 

The observation that the columns of any rumor array are equidistributed within a period is equivalent to the following conjecture.

 \begin{conjecture}
For each $k=1,2,\ldots,n$, the entries, $0,1,\ldots,k-1$, in the $k^{th}$ coordinate of the $n${-}tuples in $s_{b}[K]$ are equidistributed.
\end{conjecture}


\section{Calculating column entries} 

The $n$th column of $RA_{b}$ is periodic with (not necessarily minimal) period $ m = {}_1L_n$. That means the $n$th column satisfies  the order $m$ recurrence $z_{b,c,n} = z_{b,c+m,n}$ for $c\geq 0$.  
The characteristic polynomial of this recurrence formula is $\chi(x)=x^m-1$. The polynomial $\chi(x)$ has $m$ distinct roots, namely the $m$th roots of unity, $\{\xi^j |j=0,1,2,\ldots,m-1\}$, where $\xi=e^{2\pi i/ m}$. 
It follows that, for some coefficients $a_0,a_1,\ldots,a_{m-1}$ (which will depend on $b$ in general),
$$z_{b,c,n}=\sum_{j=0}^{m-1} a_j (\xi^j)^c.$$ 


While there does not seem to be general formulas giving the coefficient $a_{0},a_{1},\ldots,a_{m-1}$, it is easy to determine the coefficients for  any particular column. Write $A = [a_{0},a_{1},\ldots,a_{m-1}]$ for the row
vector of unknown coefficients, and $Z = [z_{b,0,n},z_{b,1,n},\ldots,z_{b,m-1,n}]$ for the initial $m$ entries in column $n$. Let $M$ denote the $m\times m$ matrix with $j,k$th entry $\xi^{(j-1)(k-1)}$, for $j,k = 1,2,\dots ,m$. To compute the $A$ vector, the matrix equation  to solve is $AM=Z$. Using the familiar fact that $M^{-1} = \frac{1}{m} {\overline M}$, where ${\overline M}$ denotes the complex conjugate of $M$, it follows that $A = \frac{1}{m}Z{\overline M}$.


As might be expected, carrying out this procedure for a number of specific values of $b$ and $n$ suggests that the list of coefficients $a_{0},a_{1},\ldots,a_{m-1}$  shows a lot of internal structure. 
Consider, for example,  the case $b=2$ and $n=4$. Column $4$ has period $12 ={}_{1}L_{4}$, which happens to be the minimal period for this column.
Computing the coefficients $a_{0},a_{1},\ldots,a_{11}$ as described above gives

\vskip 8pt

\begin{tabular}{l l l}
 $a_{0} = \frac{3}{2}$          & \quad    $a_{1} = -\frac{1}{6}(1+i)(1+\sqrt{3})$  & \quad   $a_{2}= 0$\\[+5pt]
 
 $a_{3} = -\frac{1}{6}(1-i)$ & \quad     $a_{4} = 0$                                           & \quad   $a_{5}= -\frac{1}{6}(1+i)(1-\sqrt{3})$\\[+5pt]
 
 $a_{6}= -\frac{1}{2}$         & \quad     $a_{7}= -\frac{1}{6}(1-i)(1-\sqrt{3})$    & \quad   $a_{8} = 0$\\[+5pt]
 
 $a_{9}=-\frac{1}{6}(1+i)$  & \quad     $a_{10}=  0$                                         & \quad   $a_{11} = -\frac{1}{6}(1-i)(1+\sqrt{3})$.\\
 
\end{tabular} 

\vskip 8pt


For some values of $b$, the coefficients $a_{0}, a_{1},\ldots,a_{m-1}$ are easy to calculate. For example, for any $b$ column $2$  is $2${-}periodic: $(0,1,0,1,\ldots)$. So $z_{b,c,2}$ can be written as $z_{b,c,2}=\frac{1}{2}(1)^{c}-\frac{1}{2}(-1)^c$ for $c\geq 0$. 

We will now calculate  the coefficients $a_{0}, a_{1},\ldots,a_{m-1}$
 for the particularly simple columns determined in theorems \ref{divb1} and \ref{divb2}.
 
When $n$ divides $b$, the $n$th column is $n$ periodic with initial terms $0,1,2,\ldots,n-1$.   
In this case $z_{b,c,n}=z_{b,c+n,n}$ for all $c\geq 0$. The characteristic polynomial for the recursive relation is therefore 
$\chi(x)=x^n-1$. Consequently, in this case, for all $c\geq 0$, the expression for $z_{b,c,n}$ has the form
\[
z_{b,c,n}=\sum_{j=0}^{n-1} a_{j} (\xi^j)^c = \sum_{j=0}^{n-1} a_{j} \xi^{jc}
\]
where $\xi=e^{2\pi i/ n}$. 

In the following proof, we will use the familiar identity: for $x\not= 1$,

\[
\sum_{k=0}^{n-1} kx^{k}= \frac{(x-1)nx^n-x(x^n-1)}{(x-1)^{2}}.
\]


\begin{theorem}
If $n$ divides $b$ and $\xi = e^{\frac{2\pi i}{n}}$, then 
\[
\displaystyle z_{b,c,n} = \frac{n-1}{2} +  \sum_{j=1}^{n-1}\left(\frac{1}{\overline{\xi}^{\,j}-1}\right)\xi^{{jc}} = 
\frac{n-1}{2} +  \sum_{j=1}^{n-1}\left(\frac{\xi^{j}}{1-\xi^{j}}\right)\xi^{{jc}}.
\]


\end{theorem}
\begin{proof}

Since $n$ divides $b$, the $n$th column of $RA_{b}$ is $0,1,\ldots,n-1$.  Let $\displaystyle \xi = e^{\frac{2\pi i}{n}}$, a primitive $n$th root of unity. To determine the coefficients $a_{0},a_{1},\ldots,a_{n-1}$
so that
\[
z_{b,c,n}=\sum_{j=0}^{m-1} a_j (\xi^j)^c
\] 
we need to solve 
\[
[a_{0},a_{1},\ldots, a_{n-1}] M = [0,1,2,\ldots,n-1],
\]
where $M$ is the $n\times n$ matrix with $i,j$ entry $\xi^{(i-1)(j-1)}$.  Since $M^{-1} = \frac{1}{n} \overline{M}$, where $\overline{M}$ is the complex conjugate of $M$, we see
\[
[a_{0},a_{1},\ldots, a_{n-1}]  = \frac{1}{n} [0,1,2,\ldots,n-1] \overline{M}.
\]
So $\displaystyle a_{0} = \frac{1}{n}(0+1+\cdots+(n-1))= \frac{n-1}{2}$, and for $j=1,\dots,n-1$,
\[
a_{j} = \frac{1}{n} \sum_{k=0}^{n-1}k(\overline{\xi}^{\,j})^{k} = 
 \frac{(\overline{\xi}^{\,j} -1)n\overline{\xi}^{\,jn} - \overline{\xi}^{\,j}(\overline{\xi}^{\,jn} -1)}{n(\overline{\xi}^{\,j}-1)^{2}} 
= \frac{1}{\overline{\xi}^{\,j} - 1}.
\]

\end{proof}

\begin{theorem}
If $b=(n-1)(mn+1)$ for integers $m\geq 1$ and $n\geq 2$, and  $\xi = e^\frac{2\pi i}{n(n-1)}$ is a primitive $n(n-1)$th root of unity, then  
\[
z_{b,c,n}=\frac{n-1}{2} + {\sum_{j=1}^{n(n-1)-1} a_{j} (\xi^j)^c},
\]
 where $\displaystyle a_j = 0$ if $n$ divides $j$, and $\displaystyle a_j =\frac{\xi^{j}}{(n-1)\xi^{j(n-1)}(\xi^{j}-1)}$ otherwise.
\end{theorem}

\begin{proof}
Suppose $b = (n-1)(mn+1)$ for some integers $m\geq 1$ and $n\geq 2$, and  let $\xi$ be the primitive $n(n-1)$th root of 
unity $e^\frac{2\pi i}{n(n-1)}$  .
Following the pattern of proof of the previous theorem, we see
\[
[a_0,a_1,\ldots,a_{n(n-1)-1}] = \frac{1}{n(n-1)}[0,0,\ldots,0,n-1,n-1,\ldots,n-1,\ldots\ldots,1,1,\ldots,1]\overline{M}
\]
where $M$ is the $n(n-1) \times n(n-1)$ matrix with $i,j$th entry $\xi^{(i-1)(j-1)}$.


For $0\leq j <n(n-1)$ we see
\[
a_j = \frac{1}{n(n-1)}\sum_{k=1}^{n-1} (n-k)\left(\sum_{m=0}^{n-2}(\overline{\xi}^{\,j})^{k(n-1)+m}\right)
= \frac{1}{n(n-1)}\left(\sum_{k=1}^{n-1} (n-k)\overline{\xi}^{\,jk(n-1)}\right)\left(\sum_{m=0}^{n-2}\overline{\xi}^{\,jm}\right).
\]

So $\displaystyle a_0 = \frac{1}{n(n-1)}((n-1)(n-1)+(n-1)(n-2)+\cdots+(n-1)1) = \frac{n-1}{2}.$

If $j>0$ and $\xi^{j(n-1)} = 1$, in other words, if $n$ divides $j$, then $\displaystyle \sum_{m=0}^{n-2}\overline{\xi}^{\,jm}
= \frac{\overline{\xi}^{\,j(n-1)}-1}{\overline{\xi}^{\,j} - 1} = 0$, so $a_j = 0$ in these cases.

For all other values of $j$, $0<j<n(n-1)$, the expression for $a_{j}$ simplifies to 
\[
 a_j =  \frac{\overline{\xi}^{\,j(n-1)}}{(n-1)(1-\overline{\xi}^{\,j})} = \frac{\xi^{j}}{(n-1)\xi^{j(n-1)}(\xi^{j}-1)}.
\]
\end{proof}

Since the $a_{j}$ of the last theorem are $0$ when $n$ divides $j>0$, the $n(n-1)$th column actually satisfies a linear recurrence relation with characteristic polynomial $\displaystyle \chi(x) = \frac{(x-1)(x^{n(n-1)}-1)}{x^{n-1} -1}$.

\section {Acknowledgements} The authors wish to thank the
referees for their thoughtful comments.


\begin{thebibliography}{9}

\bibitem{bl} P. B.~Borwein and T. A.~Loring, Some questions of
Erd\H{o}s and Graham on numbers of the form $\sum g_{n}/2^{g_{n}}$,
{\em Math. Comp.} \textbf{54} (1990), 377--394.

\bibitem{dm} B.~Dearden and J.~Metzger, Running modulus recursions,
{\em J. Integer Seq.} \textbf{13} (2010),
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL13/Dearden/dearden3.html}{Article 10.1.6}.

\bibitem{dim} B.~Dearden, J.~Iiams, and J.~Metzger, A function related
to the rumor sequence conjecture, {\em J. Integer Seq.} \textbf{14}
(2011), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL13/Dearden/dearden3.html}{Article 11.2.3}.

\bibitem{ra} B. Dearden, J. Iiams, and  J. Metzger,
{\tt RumorArray.cdf}, Mathematica CDF application, 2013, available at 
\newline
\url{https://cs.uwaterloo.ca/journals/JIS/VOL16/Dearden/RumorArray.cdf}.

\bibitem{er} P.~Erd\H{o}s, Some problems and results on the
irrationality of the sum of infinite series, {\em J. Math. Sci.}
\textbf{10} (1975), 1--7.

\bibitem{erg} P.~ Erd\H{o}s and R. L.~Graham, {\it Old and New Results in
Combinatorial Number Theory}, Monograph No.\ 28, {\it L'Enseignement
Math\'ematique}, 1980.

\bibitem{gkp} 
R{.} Graham, D{.} Knuth, and O{.} Patashnik, {\it  Concrete
Mathematics}, 2nd edition, Addison-Wesley, 1994.


\bibitem{va} E.~Vantieghem, On sequences related to expansions of real
numbers, {\em Fibonacci Quart.} \textbf{34} (1996), 356--361.

\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: } recurrence sequence, recurrence relation
modulo $m$, rumor sequence, running modulus recursion.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A031218}, \seqnum{A177356}, and \seqnum{A208125}.)

\bigskip
\hrule
\bigskip


\vspace*{+.1in}
\noindent
Received March 29 2013;
revised version received  October 1 2013.
Published in {\it Journal of Integer Sequences}, October 13 2013.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                

 


.