Rumor Arrays

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

                 bruce.dearden@und.edu
                  joel.iiams@und.edu
                 jerry.metzger@und.edu

Abstract

Rumor sequences are generated recursively as follows: fix nonnegative integers b, c, and let z_{0} = 0. For n ≥ 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, … 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.

1 Introduction

Rumor sequences are generated recursively as follows: fix nonnegative integers b, c, and let z_{0} = 0. For n ≥ 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 [1, p. 379], where they investigate a question raised by Erdős [5] in 1975 and again by Erdős and Graham [6, p. 62] in 1980. It seems next to have appeared in Vantieghem [8] in 1996, and, most recently, in 2010, where Dearden and Metzger [2] coined the term 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, … are written down, one below the other, some interesting and unexpected patterns appear in the columns of that 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.

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 ≥ 1, compute

z_{b,c,n} ≡ bz_{b,c,n−1} + c (mod n),

taking the least nonnegative residue modulo n, so that

bz_{b,c,n−1} + c = nq_{n} + z_{b,c,n},

where

q_{n} = ⌊(bz_{b,c,n} + c)/n⌋.

The rows of RA_{b} are rumor (running modulus recursion) sequences as described in Dearden and Metzger [2].

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 [1], conjectures concerning rumor sequences are reminiscent of the Collatz 3x+1 Conjecture. In Dearden and Metzger [2], certain rumor sequences are shown to be related to a variation of the Josephus problem as presented in Graham, Knuth, and Patashnik [7, p. 8]. Finally, Dearden, Iiams, and Metzger [3] 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, …, 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.

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

RA_{2}: z_{n} = 2z_{n−1} + c mod n, c = 0, 1, … 25. Leftmost column gives c.

3

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

RA_{6}: z_{n} = 6z_{n−1} + c mod n, c = 0, 1, … 25. Leftmost column gives c.

