A Function Related to the Rumor Sequence Conjecture

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

For an integer b ≥ 2 and for x ∈ [0, 1), define ρ_{b}(x) = ∑_{n=0}^{∞} \frac{\{\{b^{n}x\}\}}{b^{n}}, where \{\{t\}\} denotes the fractional part of the real number t. A number of properties of ρ_{b} are derived, and then a connection between ρ_{b} and the rumor conjecture is established. To form a rumor sequence {z_{n}}, first select integers b ≥ 2 and k ≥ 1. Then select an integer z_{0}, and for n ≥ 1 let z_{n} = bz_{n−1} mod (n + k), where the right side is the least non-negative residue of bz_{n−1} modulo n + k. The rumor sequence conjecture asserts that all such rumor sequences are eventually 0. A condition on ρ_{b} is shown to be equivalent to the rumor conjecture.

1 Introduction

In this note, b ≥ 2 is a fixed integer. For x ∈ [0, 1), define ρ_{b}(x) = ∑_{n=0}^{∞} \frac{\{\{b^{n}x\}\}}{b^{n}}, where \{\{t\}\} denotes the fractional part of the real number t.

A b-adic rational is a rational which can be written as a quotient of an integer and a non-negative power of b. When a b-adic is written in the form \frac{a}{b^{m}}, and m > 0, it will be assumed b does not divide a.

The ρ_{b} function is similar to the well known Takagi function τ(x) defined by τ(x) = ∑_{n=0}^{∞} \frac{< <2^{n}x> >}{2^{n}}, where < <t> > is the distance from t to the nearest integer. Whereas the summand of the Takagi function is a triangle wave, the summand of ρ_{b}(x) is a sawtooth wave. (See Figures 1, 2.) The function y = < <2^{n}x> > is continuous and periodic with period 2^{−n}, and it follows that τ is continuous. It turns out τ (see Figure 3) is also nowhere differentiable.

Figure 1: y = < <2^{2}x> >  Figure 2: y = {{2^{2}x}}

Figure 3: y = τ(x)  Figure 4: y = ρ_{2}(x)

The Takagi function has interesting analytic properties not shared by ρ_{b}. For example, while the Takagi function is continuous, ρ_{b} is easily seen to be continuous except at the b-adics as suggested by Figure 4 for the case b = 2. In general, at each b-adic, \frac{a}{b^{m}}, ρ_{b} is right continuous with a jump discontinuity of −\frac{1}{b^{m−1}(b−1)}. On the other hand, the ρ_{b} function has interesting number theoretic features not shared by τ as we will show in the following section.

In the final section of this note, we show that the ρ_{b} function is related to the rumor conjecture described in Dearden and Metzger [1], and finally a conjecture concerning ρ_{b} that is equivalent to the rumor sequence conjecture is stated.

2 Arithmetic Properties of the ρ_{b} Function

An alternative expression for ρ_{b}(x) can be given in terms of the base-b expansion of x. In this note we will follow the usual convention that base-b expansions of b-adics terminate rather than end with an infinite string of (b − 1)’s.

Theorem 1. If ∑_{j=1}^{∞} \frac{d_{j}}{b^{j}} is the base-b expansion of x ∈ [0, 1), then ρ_{b}(x) = ∑_{j=1}^{∞} \frac{jd_{j}}{b^{j}}.

Proof. Let x = ∑_{j=1}^{∞} \frac{d_{j}}{b^{j}} ∈ [0, 1). Then

ρ_{b}(x) = ∑_{n=0}^{∞} \frac{\{\{b^{n}x\}\}}{b^{n}} = ∑_{n=0}^{∞} \frac{\{\{b^{n} ∑_{j≥1} d_{j}b^{−j}\}\}}{b^{n}}

= ∑_{n=0}^{∞} \frac{1}{b^{n}} \{ ; \{∑_{j=1}^{n} d_{j}b^{n−j} + ∑_{j>n} d_{j}b^{n−j}\} ; \} = ∑_{n=0}^{∞} \frac{1}{b^{n}} ∑_{j>n} d_{j}b^{n−j}

= ∑_{n=0}^{∞} ∑_{j>n} \frac{d_{j}}{b^{j}} = ∑_{j=1}^{∞} ∑_{n=0}^{j−1} \frac{d_{j}}{b^{j}} = ∑_{j=1}^{∞} \frac{jd_{j}}{b^{j}} .

