Partial Complements and Transposable Dispersions

Clark Kimberling and John E. Brown Department of Mathematics University of Evansville 1800 Lincoln Avenue Evansville, IN 47722 USA

                  ck6@evansville.edu

Abstract

Suppose A = {a(i, j)}, for i ≥ 0 and j ≥ 0, is the dispersion of a strictly increasing sequence r = (r(0), r(1), r(2), …) of integers, where r(0) = 1 and infinitely many postive integers are not terms of r. Let R be the set of such sequences, and define t on R by tr(n) = a(0, n) for n ≥ 0. Let F be the subset of R consisting of sequences r satisfying ttr = r. The set F is characterized in terms of ordered arrangements of numbers i + jθ. For fixed i ≥ 0, the sequence a(i, j), for j ≥ 1, is the (i + 1)st partial complement of r. Central to the characterization of F is the role of the families of figurate (or polygonal) number sequences and the centered polygonal number sequences. Finally, it is conjectured that for every r in R, the iterates t^{(2m)}r converge to a sequence in F.

1 Introduction

Let N denote the set of positive integers. Suppose r = (r(0), r(1), r(2), …) is a strictly increasing sequence of integers with r(0) = 1 and infinite complement in N. Let r^{∗} be the sequence obtained by arranging in increasing order the complement of r. Let

a(0, 0) = 1, a(0, 1) = r^{∗}(1),

and inductively,

a(0, j) = r^{∗}(a(0, j − 1))

for j ≥ 1. The sequence a(0, j), for j ≥ 1, is the 1st partial complement of r. For arbitrary i ≥ 0, suppose that the sequence a(i, j) for j ≥ 0 is defined, and let a(i + 1, 0) be the least number in N that is not a(h, j) for any (h, j) satisfying 0 ≤ h ≤ i and j ≥ 0. Define

a(i + 1, j) = r^{∗}(a(i + 1, j − 1))  (1)

for j ≥ 1. In this inductive manner, an array A = {a(i, j)}, for i ≥ 0, j ≥ 0, is defined. It is called the dispersion of r^{∗}. (In [3], where the terms dispersion and interspersion are introduced, the indexing is by i ≥ 1, j ≥ 1 instead of i ≥ 0, j ≥ 0.) For fixed i ≥ 0 and variable j ≥ 1, the sequence a(i, j) is the (i + 1)st partial complement of r.

To summarize, the dispersion A of the complement of r, henceforth denoted by A(r), consists of first column r together with the terms of r^{∗} dispersed into partial complements; row i of A(r) consists of first term r(i) followed by the (i + 1)st partial complement of r. It is sometimes desirable to use a recurrence for a(i + 1, j) that refers directly to r. To develop such a recurrence, for any strictly increasing sequence ρ in N, let #(ρ(n) ≤ m) denote the number of n ≥ 1 satisfying ρ(n) ≤ m. Clearly, ρ(h) is the least m satisfying #(ρ(n) ≤ m) = h. Now take ρ = r^{∗} and h = a(i, j) to see that