4

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 [4], is available for experimentation. With the free CDF Player available from Wolfram’s Mathematica site at (http://www.wolfram.com/cdf-player), RumorArray.cdf can be used to quickly generate rumor arrays with parameter values 1 ≤ b, c, n ≤ 100.

2 Columns are periodic

For integers k, 1 ≤ k ≤ n, the value of lcm(k, k + 1, …, n), the least common multiple of the integers k, k + 1, …, , n, will occur frequently. The shorthand symbol _{k}L_{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.

Conjecture 1. The minimal period of the nth column in RA_{b} is _{k}L_{n}, where k is the largest divisor of b not exceeding n.

For any b and large enough n, clearly the period _{k}L_{n} of the periodicity conjecture will equal _{1}L_{n}, so, if the conjecture is true, then the period given in the next theorem will be the minimal period of the nth column for all sufficiently large n. It is not hard to show that for a given k ≥ 3, the least value of n ≥ k such that _{k}L_{n} = _{1}L_{n} is two times the largest prime power less than k, or, in other words, two times the values of the sequence \underline{A031218} of OEIS.

Theorem 2. For each integer b ≥ 2 the nth column of RA_{b} is periodic with period _{1}L_{n}.

Proof. The column for n = 1 is identically 0, and so it is 1-periodic. Suppose the (n − 1)st column is _{1}L_{n−1} periodic. Since _{1}L_{n−1} divides _{1}L_{n}, the (n − 1)st column is t = _{1}L_{n} periodic. So, for any integer c ≥ 0,

z_{b,c+t,n} ≡ bz_{b,c+t,n−1} + (c + t) ≡ bz_{b,c,n−1} + c ≡ z_{b,c,n} (mod n).

Consequently z_{b,c+t,n} = z_{b,c,n}.

Such a simple inductive proof of Conjecture 1 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.

Theorem 3. If n divides b, then the nth column of RA_{b} has minimal period n. One complete period has the form 0, 1, 2, … n − 1.

Proof. If n divides b, then the recursive formula reduces to z_{b,n,c} ≡ bz_{b,c,n−1} + c ≡ c (mod n). As c takes on the values 0, 1, 2, … in order, the residues modulo n repeat the pattern 0, 1, 2, …, n − 1.

Theorem 4. If b = (n − 1)(mn + 1) for integers m ≥ 1 and n ≥ 2, then nth column of RA_{b} has minimal period n(n − 1). One complete period has the form

0, 0, …, 0, n − 1, n − 1, …, n − 1, n − 2, n − 2, …, n − 2, …, 1, 1, …, 1]

where each value occurs n − 1 times.

Proof. Suppose b has the form (n − 1)(mn + 1) for some integers m ≥ 1 and n ≥ 2. Since n − 1 divides b, the (n − 1)st column of RA_{b} is 0, 1, 2, …, n − 2, 0, 1, …, n − 2, . . .. For 0 ≤ c < n(n − 1), write c = r + q(n − 1) with 0 ≤ 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, … 0, 1, 1, …, 1, 2, 2, …, 2, …, n − 1, n − 1, …, n − 1.

So

z_{b,c,n} ≡ bz_{b,c,n−1} + c (mod n)
≡ (n − 1)(mn + 1)r + c (mod n)
≡ (n − 1)(mn + 1)(c − q(n − 1)) + c (mod n)
≡ −(c + q) + c (mod n)
≡ −q (mod n)

That shows z_{b,c,n} = 0 if q = 0, and z_{b,c,n} = n − q otherwise, giving the promised period.

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

8855 = (2 − 1)(4427 × 2 + 1)
8855 = (6 − 1)(295 × 6 + 1)
8855 = (8 − 1)(158 × 8 + 1)
8855 = (12 − 1)(67 × 12 + 1)
8855 = (24 − 1)(16 × 24 + 1)
8855 = (36 − 1)(7 × 36 + 1).

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.

3 Equidistribution of columns

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

Consider the group G = ℤ_{1}×ℤ_{2}×⋯×ℤ_{n}, where ℤ_{m} denotes the additive group of integers modulo m. Fix an integer b ≥ 1. Define a bijection s_{b} : G → G by s_{b}(a_{0}, a_{1}, …, a_{n}) = (z_{0}, z_{1}, …, z_{n}) where z_{0} = a_{0}, and, assuming z_{0}, z_{1}, …, z_{j−1} have been computed, z_{j} ≡ bz_{j−1} + a_{j} (mod 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, …, k mod n) ∈ G, and let K be the subgroup {e(k) | 0 ≤ 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.

Conjecture 5. For each k = 1, 2, …, n, the entries, 0, 1, …, k − 1, in the k^{th} coordinate of the n-tuples in s_{b}[K] are equidistributed.

4 Calculating column entries

The nth column of RA_{b} is periodic with (not necessarily minimal) period m = _{1}L_{n}. That means the nth column satisfies the order m recurrence z_{b,c,n} = z_{b,c+m,n} for c ≥ 0. The characteristic polynomial of this recurrence formula is χ(x) = x^{m} − 1. The polynomial χ(x) has m distinct roots, namely the mth roots of unity, {ξ^{j}|j = 0, 1, 2, …, m − 1}, where ξ = e^{2πi/m}. It follows that, for some coefficients a_{0}, a_{1}, …, a_{m−1} (which will depend on b in general),

z_{b,c,n} = ∑_{j=0}^{m−1} a_{j}(ξ^{j})^{c}.

While there does not seem to be general formulas giving the coefficient a_{0}, a_{1}, …, a_{m−1}, it is easy to determine the coefficients for any particular column. Write A = [a_{0}, a_{1}, …, a_{m−1}] for the row vector of unknown coefficients, and Z = [z_{b,0,n}, z_{b,1,n}, …, z_{b,m−1,n}] for the initial m entries in column n. Let M denote the m × m matrix with j, kth entry ξ^{(j−1)(k−1)}, for j, k = 1, 2, …, 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}, …, 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}, …, a_{11} as described above gives