Theorem 2. The range of ρ_{b} is [0, \frac{b}{b−1}).

Proof. Let y ∈ [0, \frac{b}{b−1}) be given. Integers d_{j} ∈ D = \{0, 1, …, b − 1\} are selected recursively as follows. First let d_{1} be the largest integer in D such that \frac{d_{1}}{b} ≤ y. Assuming d_{1}, d_{2}, …, d_{i−1} have been selected, take d_{i} to be the largest integer in D such that \frac{id_{i}}{b^{i}} ≤ y − ∑_{j=1}^{i−1} \frac{jd_{j}}{b^{j}}. In this way, the base-b expansion of a number x = ∑_{j=1}^{∞} \frac{d_{j}}{b^{j}} is constructed.

We now show that this expansion of x does not end in an infinite sequence of (b − 1)’s, and consequently x ∈ [0, 1) and ρ_{b}(x) = ∑_{j=1}^{∞} \frac{jd_{j}}{b^{j}}. To this end, by way of contradiction, assume the expansion does end with an infinite sequence of (b − 1)’s. It can not be that all the digits, d_{j}, are b − 1 since, if they were, we would have

∑_{j=1}^{∞} \frac{jd_{j}}{b^{j}} = ∑_{j=1}^{∞} \frac{j(b − 1)}{b^{j}} = (b − 1) ∑_{j=1}^{∞} \frac{j}{b^{j}} = (b − 1)\frac{b}{(b − 1)^{2}} = \frac{b}{b − 1},

but ∑_{j=1}^{∞} \frac{jd_{j}}{b^{j}} ≤ y < \frac{b}{b−1}. So there must be a last digit, d_{L}, that is less than b − 1. It follows that for all m > L,

\frac{m(b − 1)}{b^{m}} ≤ y − ∑_{j=1}^{L−1} \frac{jd_{j}}{b^{j}} − \frac{Ld_{L}}{b^{L}} − ∑_{j=L+1}^{m−1} \frac{j(b − 1)}{b^{j}}.

Hence, for all m > L, we have

\frac{Ld_{L}}{b^{L}} + ∑_{j=L+1}^{m} \frac{j(b − 1)}{b^{j}} ≤ y − ∑_{j=1}^{L−1} \frac{jd_{j}}{b^{j}} .

Consequently

\frac{Ld_{L}}{b^{L}} + ∑_{j=L+1}^{∞} \frac{j(b − 1)}{b^{j}} ≤ y − ∑_{j=1}^{L−1} \frac{jd_{j}}{b^{j}} .

Now

∑_{j=L+1}^{∞} \frac{j(b − 1)}{b^{j}} = \frac{(L + 1)b − L}{b^{L}(b − 1)} > \frac{L}{b^{L}} .

Thus

\frac{L(d_{L} + 1)}{b^{L}} = \frac{Ld_{L}}{b^{L}} + \frac{L}{b^{L}} ≤ y − ∑_{j=1}^{L−1} \frac{jd_{j}}{b^{j}} ,

contradicting the choice of d_{L}.

For any i with d_{i} < b − 1, we have

\frac{id_{i}}{b^{i}} ≤ y − ∑_{j=1}^{i−1} \frac{jd_{j}}{b^{j}} < \frac{i(d_{i} + 1)}{b^{i}}.

Since that holds for infinitely many i, and since ∑_{j=1}^{∞} \frac{jd_{j}}{b^{j}} is a positive series, it follows that ρ_{b}(x) = ∑_{j=0}^{∞} \frac{jd_{j}}{b^{j}} = y.

The x constructed in the proof above is the largest of the inverses of the given y under ρ_{b}. Call the x so constructed the greedy inverse image of y. In order to construct a valid base-b number x as the greedy inverse of a given y, we explicitly required each d_{i} to be an element of the set D = {0, 1, …, b − 1}, rather than using a floor function, as in

⌊\frac{b^{i} (y − ∑_{j=1}^{i−1} \frac{jd_{j}}{b^{j}} )}{i}⌋ .

Since this integer may be larger than b − 1, the restriction on d_{i} was needed. We now show that d_{i} is eventually given by this floor function expression.

Corollary 3. With the notation as in the proof of Theorem 2, for large enough i,