a(i, j + 1) = least m satisfying (#(r^{∗}(n) ≤ m) = a(i, j)).

As #(r(n) ≤ m) + #(r^{∗}(n) ≤ m) = m, we obtain

a(i, j + 1) = least m satisfying (m − #(r(n) ≤ m) = a(i, j))
= min{m : max{n : r(n) ≤ m} = a(i, j) − m + 1}.  (2)

This recurrence is especially useful in coding computer programs that generate dispersions.

Let R be the set of sequences r described in the first sentence. Let tr denote the first partial complement of r, and let F be the family of sequences r for which ttr = t. A main objective of this paper is to characterize F in terms of sequences associated with multisets of the form

S_{θ} = {i + jθ : i ≥ 0, j ≥ 0},  (3)

where θ is a positive real number. The numbers in S_{θ} are distinct if θ is irrational; otherwise, write θ = c/d, where c and d are relatively prime positive integers. Then a number i + jθ occurs more than once in S_{θ} if and only if i ≥ c, and in this case the representations of i + jθ are these:

i, i − c + dθ, i − 2c + 2dθ, ⋯, i − ⌊i/c⌋ c + ⌊i/c⌋ dθ.

In order to treat these as distinct objects, we represent each h + kθ as an ordered pair (h, k), so that the representations of i + jθ become

(i, 0), (i − c, d), (i − 2c, 2d), ⋯, (i − ⌊i/c⌋ c, ⌊i/c⌋ d).

Define an order relation ≺ on the set {(i, j) : i ≥ 0, j ≥ 0} by

(i_{1}, j_{1}) ≺ (i_{2}, j_{2}) if i_{1} + j_{1}θ < i_{2} + j_{2}θ
(i_{1}, j_{1}) ≺ (i_{2}, j_{2}) if i_{1} + j_{1}θ = i_{2} + j_{2}θ and j_{1} < j_{2}.

We extend this definition to the case that θ is irrational, noting that the condition i_{1} + j_{1}θ = i_{2} + j_{2}θ does not occur. Now for any real θ > 0, the rank array of θ is defined by

A_{θ} = {a_{θ}(i, j) : i ≥ 0, j ≥ 0},

where

a_{θ}(i, j) = rank of (j, i) under ≺ .

(Defining a_{θ}(i, j) as the rank of (j, i) rather than that of (i, j) facilitates later developments, such as equation (13) and connections with Farey sequences. For irrational θ, the condition “rank of (j, i) under ≺” can be replaced by “rank of j + iθ under [ordinary] <”; in this case, r_{θ}(n) is simply the rank of nθ among all the numbers h + kθ.)

As an example, let c = 4 and d = 3. Then

(0, 0) ≺ (1, 0) ≺ (0, 1) ≺ (2, 0) ≺ (1, 1) ≺ (0, 2) ≺ (3, 0) ≺ (2, 1) ≺ (1, 2) ≺
(4, 0) ≺ (0, 3) ≺ (3, 1) ≺ (2, 2) ≺ (5, 0) ≺ (1, 3) ≺ (4, 1) ≺ (0, 4) ≺ (3, 2) ≺
(6, 0) ≺ (2, 3) ≺ (5, 1) ≺ (1, 4) ≺ (4, 2) ≺ (0, 5) ≺ (7, 0) ≺ (3, 3) ≺ (6, 1) ≺
(2, 4) ≺ (5, 2) ≺ (1, 5) ≺ (8, 0) ≺ (4, 3) ≺ (0, 6) ≺ ⋯

Numbering these from 1 to 33 shows that the rank array A_{4/3} starts like this:

1 2 4 7 10 14 19 25 31
3 5 8 12 16 21 27
6 9 13 18 23 29
11 15 20 26 32
17 22 28

24 33

Theorem 1.1 Suppose θ > 0. Then A_{θ} is an interspersion.

Proof: We shall show that each of the propositions (I1)-(I4) that define an interspersion in [3] is satisfied:

(I1) The rows of A_{θ} comprise a partition of N, as N is the set of ranks of numbers in S_{θ}, and these ranks are partitioned by the rows of A_{θ}.

(I2) Every row of A_{θ} is an increasing sequence, as (j, i) ≺ (j + 1, i) for all i ≥ 0, j ≥ 0. (I3) Every column of A_{θ} is an increasing sequence, as (j, i) ≺ (j, i + 1) for all i ≥ 0,

j ≥ 0.

(I4) If (u_{j}) and (v_{j}) are distinct rows of A_{θ} and if p and q are indices for which u_{p} < v_{q} < u_{p+1}, then u_{p+1} < v_{q+1} < u_{p+2}. That is, in the present context, if i ≠ i′ and a(i, p) < a(i′, q) < a(i, p + 1), or equivalently,

(p, i) ≺ (q, i′) ≺ (p + 1, i),

then

(p + 1, i) ≺ (q + 1, i′) ≺ (p + 2, i),

or equivalently, a(i, p + 1) < a(i′, q + 1) < a(i, p + 2). □

Corollary 1.1 For i ≥ 0, let s be the sequence obtained by deleting the initial term of row i of A_{θ}. Then s is the (i + 1)st partial complement of column 0 of A_{θ}.

Proof: By Theorem 1 of [3], the array A_{θ} is a dispersion, and as shown in the proof in [3],

a(i, j + 1) = t(a(i, j)),

where (t(k)) denotes the sequence of numbers, arranged in increasing order, in the set N\{a(0, j) : j ≥ 0}, this set being the complement of column 0 of A_{θ}. □

Let r_{θ} denote column 0 of A_{θ}. By Corollary 1, row 0 of A_{θ} is the sequence tr_{θ}, a property to be used in the next proof.

Corollary 1.2 Suppose θ is a positive irrational number. Then tr_{θ} = r_{1/θ} and ttr_{θ} = r_{θ}.

Proof: Referring to the array A_{1/θ}, we have, for m ≥ 0 and n ≥ 0,

a_{1/θ}(m, n) = (rank of m + n/θ in S_{1/θ})
= (rank of mθ + n in S_{θ})
= a_{θ}(n, m).

That is, A_{1/θ} is the transpose of A_{θ}. Consequently, A_{1/(1/θ)} = A_{θ}, so that ttr_{θ} = r_{θ}. □

A dispersion {a(i, j)} is transposable if its transpose, {a(j, i)}, is a dispersion. According to Corollary 3, the dispersions of A\sqrt{2} and A_{1/\sqrt{2}} are transposable; northwest corners of these arrays are shown in Example 1 We shall see in section 3 that there are transposable dispersions other than those given by the proof of Corollary 3.

Example 1: The arrays A_{θ} and A_{1/θ} for θ = \sqrt{2}

\begin{matrix}1 & 2 & 4 & 7 & 10 & … & 1 & 3 & 6 & 11 & 17 & … \\ 3 & 5 & 8 & 12 & 16 & … & 2 & 5 & 9 & 15 & 22 & … \\ 6 & 9 & 13 & 18 & 23 & … & 4 & 8 & 13 & 20 & 28 & … \\ 11 & 15 & 20 & 26 & 32 & … & 7 & 12 & 18 & 26 & 35 & … \\ 17 & 22 & 28 & 35 & 42 & … & 10 & 16 & 23 & 32 & 42 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}

Initial terms of tr can be written out from initial terms of r, for any r in R, by means of a handly little algorithm. We use the sequence r = (1, 2, 4, 7, 10, …) of column 0 of A\sqrt{2} to exemplify:

Step 1. Write initial terms of the complement, r^{∗}, with counting numbers above:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 3 5 6 8 9 11 12 13 15 16 17 18 20 21

Step 2. Determine the chain 1 → 3 → 6 → 11 → 17 → ⋯, as indicated by the paired rectangles. These numbers form the sequence tr, alias row 0 of A\sqrt{2}, alias (after the initial 1) the 1st partial complement of r. (Note that repeating the procedure starting with the pair (2, 5) yields the 2nd partial complement of r, and so on.)

If θ ∈ N, then the sequences r_{θ} and r_{1/θ}, we shall prove in section 2, are closely related to certain well-known sequences. We continue this introduction with an overview of those sequences, with reference to indexing systems in [5] and [6]. Sequences of polygonal (or figurate) numbers, typified by

P_{1} = (1, 3, 6, 10, 15, …) = triangular numbers (A000217 in [6], 253 in [5])
P_{2} = (1, 4, 9, 16, 25, …) = square numbers (A000290 in [6], 338 in [5])
P_{3} = (1, 5, 12, 22, 35, …) = pentagonal numbers (A000326 in [6], 339 in [5]),

are given for k ≥ 1 by

P_{k}(n) = k ( \begin{matrix}n + 1 \\ 2 \end{matrix} ) + n + 1  (4)

for n ≥ 0. Sequences of central polygonal numbers,

Q_{1} = (1, 3, 7, 13, 21, …) = central polygonal numbers (A002061 in [6])
Q_{2} = (1, 4, 10, 19, 31, …) = central triangular numbers (A005448 in [6])
Q_{3} = (1, 5, 13, 25, 41, …) = central square numbers (A001844 in [6]),

are given for k ≥ 1 by

Q_{k}(n) = (k + 1) ( \begin{matrix}n + 1 \\ 2 \end{matrix} ) + 1  (5)

for n ≥ 0, so that

Q_{k}(n) = P_{k+1}(n) − n.  (6)

The sequences P_{k} and Q_{k} are easily expressed in terms of P_{1} and Q_{1}:

P_{k}(n) = P_{1}(n) + (k − 1)P_{1}(n − 1),
Q_{k}(n) = Q_{1}(n) + (k − 1)P_{1}(n − 1),

for k ≥ 1, n ≥ 1. For a colorful introduction to the geometry associated with the numbers P_{k} and Q_{k}, see [1, pp. 38-42]. Consider next the sequences

P̂_{1} = (1, 2, 4, 7, 11, …) = lazy caterer sequence (A000124 in [6], 386 in [5])
P̂_{2} = (1, 2, 3, 5, 7, …) = (A001401 in [6], 354 in [5])
P̂_{3} = (1, 2, 3, 4, 6, …) = (A008748 in [6])

and

Q̂_{1} = (1, 2, 4, 6, 9, …) = quarter-squares sequence (A002620 in [6], 105 in [5])
Q̂_{2} = (1, 2, 3, 5, 7, …) = (A001840 in [6], 207 in [5])
Q̂_{3} = (1, 2, 3, 4, 6, …) = (A001972 in [6], 208 on [5]).

These typify families defined for k ≥ 1 by

P̂_{k}(n) = P̂_{k}(n − 1) + ⌊\frac{n + k − 1}{k}⌋,  (7)
Q̂_{k}(n) = Q̂_{k}(n − 1) + ⌊\frac{n + k + 1}{k + 1}⌋,  (8)

for n ≥ 1, where P̂_{k}(0) = Q̂_{k}(0) = 1. For k = 1, the recurrence (7) gives P̂_{1}(n) = P̂_{1}(n−1)+n, whence by induction,

P̂_{1}(n) = P_{1}(n) − n.  (9)

Also, equation (7) implies that P̂_{k} is the sequence obtained by arranging in increasing order the numbers in the set

{1} ∪ {P_{k}(n) + i(n + 1) + 1 : 0 ≤ i ≤ k − 1, n ≥ 1}.  (10)

Likewise, equation (8), or alternatively the identity

Q̂_{k}(n) = P̂_{k+1}(n + 1) − 1,  (11)

can be used to prove that the sequence Q̂_{k} results by ordering the numbers in the set

{1} ∪ {Q_{k}(n) + in + i − 1 : 0 ≤ i ≤ k, n ≥ 1}.  (12)

The sequences Q̂_{k}, for k ≥ 2, count certain restricted partitions called denumerants in [2, pp. 108-124] and [5]. References listed in [6] and [5] lead to extensive literature on the sequences P_{k} and Q_{k}. However, observations of relationships (e.g., Theorem 4) between P_{k} and P̂_{k} (and between Q_{k} and Q̂_{k}) to be proved in section 2 may be new.

As a final introductory note, interspersions are closely related to fractal sequences; see [7] for a list of references. Thus, results proved below for interspersions (hence dispersions) could to be stated in terms of fractal sequences.

2 Rank Sequences

In this section, the word rank refers to the ordinary less-than-or-equal relation, ≤ (not the θ-dependent relation ≺ defined in section 1, which will be considered further in section 4.) Recall from section 1 that for rational θ, the multiset S_{θ} in (3) contains repeated elements, so that an element may have more than one rank.

Suppose θ > 0 and n ≥ 0. The minrank sequence of θ, denoted by m_{θ}, is defined by

m_{θ}(n) = least h such that n has rank h in S_{θ},

and the maxrank sequence of θ, denoted by M_{θ}, is defined by

M_{θ}(n) = greatest h such that n has rank h in S_{θ}.

If θ is a positive integer, then the lower self-rank sequence of θ is defined by

ℓ_{θ}(n) = m_{θ}(θn),

and the upper self-rank sequence of θ, by

L_{θ}(n) = M_{θ}(θn).

As L_{θ} is clearly the sequence r_{θ} of section 1, we shall henceforth write it as r_{θ}. Of course, m_{θ} = M_{θ} (and ℓ_{θ} = r_{θ}) if and only if θ is irrational.

For any real θ > 0,

r_{θ}(n) = #{(i, j) : i + jθ ≤ nθ}.

Consider the set of (i, j) satisfying (n − 1)θ < i + jθ ≤ nθ, or equivalently, (n − j − 1)θ < i ≤ (n − j)θ. There is one such i for j = n, and for j = 0, 1, …, n − 1, the number of such i is ⌊(n − j)θ⌋ − ⌊(n − j − 1)θ⌋ . Summing gives a simple recurrence

r_{θ}(n) = r_{θ}(n − 1) + ⌊nθ⌋ + 1  (13)

for n ≥ 1, from which follows

r_{θ}(n) = n + 1 + ∑_{i=1}^{n} ⌊iθ⌋ .  (14)

Alternatively, we may write

r_{θ}(n) = #{(i, j) : i + jθ ≤ nθ}
= #{(i, j) : j ≤ n − i/θ},

so that the numbers j to be counted are 0, 1, 2, …, ⌊n − i/θ⌋ , for i = 0, 1, …, ⌊nθ⌋ , and

r_{θ}(n) = ∑_{i=0}^{⌊nθ⌋}(1 + ⌊n − i/θ⌋)

= ⌊nθ⌋ + 1 + ∑_{i=0}^{⌊nθ⌋} ⌊n − i/θ⌋ .  (15)

(Equations much like (14) and (15) appear in [4]; the sequence r_{3/2} is A077043 in [6].)

Clearly,

M_{θ}(n) = M_{1/θ}(n/θ) = r_{1/θ}(n).  (16)

If θ is rational, write θ = c/d, where c and d are relatively prime numbers in N. Then there are a total of ⌊n/c⌋+1 pairs (i, j) satisfying i+jθ = n, so that there are M_{θ}(n)−(⌊n/c⌋+1) pairs (i, j) satisfying i + jθ < n. Consequently,

m_{c/d}(n) = M_{c/d}(n) − ⌊n/c⌋ = r_{d/c}(n) − ⌊n/c⌋ .  (17)

Table 1. Sequences associated with θ = 2

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ S_{θ}(n) & 0 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 4 & 5 & 5 & 5 \\ m_{θ}(n) & 1 & 2 & 3 & 5 & 7 & 10 & 13 & 17 & 21 & 26 & 31 & 37 \\ M_{θ}(n) & 1 & 2 & 4 & 6 & 9 & 12 & 16 & 20 & 25 & 30 & 36 & 42 \\ ℓ_{θ}(n) & 1 & 3 & 7 & 13 & 21 & 31 & 43 & 57 & 73 & 91 & 111 & 133 \\ r_{θ}(n) & 1 & 4 & 9 & 16 & 25 & 36 & 49 & 64 & 81 & 100 & 121 & 144 \end{matrix}

As suggested by Table 1, the self-rank sequences of a positive integer, k, are, loosely speaking, the sequences P_{k} and Q_{k} in section 1. A more precise statement of this connection takes the form of Theorem 2.

Theorem 2.1 Suppose θ ∈ N. The upper self-rank sequence of θ is given by

r_{θ}(n) = P_{θ}(n), n ≥ 0.

The lower self-rank sequence of θ is given by

ℓ_{θ}(n) = Q_{θ−1}(n), n ≥ 0, if θ ≥ 2,
ℓ_{1}(n) = P̂_{1}(n), n ≥ 0.

Proof: Suppose n ≥ 0. Putting ⌊iθ⌋ = iθ in (14) gives

r_{θ}(n) = n + 1 + θ ∑_{i=0}^{n} i.
= P_{θ}(n), by (4).

As the rank of the first occurrence of θn in S_{θ}, the number ℓ_{θ}(n) is easily obtained from r_{θ}(n), the total number of occurrences of θn being n + 1; thus

ℓ_{θ}(n) = r_{θ}(n) − n = P_{θ}(n) − n.

In case θ ≥ 2, we therefore have ℓ_{θ}(n) = Q_{θ−1}(n), by (6), and if θ = 1, then ℓ_{θ}(n) = P̂_{1}(n), by (9). □

Theorem 2.2 Suppose θ is an integer ≥ 2. If n ≥ 0, then

M_{θ}(n) = r_{1/θ}(n) = Q̂_{θ−1}(n),  (18)
m_{1/θ}(n) = Q_{θ−1}(n),  (19)
M_{1/θ}(n) = P_{θ}(n),  (20)
m_{θ}(n) = P̂_{θ}(n).  (21)

Proof: That M_{θ}(n) = r_{1/θ}(n) has already been established. Equations (14) and (8) give

r_{1/θ}(n) = r_{1/θ}(n − 1) + ⌊\frac{n}{θ}⌋ + 1 and Q̂_{θ−1}(n) = Q̂_{θ−1}(n − 1) + ⌊\frac{n}{θ}⌋ + 1,

showing that the sequences r_{1/θ} and Q̂_{θ+1} have a common recurrence relation. As they also have identical initial terms, (18) follows.

Next,

m_{1/θ}(n) = r_{θ}(n) − n, by (17)
= P_{θ}(n) − n, by Theorem 2
= Q_{θ−1}(n) by (6), and (18) is proved.

Further,

M_{1/θ}(n) = r_{θ}(n), by (12)
= P_{θ}(n), by Theorem 2, so that (19) holds,

and

m_{θ}(n) = r_{1/θ}(n) − ⌊n/θ⌋ , by (17)
= Q̂_{θ−1}(n) − ⌊n/θ⌋ , by (18)
= P̂_{θ}(n + 1) − 1 − ⌊n/θ⌋, by (11)
= P̂_{θ}(n), by (7).  □

Theorems 4 and 5 show the manner in which the sequences P_{k}, Q_{k}, P̂_{k}, Q̂_{k} are related to minrank and maxrank sequences. We turn next toward Theorem 6, which establishes that two of the sequences are partial complements of the other two. A preliminary example may be helpful. We begin by writing the complement P_{2}^{∗} of P_{2} in labeled rows of consecutive integers:

S_{0}:  2 3
S_{1}:  5 6 7 8
S_{2}:  10 11 12 13 14 15
S_{3}:  17 18 19 20 21 22 23 24
⋮

Two equally spaced numbers from S_{n} are boxed. These numbers, one can easily check, taken together and preceded by 1, form the first partial complement of P_{2}. By equation (7), they also form the sequence P̂_{2}. We generalize this method in the next proof.

Theorem 2.3 Suppose k ≥ 1. The 1st partial complement of P_{k} is P̂_{k}, and the 1st partial complement of Q_{k} is Q̂_{k}.

Proof: The complement P_{k}^{∗} of P_{k} consists of segments S_{n} of k(n + 1) consecutive integers, given by

S_{n} = {P_{k}(n) + 1, P_{k}(n) + 2, …, P_{k}(n + 1) − 1}

for n ≥ 0. Thus, the initial segment S_{0} consists of the k numbers 2, 3, …, k + 1, for which we have

tP_{k}(h) = h + 1 = P̂_{k}(h) for 1 ≤ h ≤ k.

(Recall that tr denotes the first partial complement of a sequence r; the notation tr(h) abbreviates (tr)(h).) As the number k + 2 is not in P_{k}^{∗}, we have from S_{1} the k + 1 numbers

k + 3, k + 5, …, 3k + 1

satisfying

tP_{k}(k + 1) = k + 3,
tP_{k}(k + 3) = k + 5,
⋮
tP_{k}(3k − 1) = 3k + 1 = P_{k}(2) − 2.

In order to extend these patterns to represent the appropriate numbers in each segment S_{n}, let

s_{n,j} = P_{k}(n) + 1 + (j − 1)(n + 1), for 1 ≤ j ≤ k, n ≥ 0,

and arrange these in segments of length k + 1 :

Table 2. The numbers s_{n,j}

\begin{matrix}s_{0,1} = 2 & s_{0,2} = 3 & … & s_{0,k} = k + 1 \\ s_{1,1} = k + 3 & s_{1,2} = k + 5 & … & \begin{matrix}s_{1,k} = 3k + 1 \\ = P_{k}(2) − 2 \end{matrix} \\ s_{2,1} = P_{k}(2) + 1 & s_{2,2} = P_{k}(2) + 4 & … & \begin{matrix}s_{2,k} = P_{k}(2) + 3k − 2 \\ = P_{k}(3) − 3 \end{matrix} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ s_{n,1} = P_{k}(n) + 1 & s_{n,2} = P_{k}(n) + n + 2 & … & \begin{matrix}s_{n,k} = P_{k}(n) + (k − 1)n + k + 1 \\ = P_{k}(n + 1) − n − 1 \end{matrix} \\ ⋮ & ⋮ & ⋮ & ⋮ \end{matrix}

The numbers in the following tableau satisfy the chain of equations defining first partial complement:

\begin{matrix}tP_{k}(1) = s_{0,1} & tP_{k}(s_{0,1}) = s_{0,2} & … & tP_{k}(s_{0,k−1}) = s_{0,k} \\ tP_{k}(s_{0,k}) = s_{1,1} & tP_{k}(s_{1,1}) = s_{1,2} & … & tP_{k}(s_{1,k−1}) = s_{1,k} \\ tP_{k}(s_{1,k}) = s_{2,1} & … & … & … \end{matrix}  (22)

In order to confirm that the sequence tP_{k} has the values indicated by (22), these equations must be proved:

(i) tP_{k}(s_{n,k}) = s_{n+1,1} for n ≥ 0, as in column 1;
(ii) tP_{k}(s_{n,j}) = s_{n,j+1} for 1 ≤ j ≤ k − 1, n ≥ 0, as in columns 2 to k.

We begin with (ii). Within S_{n} lie the consecutive integers

s_{n,j}, s_{n,j} + 1, …, s_{n,j+1}.

Inductively, the first of these is tP_{k}(s_{n,j−1}), so that in P_{k}^{∗}, these integers are indexed as indicated by the top row of the next array:

\begin{matrix}s_{n,j−1} & s_{n,j−1} + 1 & s_{n,j−1} + 2 & … & s_{n,j−1} + n + 1 = s_{n,j} \\ s_{n,j} & s_{n,j} + 1 & s_{n,j} + 2 & … & s_{n,j} + n + 1 = s_{n,j+1} \end{matrix}

In other words, because the integers in both rows are consecutive, the inductively assumed relation tP_{k}(s_{n,j−1}) = s_{n,j} implies tP_{k}(s_{n,j}) = s_{n,j+1}.

Now regarding (i), we modify (22) to obtain

\begin{matrix}s_{n,k−1} & … & s_{n,k−1} + n & s_{n,k−1} + n + 1 = s_{n,k} \\ s_{n,k} & … & s_{n,k} + n & s_{n,k} + n + 2 = s_{n+1,1} \end{matrix}

The point here is that the integers in row 1 are consecutive, but that those in row 2, consecutive up to the penultimate term, skip over the number s_{n,k} + n + 1 = P_{k}(n).

As indicated by Table 2, tP_{k} is the sequence having initial term 1 and difference sequence consisting of k 1s followed by k 2s followed by k 3s, and so on. The same characterization holds, by (7), for the sequence P̂_{k}. Therefore, P̂_{k} = tP_{k}.

We turn now to the proposition that the 1st partial complement of Q_{k} is Q̂_{k}. The complement Q_{k}^{∗} of Q_{k} consists of segments T_{n} of (k +1)(n+1)−2 consecutive integers, given by

T_{n} = {Q_{k}(n) + 1, Q_{k}(n) + 2, …, Q_{k}(n + 1) − 1}

for n ≥ 0. The method of proof used above for P_{k} is P̂_{k} applies to these segments, leading to the conclusion, via (8), that Q̂_{k} = tQ_{k}. □

3 Farey trees

In section 1, it is proved that if θ is a positive irrational number, then ttr_{θ} = r_{θ}, or equivalently, that the dispersion A_{θ} is transposable. In case θ ∈ N, the sequences r_{θ} and r_{1/θ} are those discussed in section 2. Here in section 3, we consider r_{θ} when θ is a rational number and introduce certain limiting sequences, to be denoted by r_{θ}^{−}. In section 4, we outline a possible proof that the only sequences r satisfying the equation ttr = r are of the forms r_{θ} and r_{θ}^{−}.

Suppose n ≥ 1. The set F_{n} of Farey fractions of order n consists of the rational numbers c/d for which 0 ≤ c ≤ d, 1 ≤ d ≤ n, and c and d are relatively prime. For example, the Farey fractions of order 5 are

0, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, 1.

The numbers in F_{n}, taken consecutively as endpoints, determine a partition of the interval [0, 1); for example, for n = 5, the subintervals are

[0, \frac{1}{5}), [\frac{1}{5}, \frac{1}{4}), [\frac{1}{4}, \frac{1}{3}), [\frac{1}{3}, \frac{2}{5}), [\frac{2}{5}, \frac{1}{2}), [\frac{1}{2}, \frac{3}{5}), [\frac{3}{5}, \frac{2}{3}), [\frac{2}{3}, \frac{3}{4}),[\frac{3}{4}, \frac{4}{5}), [\frac{4}{5}, 1).  (23)

The connection between Farey fractions and sequences r_{θ} is indicated by the following example: for 0 ≤ θ < 1, the number r_{θ}(5) has one of the ten values

6, 7, 8, 9, 10, 12, 13, 14, 15, 16

according to which of the intervals in (23) contains θ.

Corresponding to successive sets F_{n}, we show six levels of the 0-Farey tree, which represents all the sequences r_{θ} for which θ ∈ [0, 1) :

[figure: 1; 2; 3; 4; 4; 5; 6; 7; 5; 6; 7; 9; 10; 11; 6; 7; 8; 9; 10; 12; 13; 14; 15; 16]

Level n consists of |F_{n}| numbers, ranging from n + 1 to P̂_{1}(n). When progressing from level n to level n + 1, a branching occurs at a number if and only if the corresponding n-level interval contains a fraction (in reduced form) having denominator n + 1. For example, if θ ∈ [1/5, 1/4) then r_{θ}(8) = 13, in level 8 of the Farey tree. The fraction 2/9 lies in [1/5, 1/4), so that a branching occurs at 13:

r_{θ}(9) = \{ \begin{matrix}15 & if θ ∈ [1/5, 2/9) \\ 16 & if θ ∈ [2/9, 1/4). \end{matrix} .

It is easy to adapt the Farey tree for numbers θ′ in an interval ⌊h, h + 1), where h is a positive integer; viz., equation (14) yields

r_{θ}′(n) = r_{θ}(n) + h ( \begin{matrix}n + 1 \\ 2 \end{matrix} ) ,  (24)

where θ = θ′ − h, so that the desired tree, which we call the h-Farey tree, results by adding n(n + 1)/2 to the n-level nodes of the Farey tree, for all n ≥ 0. It follows from (24) that in the h-Farey tree at level n the numbers range from P_{h}(n) up to Q_{h}(n).

The set of infinite paths from 1 down through a Farey tree are of three types:

(i) paths that eventually stay left
(ii) paths that eventually stay right
(iii) all other paths.

The description, “paths that eventually stay left,” applies to any path such that, after some level in a Farey tree, every time a branching occurs, the path takes the left branch, and likewise for “paths that eventually stay right”.

In order to interpret these paths as representations of three kinds of sequences r_{θ}, recall that each node x of a Farey tree corresponds to an interval ⌊u, w). If x connects to only one successor, y, in the next level, then y corresponds to the same interval, ⌊u, w). The only other possibility is that x is a branching node, meaning that x has two successors, y and z, in the next level, and that there is a rational number v such that y ∈ ⌊u, v) and z ∈ ⌊v, w).