\begin{matrix}a_{0} = \frac{3}{2} & a_{1} = −\frac{1}{6}(1 + i)(1 + \sqrt{3}) & a_{2} = 0 \\ a_{3} = −\frac{1}{6}(1 − i) & a_{4} = 0 & a_{5} = −\frac{1}{6}(1 + i)(1 − \sqrt{3}) \\ a_{6} = −\frac{1}{2} & a_{7} = −\frac{1}{6}(1 − i)(1 − \sqrt{3}) & a_{8} = 0 \\ a_{9} = −\frac{1}{6}(1 + i) & a_{10} = 0 & a_{11} = −\frac{1}{6}(1 − i)(1 + \sqrt{3}). \end{matrix}

For some values of b, the coefficients a_{0}, a_{1}, …, a_{m−1} are easy to calculate. For example, for any b column 2 is 2-periodic: (0, 1, 0, 1, …). 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 ≥ 0.

We will now calculate the coefficients a_{0}, a_{1}, …, a_{m−1} for the particularly simple columns determined in theorems 3 and 4.

When n divides b, the nth column is n periodic with initial terms 0, 1, 2, …, n−1. In this case z_{b,c,n} = z_{b,c+n,n} for all c ≥ 0. The characteristic polynomial for the recursive relation is therefore χ(x) = x^{n} − 1. Consequently, in this case, for all c ≥ 0, the expression for z_{b,c,n} has the form

z_{b,c,n} = ∑_{j=0}^{n−1} a_{j}(ξ^{j})^{c} = ∑_{j=0}^{n−1} a_{j}ξ^{jc}

where ξ = e^{2πi/n}.

In the following proof, we will use the familiar identity: for x ≠ 1,

∑_{k=0}^{n−1} kx^{k} = \frac{(x − 1)nx^{n} − x(x^{n} − 1)}{(x − 1)^{2}}.

Theorem 6. If n divides b and ξ = e^{\frac{2πi}{n}}, then

z_{b,c,n} = \frac{n − 1}{2} + ∑_{j=1}^{n−1} (\frac{1}{\overline{ξ}^{j} − 1}) ξ^{jc} = \frac{n − 1}{2} + ∑_{j=1}^{n−1} (\frac{ξ^{j}}{1 − ξ^{j}} ) ξ^{jc}.

Proof. Since n divides b, the nth column of RA_{b} is 0, 1, …, n − 1. Let ξ = e^{\frac{2πi}{n}}, a primitive nth root of unity. To determine the coefficients a_{0}, a_{1}, …, a_{n−1} so that

z_{b,c,n} = ∑_{j=0}^{m−1} a_{j}(ξ^{j})^{c}

we need to solve

[a_{0}, a_{1}, …, a_{n−1}]M = [0, 1, 2, …, n − 1],

where M is the n × n matrix with i, j entry ξ^{(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}, …, a_{n−1}] = \frac{1}{n}[0, 1, 2, …, n − 1]\overline{M}.

So a_{0} = \frac{1}{n}(0 + 1 + ⋯ + (n − 1)) = \frac{n − 1}{2}, and for j = 1, …, n − 1,

a_{j} = \frac{1}{n} ∑_{k=0}^{n−1} k(\overline{ξ}^{j})^{k} = \frac{(\overline{ξ}^{j} − 1)n\overline{ξ}^{jn} − \overline{ξ}^{j}(\overline{ξ}^{jn} − 1)}{n(\overline{ξ}^{j} − 1)^{2}} = \frac{1}{\overline{ξ}^{j} − 1}.

Theorem 7. If b = (n − 1)(mn + 1) for integers m ≥ 1 and n ≥ 2, and ξ = e^{\frac{2πi}{n(n−1)}} is a primitive n(n − 1)th root of unity, then