d_{i} = ⌊\frac{b^{i} (y − ∑_{j=1}^{i−1} \frac{jd_{j}}{b^{j}} )}{i}⌋ and 0 ≤ y − ∑_{j=1}^{i} \frac{jd_{j}}{b^{j}} < \frac{i}{b^{i}} .

Proof. We show, for i large enough, that the quantity z = b^{i} (y − ∑_{j=1}^{i−1} \frac{jd_{j}}{b^{j}} ) /i is less than b, and, thus, ⌊z⌋ ∈ D. From the proof of Theorem 2, there is an integer n with d_{n} < b − 1, where d_{n} is the largest integer in D = {0, 1, …, b − 1} such that

\frac{nd_{n}}{b^{n}} ≤ y − ∑_{j=1}^{n−1} \frac{jd_{j}}{b^{j}} .

Thus, we see that

\frac{nd_{n}}{b^{n}} ≤ y − ∑_{j=1}^{n−1} \frac{jd_{j}}{b^{j}} < \frac{n(d_{n} + 1)}{b^{n}}.  (1)

Equivalently, we have

d_{n} ≤ \frac{b^{n} (y − ∑_{j=1}^{n−1} \frac{jd_{j}}{b^{j}} )}{n} < d_{n} + 1.

Now, since d_{n} + 1 < b, we have that

⌊\frac{b^{n} (y − ∑_{j=1}^{n−1} \frac{jd_{j}}{b^{j}} )}{n}⌋ ∈ D.

Therefore, d_{n} may be expressed as

d_{n} = ⌊\frac{b^{n} (y − ∑_{j=1}^{n−1} \frac{jd_{j}}{b^{j}} )}{n}⌋ .

And, rearranging (1) we see that

0 ≤ y − ∑_{j=1}^{n} \frac{jd_{j}}{b^{j}} < \frac{n}{b^{n}} .

Inductively, consider any i ≥ n where

0 ≤ y − ∑_{j=1}^{i} \frac{jd_{j}}{b^{j}} < \frac{i}{b^{i}} .  (2)

By definition, d_{i+1} is the greatest integer in D such that

d_{i+1} ≤ \frac{b^{i+1} (y − ∑_{j=1}^{i} \frac{jd_{j}}{b^{j}} )}{i + 1}.  (3)

Moreover, using (2), we have

\frac{b^{i+1} (y − ∑_{j=1}^{i} \frac{jd_{j}}{b^{j}} )}{i + 1} < \frac{i}{i + 1}b < b.

Hence, as before, we have that

d_{i+1} = ⌊\frac{b^{i+1} (y − ∑_{j=1}^{i} \frac{jd_{j}}{b^{j}} )}{i + 1}⌋ ,

since the value of the floor expression is an element of the set D. Finally, from (3), we have

\frac{(i + 1)d_{i+1}}{b^{i+1}} ≤ y − ∑_{j=1}^{i} \frac{jd_{j}}{b^{j}} < \frac{(i + 1)(d_{i+1} + 1)}{b^{i+1}}.

From which we have

0 ≤ y − ∑_{j=1}^{i+1} \frac{jd_{j}}{b^{j}} < \frac{i + 1}{b^{i+1}},

completing the induction.

There are several easily verified functional identities satisfied by ρ_{b} stated in the next theorem.

Theorem 4. The following identities hold for ρ_{b}:

(a) For the b-adic x = \frac{a}{b^{m}} ∈ [0, 1), ρ_{b}(x) + ρ_{b}(1 − x) = \frac{b}{b−1} − \frac{1}{b^{m−1}(b−1)}.

(b) For any non-b-adic x ∈ [0, 1), ρ_{b}(x) + ρ_{b}(1 − x) = \frac{b}{b−1}.

(c) For x ∈ [0, 1) and integer m ≥ 1, ρ_{b} (\frac{x}{b^{m}} ) = \frac{m}{b^{m}} x + \frac{1}{b^{m}} ρ_{b}(x).

(d) If b^{m}x ∈ [0, 1), then ρ_{b}(b^{m}x) = b^{m}ρ_{b}(x) − mb^{m}x.