Clearly then, paths of type (i) represent r_{θ} when θ is a rational number, and the property, “eventually stay left” corresponds to θ lying in the interval ⌊θ, w) for every w.

Next, consider an eventually-stay-right path. From some node on, the corresponding intervals are of the form ⌊v_{m}, w) where (v_{m}) is a nondecreasing sequence of rationals with rational limit w. The sequence corresponding to these intervals, which we denote by r_{(w−)}, is therefore given by

r_{(w−)} = lim_{m→∞}r_{v_{m}}.  (25)

For example, r_{(2−)} = Q_{1} (whereas r_{2} = P_{2}).

Paths of type (iii) represent r_{θ} when θ is an irrational number, the limit point of a nest of intervals ⌊u_{m}, w_{m}) having rational endpoints.

Theorem 3.1 Suppose θ = c/d, where c and d in N are relatively prime. Then

r_{(c/d−)}(n) = r_{d/c}(n) − ⌊n/c⌋ .  (26)

Proof: Clearly (26) holds for n = 0. Suppose n ≥ 1, and let

μ = min{kd/c − ⌊kd/c⌋ : 1 ≤ k ≤ n, c ∤ k}.  (27)

Let p, q in N be relatively prime satisfying d/c − p/q < μ. (That is, the interval [p/q, c/d) is of the form [v_{m}, w) used for (25) to define r_{(c/d−)}.) Then