z_{b,c,n} = \frac{n − 1}{2} + ∑_{j=1}^{n(n−1)−1} a_{j}(ξ^{j})^{c},

where a_{j} = 0 if n divides j, and a_{j} = \frac{ξ^{j}}{(n − 1)ξ^{j(n−1)}(ξ^{j} − 1)} otherwise.

Proof. Suppose b = (n − 1)(mn + 1) for some integers m ≥ 1 and n ≥ 2, and let ξ be the primitive n(n − 1)th root of unity e^{\frac{2πi}{n(n−1)}} . Following the pattern of proof of the previous theorem, we see

[a_{0}, a_{1}, …, a_{n(n−1)−1}] = \frac{1}{n(n − 1)}[0, 0, …, 0, n − 1, n − 1, …, n − 1, . . . . . . , 1, 1, …, 1]\overline{M}

where M is the n(n − 1) × n(n − 1) matrix with i, jth entry ξ^{(i−1)(j−1)}.

For 0 ≤ j < n(n − 1) we see

a_{j} = \frac{1}{n(n − 1)} ∑_{k=1}^{n−1}(n−k) (∑_{m=0}^{n−2}(\overline{ξ}^{j})^{k(n−1)+m}) = \frac{1}{n(n − 1)} (∑_{k=1}^{n−1}(n − k)\overline{ξ}^{jk(n−1)}) (∑_{m=0}^{n−2} \overline{ξ}^{jm}) .

So a_{0} = \frac{1}{n(n − 1)}((n − 1)(n − 1) + (n − 1)(n − 2) + ⋯ + (n − 1)1) = \frac{n − 1}{2}.

If j > 0 and ξ^{j(n−1)} = 1, in other words, if n divides j, then ∑_{m=0}^{n−2} \overline{ξ}^{jm} = \frac{\overline{ξ}^{j(n−1)} − 1}{\overline{ξ}^{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{ξ}^{j(n−1)}}{(n − 1)(1 − \overline{ξ}^{j})} = \frac{ξ^{j}}{(n − 1)ξ^{j(n−1)}(ξ^{j} − 1)}.

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 χ(x) =

\frac{(x − 1)(x^{n(n−1)} − 1)}{x^{n−1} − 1}.

5 Acknowledgements

The authors wish to thank the referees for their thoughtful comments.

References

[1] P. B. Borwein and T. A. Loring, Some questions of Erdős and Graham on numbers of the form ∑ g_{n}/2^{g_{n}}, Math. Comp. 54 (1990), 377–394.

[2] B. Dearden and J. Metzger, Running modulus recursions, J. Integer Seq. 13 (2010), Article 10.1.6.

[3] B. Dearden, J. Iiams, and J. Metzger, A function related to the rumor sequence conjecture, J. Integer Seq. 14 (2011), Article 11.2.3.

[4] B. Dearden, J. Iiams, and J. Metzger, RumorArray.cdf, Mathematica CDF application, 2013, available at

   https://cs.uwaterloo.ca/journals/JIS/VOL16/Dearden/RumorArray.cdf.

[5] P. Erdős, Some problems and results on the irrationality of the sum of infinite series, J. Math. Sci. 10 (1975), 1–7.

[6] P. Erdős and R. L. Graham, Old and New Results in Combinatorial Number Theory, Monograph No. 28, L’Enseignement Mathématique, 1980.

[7] R. Graham, D. Knuth, and O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.

[8] E. Vantieghem, On sequences related to expansions of real numbers, Fibonacci Quart. 34 (1996), 356–361.

2000 Mathematics Subject Classification: Primary 11B37; Secondary 11A50. Keywords: recurrence sequence, recurrence relation modulo m, rumor sequence, running modulus recursion.

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

Received March 29 2013; revised version received October 1 2013. Published in Journal of Integer Sequences, October 13 2013.

Return to Journal of Integer Sequences home page.