Theorem 5. Suppose \frac{s}{t} is a rational number in lowest terms with gcd(t, b) = 1. If ρ_{b}(\frac{s}{t}) = \frac{u}{v}, a rational in lowest terms, then (1) there is a divisor t′ > 1 of t such that (t′)^{2} divides v, and (2) b divides u.

Proof. Since t is relatively prime to b, the base-b expansion of \frac{s}{t} is purely periodic. Let r be the order of b modulo t, so that r is the period of that expansion. That means there is an integer c so that ct = b^{r} − 1. Then

\frac{s}{t} = \frac{cs}{ct} = \frac{cs}{b^{r} − 1} = ∑_{m≥1} \frac{cs}{b^{mr}} = ∑_{m≥1} \frac{∑_{i=1}^{r} b^{r−i}d_{i}}{b^{mr}} ,

where

\frac{s}{t} = ∑_{j≥1} \frac{d_{j}}{b^{j}} = ∑_{m≥0} ∑_{i=1}^{r} \frac{d_{i}}{b^{mr+i}} has period r.

First, calculate ρ_{b}(\frac{s}{t}) as follows:

\frac{u}{v} = ρ_{b} (\frac{s}{t}) = ∑_{j≥1} \frac{jd_{j}}{b^{j}} = ∑_{m≥0} ∑_{i=1}^{r} \frac{(mr + i)d_{mr+i}}{b^{mr+i}} = ∑_{m≥0} ∑_{i=1}^{r} \frac{(mr + i)d_{i}}{b^{mr+i}}

= ∑_{m≥0} \frac{1}{b^{mr}} (mr ∑_{i=1}^{r} \frac{d_{i}}{b^{i}} + ∑_{i=1}^{r} \frac{id_{i}}{b^{i}} )

= ∑_{m≥0} \frac{1}{(b^{r})^{m+1}} (mr ∑_{i=1}^{r} b^{r−i}d_{i} + ∑_{i=1}^{r} ib^{r−i}d_{i})

= ∑_{m≥0} \frac{1}{(b^{r})^{m+1}} (mrcs + w) , where w = ∑_{1≤i≤r} ib^{r−i}d_{i}

= \frac{rcs}{(b^{r} − 1)^{2}} + \frac{w}{b^{r} − 1} = \frac{rcs + (b^{r} − 1)w}{(b^{r} − 1)^{2}} = \frac{rcs + ctw}{c^{2}t^{2}}

= \frac{rs + tw}{ct^{2}}.

Let d = gcd(t, r) and define t′ and r′ by t = t′d and r = r′d. Then, we have

ρ_{b} (\frac{s}{t}) = \frac{r′s + t′w}{ctt′} = \frac{r′s + t′w}{cd(t′)^{2}}.

Since r divides φ(t) we have

r ≤ φ(t) < t, hence, 1 ≤ r′ < t′.

In particular, we have that t′ ≠ 1.

Since t′ is relatively prime to both s and r′, we have that (t′)^{2} does not cancel when the fraction is reduced to lowest terms. That completes the proof of (1).

For the proof of (2), calculate ρ_{b}(\frac{s}{t}) as

\frac{u}{v} = ρ_{b} (\frac{s}{t}) = ∑_{m≥0} ∑_{i=1}^{r} \frac{(mr + i)d_{i}}{b^{mr+i}} = ∑_{i=1}^{r} ∑_{m≥0} \frac{(mr + i)d_{i}}{b^{mr+i}}

= \frac{1}{(b^{r} − 1)^{2}} ∑_{i=1}^{r} d_{i}b^{r−i}(r − i + b^{r}i).

Note that b is a factor of each term in the sum, including the term when i = r. Since b is relatively prime to b^{r} − 1, it follows that b divides u.

Corollary 6. There are rationals in the range [0, \frac{b}{b−1}) of ρ_{b} that are not images of any rationals in its domain.

Example 7. For b ≠ 3, the rational \frac{1}{3} cannot be the image of a rational under ρ_{b}.

The conditions given in Theorem 5 apparently do not completely characterize the rationals that are images of rationals. In particular, for b = 2 we suspect that among \frac{2k}{9}, k = 1, 2, 4, 5, 7, 8, only \frac{8}{9} = ρ_{2}(\frac{1}{3}) and \frac{10}{9} = ρ_{2}(\frac{2}{3}) have rational inverse images.