r_{(c/d−)}(n) = r_{p/q}(n)
= n + 1 + ⌊p/q⌋ + ⌊2p/q⌋ + ⋯ + ⌊np/q⌋ .  (28)

By (27),

⌊kp/q⌋ = \{ \begin{matrix}⌊kd/c⌋ & if c ∤ kd; \\ ⌊kd/c⌋ − 1 & if c | kd \end{matrix}

for 1 ≤ k ≤ n. As c and d are relatively prime, the values of k for which c | kd are c, 2c, …, ⌊n/c⌋ c, so that (28) gives

r_{(c/d−)}(n) = n + 1 + ⌊d/c⌋ + ⌊2d/c⌋ + ⋯ + ⌊nd/c⌋ − ⌊n/c⌋
= r_{d/c}(n) − ⌊n/c⌋ , by (14).  □

4 Rank Arrays and the Family F

Throughout section 4, the word rank refers to the order relation ≺ except where otherwise indicated. (The relation ≺, dependent on rational θ, is defined in section 1 on the set of ordered pairs (i, j), i ≥ 0, j ≥ 0.)

Theorem 4.1 Suppose θ = c/d, where c and d in N are relatively prime. Then the 1st partial complement of r_{θ} is given by

tr_{θ}(n) = m_{θ}(n) = r_{1/θ}(n) − ⌊n/c⌋ .  (29)

Proof: The sequence tr_{θ} is row 0 of A_{θ}, so that tr_{θ}(n) is the rank of (n, 0), for all n ≥ 0. This means that tr_{θ}(n) is the rank of the first occurrence of the number n when the numbers in S_{θ} are ranked under ≤ . In other words, tr_{θ}(n) = m_{θ}(n), where m_{θ} is the minrank sequence of section 2. Thus, (29) follows from (17). □

Corollary 4.1 Suppose θ = c/d, where c and d in N are relatively prime. Then the 1st partial complement of r_{θ} is given by

tr_{θ}(n) = r_{(θ−)}(n)  (30)

for n ≥ 0.

Proof: This is an obvious consequence of Theorems 5 and 6. □

Lemma 4.1 Suppose r ∈ R and n_{1} ∈ N. Then there exists n_{0} in N such that if s in R satisfies s(n) = r(n) for n = 0, 1, …, n_{0}, then s^{∗}(n) = r^{∗}(n) for n = 1, 2, …, n_{1}.

Proof: Let n_{0} be the least n for which r(n) > r^{∗}(n_{1}). The numbers r^{∗}(1), r^{∗}(2), …, r^{∗}(n_{1}) are then uniquely determined by the numbers r(0), r(1), …, r(n_{0}), as the former simply occupy in increasing order the positions not occupied by the latter in the list 1, 2, 3, …, r(n_{0}) of consecutive integers. □

Lemma 4.2 Suppose r ∈ R and n′ ∈ N. Then there exists n_{0} in N such that if s in R satisfies s(n) = r(n) for n = 0, 1, …, n_{0}, then ts(n) = tr(n) for n = 0, 1, …, n′.

Proof: Let n_{1} be the number such that tr(n′) = r^{∗}(n_{1}). The numbers tr(n) for n = 0, 1, …, n′ are among, and are uniquely determined by, the numbers r^{∗}(n) for n = 1, 2, …, n_{1}. Let n_{0} be as in Lemma 10, so that the numbers tr(n) for n = 0, 1, …, n′ are uniquely determined by the numbers r(n) for n = 0, 1 …, n_{0}. □

Corollary 4.2 Suppose θ = c/d, where c and d in N are relatively prime. Then

ttr_{θ} = r_{θ}.  (31)

Proof: Suppose n_{0} and n_{1} are positive integers. By Corollary 9, there exist c′ and d′, relatively prime in N, such that d′/c′ < d/c and

tr_{c/d}(n) = r_{d′/c′}(n) for n = 0, 1, …, n_{0}.  (32)

It might be tempting to say that we apply t to (32) to get

ttr_{c/d}(n) = tr_{d′/c′}(n) for n = 0, 1, …, n_{0},

but this mistake overlooks the meaning of the notation tr(n) as (tr)(n), not t(r(n)). Instead, we can, in accord with Lemma 11, and do, take n_{0} large enough that (32) implies

ttr_{c/d}(n) = tr_{d′/c′}(n) for n = 0, 1, …, n_{1}.  (33)

Let γ and δ, relatively prime in N, satisfy γ/δ > c/d and

r_{γ/δ}(n) = r_{c/d}(n) for n = 0, 1, …, n_{1}.  (34)

By Corollary 9, there exist c′′ and d′′, relatively prime in N, such that c′′/d′′ < c′/d′ and

tr_{d′/c′}(n) = r_{c′′/d′′}(n) for n = 0, 1, …, n_{1}.  (35)

As c′/d′ > c/d, we can and do choose c′′ and d′′ so that c′′/d′′ > c/d and c′′/d′′ > γ/δ. Then by (33)-(35),

ttr_{c/d}(n) = r_{c′′/d′′}(n)
= r_{c/d}(n) for n = 0, 1, …, n_{1}.

As n_{1} is arbitrary, (31) follows. □

Corollaries 9 and 12 extend Corollary 3 from the case that θ is irrational to the case that θ is any positive real number. In other words, r_{θ} is in the family F of fixed points under the operator tt, or, in yet other words, the 1st partial complement of the 1st partial complement of any r_{θ} is r_{θ} itself. The next corollary identifies additional members of F, and in section 5, we conjecture that there are no others.

Corollary 4.3 Suppose θ = c/d, where c and d in N are relatively prime. Then

ttr_{(θ−)} = r_{(θ−)}.  (36)

Proof: Suppose n_{0,} n_{1}, and n_{2} are positive integers. Let c′ and d′, relatively prime in N, satisfy

r_{c′/d′}(n) = r_{(θ−)}(n) for n = 0, 1, …, n_{0} and
ttr_{c′/d′}(n) = ttr_{(θ−)}(n) for n = 0, 1, …, n_{1}.

By Corollary 12, we can, and do, choose n_{0} and n_{1} large enough that

ttr_{(θ−)}(n) = r_{c′/d′}(n) for n = 0, 1, …, max{n_{0}, n_{1}, n_{2}}.

As n_{0}, n_{1}, n_{2} are arbitrarily large, (36) follows. □

For any array A = {a(i, j)}, let T A denote the transpose, {a(j, i)}, of A. Let A_{(θ−)} denote the interspersion whose column 0 is the sequence r_{(θ−)}. Membership in the family F can now be stated in terms of transposable interspersions:

Corollary 4.4 Suppose θ is a positive real number. Then T A_{(θ−)} = A, T T A_{θ} = A_{θ}, and T T A_{(θ−)} = A_{(θ−)}.

Proof: If θ is a positive integer, the three asserted equations follow from Theorem 4, as in this case, r_{θ} and r_{(θ−)} are P_{θ} and P̂_{θ}, (and r_{1/θ} and r_{(1/θ−)} are Q_{θ} and Q̂_{θ}). For irrational, θ, we have A_{(θ−)} = A_{1/θ}, and the proposition follows from Corollary 12. For all other positive θ, the asserted equations follow immediately from Corollaries 9, 12, and 13.

Example 2: The interspersions A_{3/2} and A_{(3/2−)}

\begin{matrix}1 & 2 & 4 & 6 & 9 & … & 1 & 3 & 7 & 12 & 19 & … \\ 3 & 5 & 8 & 11 & 15 & … & 2 & 5 & 10 & 16 & 24 & … \\ 7 & 10 & 14 & 18 & 23 & … & 4 & 8 & 14 & 21 & 30 & … \\ 12 & 16 & 21 & 26 & 32 & … & 6 & 11 & 18 & 26 & 36 & … \\ 19 & 24 & 30 & 36 & 43 & … & 9 & 15 & 23 & 32 & 43 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}