In Theorem 8 we derive an expression for ρ_{b}(\frac{a}{b^{r}}) analogous to one for the Takagi function given by Maddock [2]. If the base-b expansion of the positive integer a is given by a = ∑_{i=0}^{m−1} e_{i}b^{i}, define σ_{b}(a) by

σ_{b}(a) = ∑_{i=0}^{m−1} ie_{i}b^{i}.

It is easy to check that σ_{b}(a) can be written in a way that does not specifically involve the base-b expansion:

σ_{b}(a) = ∑_{j≥1} b^{j} ⌊\frac{a}{b^{j}} ⌋ = ∑_{1≤b^{j}≤a}(a − (a mod b^{j})).

The σ_{b} functions are related to several sequences in Sloane’s OEIS database. Specifically, sequence \underline{A080277} is a + σ_{2}(a) = ∑_{j≥0} 2^{j}⌊\frac{a}{2^{j}} ⌋, while \underline{A080333} is a + σ_{3}(a) = ∑_{j≥0} 3^{j}⌊\frac{a}{3^{j}} ⌋. Also, the sums s_{a} = ∑_{1≤b^{j}≤a}(a mod b^{j}) appear in OEIS for b = 2 and b = 3 as \underline{A049802} and \underline{A049803} respectively.

Theorem 8. For the b-adic rational \frac{a}{b^{r}}, where 0 ≤ a < b^{r}, we have

ρ_{b} (\frac{a}{b^{r}} ) = \frac{ra − σ_{b}(a)}{b^{r}}.

Proof. Let the base-b expansion of a be a = ∑_{i=0}^{r−1} e_{i}b^{i}. We then have

ρ_{b} (\frac{a}{b^{r}} ) = ρ_{b} (∑_{i=0}^{r−1} \frac{e_{i}}{b^{r−i}} ) = ∑_{i=0}^{r−1} \frac{(r − i)e_{i}}{b^{r−i}} ,

= \frac{1}{b^{r}} [∑_{i=0}^{r−1} re_{i}b^{i} − ∑_{i=0}^{r−1} ie_{i}b^{i}] ,

= \frac{1}{b^{r}} [ra − σ_{b}(a)] .

Theorem 9. Consider the rational number s/t in reduced form with t relatively prime to b. Let r = ord_{t}(b), ct = b^{r} − 1, and a = cs. Then,

ρ_{b} (\frac{s}{t}) = ρ_{b} (\frac{a}{b^{r} − 1}) = \frac{rb^{r}a}{(b^{r} − 1)^{2}} − \frac{σ_{b}(a)}{b^{r} − 1}.

Proof. Given the base-b expansion a = ∑_{i=0}^{r−1} e_{i}b^{i}, we have

\frac{a}{b^{r} − 1} = ∑_{k≥1} ∑_{i=0}^{r−1} \frac{e_{i}}{b^{rk−i}} .

Hence, we calculate

ρ_{b} (\frac{s}{t}) = ρ_{b} (\frac{a}{b^{r} − 1}) = ∑_{k≥1} ∑_{i=0}^{r−1}(rk − i)\frac{e_{i}}{b^{rk−i}} ,

= ∑_{k≥1} \frac{1}{b^{rk}} [∑_{i=0}^{r−1} rke_{i}b^{i} − ∑_{i=0}^{r−1} ie_{i}b^{i}] ,

= ∑_{k≥1} \frac{1}{b^{rk}} [kra − σ_{b}(a)] ,

= \frac{rb^{r}a}{(b^{r} − 1)^{2}} − \frac{σ_{b}(a)}{b^{r} − 1}.

Theorem 9 leads to a relation between two values of ρ_{b}. With s, t, r, a as in the proof of that theorem, we see

ρ_{b} (\frac{s}{t}) = ρ_{b} (\frac{a}{b^{r} − 1}) = \frac{rb^{r}a}{(b^{r} − 1)^{2}} − \frac{σ_{b}(a)}{b^{r} − 1}

= \frac{rb^{r}a − (b^{r} − 1)σ_{b} (a)}{(b^{r} − 1)^{2}}

= \frac{ra + (b^{r} − 1) (ra − σ_{b}(a))}{(b^{r} − 1)^{2}}

= \frac{ra}{(b^{r} − 1)^{2}} + \frac{b^{r}}{b^{r} − 1}ρ_{b} (\frac{a}{b^{r}} ) .

3 The Connection Between ρ_{b} and Rumor Sequences

In Dearden and Metzger [1], rumor sequences (\underline{ru}nning \underline{mo}dulus \underline{r}ecursive sequences) were introduced as follows:

Let b ≥ 2 and k ≥ 1 be integers. To construct an (integer) rumor sequence select an integer z_{0}, and for n ≥ 1 let z_{n} = bz_{n−1} mod (n + k), where the right side is the least nonnegative residue of bz_{n−1} modulo n + k. The rumor sequence conjecture asserts that all such integer rumor sequences are eventually 0. Since the conjecture concerns only the eventual behavior of such sequences and since 0 ≤ z_{1} < k + 1, nothing is lost by restricting z_{0} to the interval [0, k).

To establish a connection between the rumor sequence conjecture and the ρ_{b} function, it is convenient to generalize the notion of integer rumor sequences to real rumor sequences.

Let b ≥ 2 and k ≥ 1 be integers. To construct a (real) rumor sequence, select any real number x_{0} and for n ≥ 1 let x_{n} = bx_{n−1} mod (n + k) where the right hand side is taken to be

bx_{n−1} − (n + k) ⌊\frac{bx_{n−1}}{n + k} ⌋ .  (4)

As with integer rumors, there is no loss if x_{0} is restricted to the interval [0, k). The real and integer rumors are identical when x_{0} = z_{0} is an integer.

It will be shown that the rumor conjecture for integer rumor sequences is true if and only if the greedy inverse image under ρ_{b} of every b-adic rational is a b-adic rational. It is worth noting that, in general, not all inverse images of a b-adic under ρ_{b} need be b-adic.

Example 10. Consider the 3-adic rational y = \frac{2}{3} in the range of ρ_{3}. With b = 3, let the greedy ρ_{3} inverse image of \frac{5}{6} be x. Since 6 is not divisible by a square greater than 1, x must be irrational. It follows that 1 − x is irrational and, by Theorem 4(b), we see

ρ_{3}(1 − x) = \frac{3}{2} − \frac{5}{6} = \frac{2}{3}.

Theorem 11. For b ≥ 2, all integer rumor sequences are eventually 0 if and only if the greedy inverse image under ρ_{b} of every b-adic is b-adic.

Proof. Suppose that all integer rumor sequences are eventually zero, and let y = a/b^{m} be a b-adic rational in [0, b/(b − 1)). By Corollary 3, there is an integer n so that for k ≥ n we have

d_{k} = ⌊\frac{b^{k} (y − ∑_{j=1}^{k−1} jd_{j}/b^{j})}{k}⌋ and 0 ≤ y − ∑_{j=1}^{k} \frac{jd_{j}}{b^{j}} < \frac{k}{b^{k}} .

Now, consider the real rumor sequence with initial value x_{0} ∈ [0, n) given by

x_{0} = b^{n} (y − ∑_{j=1}^{n} \frac{jd_{j}}{b^{j}} ) .

Applying the rumor recursion (4), we have

x_{1} = bx_{0} − (n + 1) ⌊\frac{bx_{0}}{n + 1}⌋

= b^{n+1} (y − ∑_{j=1}^{n} \frac{jd_{j}}{b^{j}} ) − (n + 1) ⌊\frac{b^{n+1} (y − ∑_{j=1}^{n} jd_{j}/b^{j})}{n + 1}⌋

= b^{n+1} (y − ∑_{j=1}^{n} \frac{jd_{j}}{b^{j}} ) − (n + 1)d_{n+1}, by Corollary 3

= b^{n+1} (y − ∑_{j=1}^{n+1} \frac{jd_{j}}{b^{j}} ) .

More generally, induction shows that, for all i ≥ 0, we have

x_{i} = b^{n+i} (y − ∑_{j=1}^{n+i} \frac{jd_{j}}{b^{j}} ) = b^{n+i} (\frac{a}{b^{m}} − ∑_{j=1}^{n+i} \frac{jd_{j}}{b^{j}} ) .

Now, for i ≥ m − n, the sequence x_{i} is obtained from an integer rumor recursion, and by our assumption that integer rumor sequence is eventually zero, say from term i_{0} on. That means the greedy inverse image under ρ_{b} of the b-adic rational a/b^{m} = ∑_{j=1}^{n+i_{0}} jd_{j}/b^{j} is the b-adic rational