Example 3: The interspersions A_{2/3} and A_{(2/3−)}

\begin{matrix}1 & 3 & 6 & 11 & 17 & … & 1 & 2 & 4 & 7 & 10 & … \\ 2 & 5 & 9 & 15 & 22 & … & 3 & 5 & 8 & 12 & 16 & … \\ 4 & 8 & 13 & 20 & 28 & … & 6 & 9 & 13 & 18 & 23 & … \\ 7 & 12 & 18 & 26 & 35 & … & 11 & 15 & 20 & 26 & 32 & … \\ 10 & 16 & 23 & 32 & 42 & … & 17 & 22 & 28 & 35 & 42 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}

Theorem 4.2 Suppose θ is a positive real number. Neighboring terms in column j of the rank array A_{θ} satisfy the equation

a(i, j) − a(i − 1, j) = ⌊iθ⌋ + j + 1  (37)

for i ≥ 1, j ≥ 0.

Proof: Suppose i ≥ 1. By (13),

a(i, 0) − a(i − 1, 0) = r_{θ}(i) − r_{θ}(i − 1) = ⌊iθ⌋ + 1.

Thus, equation (37) is equivalent to

ℜ(j, i) − ℜ(j, i − 1) = ℜ(0, i) − ℜ(0, i − 1) + j,  (38)