υ = ∑_{j=1}^{n+i_{0}} \frac{d_{j}}{b^{j}} = \frac{∑_{j=1}^{n+i_{0}} d_{j}b^{n+i_{0}−j}}{b^{n+i_{0}}} .

Conversely, suppose that the greedy inverse image of b-adic rationals in [0, b/(b − 1)) are b-adic rationals. Consider an integer rumor recursion with initial value z_{0} in [0, k). By our assumption the greedy inverse of the b-adic rational y = z_{0}/b^{k} is a b-adic rational ∑_{j=1}^{n} j/b^{j}, where

y = ∑_{j=1}^{n} \frac{jd_{j}}{b^{j}} , with d_{j} ∈ \{0, 1, …, b − 1\}.

Since f(x) = x/b^{x} is a nondecreasing function on positive integers for all integers b ≥ 2, we have z_{0}/b^{k} < k/b^{k} ≤ m/b^{m} for all m = 1, 2, 3, …, k. Therefore, it follows that

0 ≤ \frac{z_{0}}{b^{k}} − ∑_{j=1}^{m−1} \frac{jd_{j}}{b^{j}} < \frac{m}{b^{m}} , for m = 1, 2, …, k .

Hence,

d_{j} = 0 for j = 1, 2, …, k.

It follows that

\frac{z_{0}}{b^{k}} = y = ∑_{j=k+1}^{n−k} \frac{(k + i)d_{k+i}}{b^{k+i}} .  (5)

Moreover, for all m = 1, 2, …, n − k, we have

\frac{(k + m)d_{k+m}}{b^{k+m}} ≤ \frac{z_{0}}{b^{k}} − ∑_{i=1}^{m−1} \frac{(k + i)d_{k+i}}{b^{k+i}} < \frac{(k + m)(d_{k+m} + 1)}{b^{k+m}}.

Multiplying through by b^{k} gives

\frac{(k + m)d_{k+m}}{b^{m}} ≤ z_{0} − ∑_{i=1}^{m−1} \frac{(k + i)d_{k+i}}{b^{i}} < \frac{(k + m)(d_{k+m} + 1)}{b^{m}}.

In particular, for m = 1 we have

\frac{(k + 1)d_{k+1}}{b} ≤ z_{0} < \frac{(k + 1)d_{k+1}}{b}

or

d_{k+1} ≤ ⌊\frac{bz_{0}}{k + 1}⌋ < d_{k+1} + 1.

It follows that

z_{1} = bz_{0} − (k + 1) ⌊\frac{bz_{0}}{k + 1}⌋ = bz_{0} − (k + 1)d_{k+1}.

Hence,

\frac{z_{1}}{b} = z_{0} − \frac{(k + 1)d_{k+1}}{b} .

In general, induction shows that, for all m ≥ 1,

\frac{z_{m}}{b^{m}} = z_{0} − ∑_{i=1}^{m} \frac{(k + i)d_{k+i}}{b^{i}} .

Therefore, by equation (5), we have

\frac{z_{n−k}}{b^{n−k}} = z_{0} − ∑_{i=1}^{n−k} \frac{(k + i)d_{k+i}}{b^{i}} = 0.

Thus, any integer rumor sequence is eventually zero.

The following corollary follows immediately from the proof of Theorem 11.

Corollary 12. Let b ≥ 2 be an integer. The integer rumor sequence with initial term z_{0}, where 0 ≤ z_{0} < k, is eventually 0 if and only if the greedy inverse image of \frac{z_{0}}{b^{k}} under ρ_{b} is b-adic.

Conjecture 13. The greedy inverse image of every b-adic under ρ_{b} is b-adic.

4 Acknowledgments

The authors would like to thank the referee for the careful reading and helpful suggestions which improved the paper.

References

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

[2] Z. Maddock, Level sets of the Takagi function: Hausdorff dimension, Monatshefte für Math., 160 (2010), 167–186.

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

(Related to sequences \underline{A049802}, \underline{A049803}, \underline{A080277}, \underline{A080333}, and \underline{A177356}.)

Received December 1 2010; revised version received February 1 2011; Published in Journal of Integer Sequences, February 19 2011.

Return to Journal of Integer Sequences home page.