where ℜ(h, k) denotes the rank of (h, k) under ≺ . Let v = ⌊iθ⌋ . The v ordered pairs (h, k) counted by ℜ(0, i) − ℜ(0, i − 1) we represent as

(0, i − 1) ≺ (h_{1}, k_{1}) ≺ (h_{2}, k_{2}) ≺ ⋯ ≺ (h_{v}, k_{v}) = (0, i).  (39)

Clearly, (39) implies

(1, i − 1) ≺ (h_{1} + 1, k_{1}) ≺ (h_{2} + 1, k_{2}) ≺ ⋯ ≺ (h_{v} + 1, k_{v}) = (1, i).  (40)

It is easy to check that there is exactly one integer q satisfying

(1, i − 1) ≺ (0, i + q) ≺ (1, i),  (41)

namely

q = \{ \begin{matrix}0 & if θ = 1; \\ ⌊1/θ⌋ & otherwise. \end{matrix}

Thus, by (40) and (41), there are v + 1 ordered pairs (h, k), satisfying

(1, i − 1) ≺ (h, k) ≺ (1, i).  (42)

Now if (h, k) is an ordered pair satisfying (42), then either h = 0, so that k = q, or else (h − 1, k) is one of the ordered pairs in (39); thus every (h, k) satisfying (40) is one of the v + 1, so that (37) holds for j = 1.

The method used to get from (39) to (42), namely, adding 1 to all first coordinates and then inserting the sole ordered pair having first coordinate 0, applies inductively, so that (38) and (37) hold for all j ≥ 0. □

Corollary 4.5 Suppose θ is a positive real number. Neighboring terms in column j of the array A_{(θ−)} = {b(i, j)} satisfy the equation

b(i, j) − b(i − 1, j) = ⌈i/θ⌉ + j,  (43)

where ⌈ ⌉ denotes the ceiling function, for i ≥ 1, j ≥ 0.

Proof: Suppose n_{0} ∈ N. Let c′ and d′, relatively prime in N, satisfy

r_{c′/d′}(n) = r_{(θ−)}(n)

for n = 0, 1, …, n_{0}. In the rank array A_{c′/d′} = {a′(i, j)}, each a′(i, j) that is ≤ r_{c′/d′}(n_{0}) has the same position (i, j) that the same number has in A_{(θ−)}; that is, b(i, j) = a′(i, j) for a′(i, j) ranging from 1 up to r_{c′/d′}(n_{0}). By (37),

a′(i, j) = a′(i − 1, j) = ⌊ic′/d′⌋ + j + 1,

so that b(i, j) − b(i − 1, j) − j = ⌊ic′/d′⌋ + 1, showing that

b(i, j) − b(i − 1, j) − j

is invariant of j. Now b(i, 0) = r_{d/c} − ⌊i/c⌋, by (26), so that

b(i, 0) − b(i − 1, 0) = r_{d/c}(i) − r_{d/c}(i − 1) − (⌊i/c⌋ − ⌊(i − 1)/c⌋
= ⌊id/c⌋ + 1 − ⌊i/c⌋ + ⌊(i − 1)/c⌋.

Consequently,

b(i, j) − b(i − 1, j) = ⌊id/c⌋ − ⌊i/c⌋ + ⌊(i − 1)/c⌋ + j + 1,

and it is easy to verify that the right-hand side simplifies as in (43). □

Corollary 4.6 Suppose θ is a positive real number. The terms of the dispersion A_{θ} satisfy the equation

a(i, j) = a(i, 0) + a(0, j) + ij − 1

for i ≥ 0, j ≥ 0.

Proof: By (37),

a(h, j) − a(h − 1, j) = ⌊hθ⌋ + j + 1

for h = 1, 2, …, i. Summing over those values of h gives

a(i, j) = a(0, j) + ⌊θ⌋ + ⌊2θ⌋ + ⋯ + ⌊iθ⌋ + i(j + 1)
= a(0, j) + r_{θ}(i) − i − 1 + i(j + 1), by (13)
= a(i, 0) + a(0, j) + ij − 1.  □

Corollary 4.7 Suppose θ = c/d, where c and c are relatively prime in N. The terms of the dispersion A_{(θ−)} = {b(i, j)} satisfy the equation

b(i, j) = b(i, 0) + b(0, j) + ij + ⌊i/c⌋

for i ≥ 0, j ≥ 0.

Proof: By (43),

b(h, j) − b(h − 1, j) = ⌈h/θ⌉ + j

for h = 1, 2, …, i. Summing over those values of h as in the proof of Corollary 7.2 and simplfying via the identify

⌈x⌉ = \{ \begin{matrix}x & if x is an integer; \\ ⌊x⌋ + 1 & otherwise \end{matrix}

yield the asserted equation. □

5 Convergence

It appears likely that if r ∈ R, then the sequence of sequences,

r, ttr, tt(ttr), …,

whose general term we abbreviate as t^{(2n)}r, converges, and that the limiting sequence is one of the sequences r_{θ} or r_{(θ−)} for some positive real number θ. If so, then the family F of sequences satisfying ttr = r clearly contains no sequences other than those already accounted for.

Proof that (t^{(2n)}r) converges seems elusive. This section offers lemmas which may someday be found useful in a proof but are of independent interest in any case. The items for which proof is sought are then presented as Conjectures 22-26.

Suppose that u and v are sequences in R and that their initial segments of some length are identical Then some initial segments of the complements, u^{∗} and v^{∗}, must be identical. The following lemma provides some insight.

Lemma 5.1 Suppose u and v are sequences in R such that u(i) = v(i) for i = 0, 1, …, n, and u(n + 1) ≥ v(n + 1). Then

u^{∗}(j) = v^{∗}(j) for j = 1, 2, …, v(n + 1) − n − 2.

Proof: For h = 0, 1, …, n, the v(h + 1) − v(h) − 1 numbers v(h) + 1 to v(h + 1) − 1, taken in order, comprise an initial segment of both v^{∗} and u^{∗}. The length of this common segment is

∑_{h=0}^{n}[v(h + 1) − v(h) − 1] = v(n + 1) − n − 2.  □  (44)

Lemma 5.2 Suppose c and d in N are relatively prime. Suppose r ∈ R and that there exists n ≥ 2 such that r(i) = r_{c/d}(i) and r(n + 1) ≥ r_{c/d}(n + 1). Then r^{∗}(j) = r_{c/d}^{∗}(j) for j = 1, 2, …, J, where

J = r_{c/d}(n) + ⌊(n + 1)c/d⌋ − n − 1.  (45)

Proof: In Lemma 19, take u = r and v = r_{c/d}. Then v(n + 1) = r_{c/d}(n + 1) in (44), and (13) implies (45). □

Lemma 5.3 Suppose c and d in N are relatively prime and c > d. Then

r_{c/d}^{∗}(i) = i + 1 for i = 1, 2, …, r_{c/d}(1) − 2,
r_{c/d}^{∗}(r_{c/d}(m) − m + J) = r_{c/d}(m) + J + 1  (46)
for J = 0, 1, …, ⌊(m + 1)c/d⌋ − 1, m = 1, 2, 3, ….  (47)

Proof: Consider the sequence of numbers to which r_{c/d}^{∗} is applied: initially,

1, 2, …, r_{c/d}(1) − 2, followed by
r_{c/d}(m) − m + J, for m = 1 and J = 0, 1, …, ⌊2c/d⌋ − 1,
r_{c/d}(m) − m + J, for m = 2 and J = 0, 1, …, ⌊3c/d⌋ − 1,

and so on. Thus, the sequence in question is the sequence of positive integers. Their images under the function r_{c/d}^{∗} are determined by arranging all the numbers r_{c/d}^{∗}(i) in increasing order. This listing is conveniently broken into segments, first from 1 to r_{c/d}(1) − 1, then from r_{c/d}(1) + 1 to r_{c/d}(2) − 1, and so on. Thus, counting the first segment as segment 1, the (m + 1)st segment, for m ≥ 1, is as given by (46) and (47). □

Conjecture 5.1 Suppose c and d in N are relatively prime. Suppose that r ∈ R and that there exists n ≥ 1 such that r(i) = r_{c/d}(i) for i = 0, 1, …, n, and

r(n + 1) ≥ r_{c/d}(n + 1).  (48)

Then

tr(i) = tr_{c/d}(i) for i = 0, 1, 2, …, ⌊(n + 1)c/d⌋.  (49)

Conjecture 5.2 Continuing, suppose, instead of (48), that

r(n + 1) ≤ r_{c/d}(n + 1) − 2.  (50)

Then

tr(n + 1) = tr_{c/d}(n + 1) − 1.  (51)

Conjecture 5.3 Continuing, suppose, instead of (50), that

r(n + 1) = r_{c/d}(n + 1) − 1.  (52)

Then

tr(n + 1) = tr_{c/d}(n + 1).  (53)

Conjecture 5.4 Continuing, suppose

z(i) = tr_{c/d}(i) for i = 0, 1, …, ⌊(n + 1)c/d⌋

and

z(i + 1) − z(i) ≥ z(i) − z(i − 1)  (54)

for i ≥ ⌊(n + 1)c/d⌋. Then

tz(i) = r_{c/d}(i) for i = 0, 1, 2, …, n + 1.  (55)

Conjecture 5.5 Suppose r ∈ R. Then there exists a positive real number θ such that lim_{n→∞}t^{(2n)}r is one of the sequences r_{θ} and r_{(θ−)}.

Possible method of proof: If r is r_{θ} or r_{(θ−)} for some then θ, then ttr = r by Corollaries 3, 12, and 13. Suppose then that r is not any such r_{θ} or r_{(θ−)}. Let

(γ, δ) = \{ \begin{matrix}(1, 2) & if r(1) = 2; \\ (r(1) − 2, 1) & if r(1) ≥ 3. \end{matrix}

Then r(0) = r_{γ/δ}(0) = 1 and r(1) = r_{γ/δ}(1), so that the set of rational numbers γ/δ satisfying

r(i) = r_{γ/δ}(i) for i = 0, 1, …, m,  (56)

for some m ≥ 1, is not empty. The set of numbers m for which (56) holds for some γ/δ is not unbounded, for if it were, there would be a sequence γ_{m}/δ_{m} having limit θ such that r ∈ {r_{θ}, r_{θ}^{−}}, a contradiction. Let n be the greatest m for which (56) holds, and let c/d, where c and d are relatively prime, be a rational number such that

r(i) = r_{c/d}(i) for 0, 1, 2, …, n.

As r(n + 1) ≠ r_{c/d}(n + 1), one of the inequalities (48), (50), and (52) holds, so that we have cases:

Case 1: r(n + 1) ≥ r_{c/d}(n + 1). If Conjecture 22 is valid, then (49) holds.

Case 2: r(n + 1) ≤ r_{c/d}(n + 1) − 2. If Conjecture 23 is valid, then by (51), the sequences tr_{c/d} and tr satisfy the hypothesis of Conjecture 24 (with tr_{c/d} and tr substituted for r_{c/d} and r, respectively).

Case 3: r(n + 1) = r_{c/d}(n + 1) − 1. If Conjecture 24 is valid, then by (53), the sequences tr_{c/d} and tr satisfy the hypothesis of Conjecture 22 (with tr_{c/d} and tr substituted for r_{c/d} and r, respectively).

Let

r′ = \{ \begin{matrix}tr & if (48) holds; \\ tttr & if (50) holds; \\ tr & if (52) holds. \end{matrix}  (57)

The discussion of the three cases shows that r′ satisfies (48), hence (49), if Conjecture 22 is valid. Let z = r′. It is easy to check that (54) holds (for z = tρ, for every ρ in R). Thus, if Conjecture 25 is valid, then, with reference to (56), the sequence ttttr satisfies

ttttr(i) = r_{c/d}(i) for i = 0, 1, … n, n + 1

(whereas r(n + 1) may not be equal to r_{c/d}(n + 1)), and a proof of Conjecture 26 follows by repeated applications of Conjectures 22-25. It is hoped that someone will prove those conjectures!

The interested reader may wish to use the following website:

http://csserver.evansville.edu/˜ brownie/cgi-bin/transpose.

There, the reader can submit the first ten to thirty terms of a sequence r. The dispersion of the complementary sequence will appear, of which the submitted sequence is the first column. The reader can then request iterations and see, in the successive first columns, initial terms of the sequences tr, ttr, tttr, …

References

[1] John H. Conway and Richard K. Guy, The Book of Numbers, Springer-Verlag, New York, 1996.

[2] Louis Comtet, Advanced Combinatorics, revised and enlarged edition, D. Reidel, Dordrecht, 1974.

[3] Clark Kimberling, Interspersions and dispersions, Proc. Amer. Math. Soc. 117 (1993), 313–321.

[4] Clark Kimberling, Fractal sequences and interspersions, Ars Combinatoria 45 (1997), 157–168.

[5] Stéphanie Petit, editor (2003) Encyclopedia of Combinatorial Structures,

http://pauillac.inria.fr/algo/encyclopedia/index.html .

[6] N. J. A. Sloane, editor (2003), The On-Line Encyclopedia of Integer Sequences,

http://www.research.att.com/~njas/sequences/ .

[7] N. J. A. Sloane, (2003) Classic Sequences In The On-Line Encyclopedia of Integer Sequences: (Part 1:) The Wythoff Array and The Para-Fibonacci Sequence,

http://www.research.att.com/~njas/sequences/classic.html .

2000 Mathematics Subject Classification: Primary 11B36; Secondary 11B25, 11B37. Keywords: central polygonal numbers, dispersion, interspersion, Farey sequence, Farey tree, fractal sequence, partial complement, polygonal numbers, rank array, rank sequence.

(Concerned with sequences \underline{A000124}, \underline{A000217}, \underline{A000290}, \underline{A000326}, \underline{A001401}, \underline{A001840}, \underline{A001844}, \underline{A001972}, \underline{A002061}, \underline{A002620}, \underline{A005448}, \underline{A008748}, \underline{A077043}, \underline{A082152}, \underline{A082153}, \underline{A082154}, \underline{A082155}, \underline{A082156}, \underline{A086270}, \underline{A086271}, \underline{A086272}, \underline{A086273}, \underline{A087465}, \underline{A087466}, \underline{A087467}, \underline{A087468}, \underline{A087469}, \underline{A087470}.)

Received October 14 2003; revised version received January 19 2004. Published in Journal of Integer Sequences, February 18 2004.

Return to Journal of Integer Sequences home page.