Self-Containing Sequences, Fractal Sequences, Selection Functions, and Parasequences

Clark Kimberling Department of Mathematics University of Evansville 1800 Lincoln Avenue Evansville, IN 47722 USA

                      ck6@evansville.edu

Abstract This paper surveys various kinds of ordered sets, with numerous citations to sequences in the On-Line Encyclopedia of Integer Sequences. These ordered sets include self-containing sequences, infinitive sequences, fractal sequences, and parasequences (which are introduced here as a certain type of doubly infinite sequence). Relationships among these are presented, and among more than thirty examples, the Cantor fractal sequence and the Farey fractal sequence are presented. There are several conjectures involving parasequences.

1 Introduction

A sequence that contains itself as a proper subsequence obviously does so infinitely many times. This sort of containment nest is analogous to nested geometric configurations widely known as fractals. In this article, we examine first the class of self-containing sequences, and then, as a subclass, fractal sequences (e.g., [2, 5, 6, 9]).

In Sections 2 and 3, proper self-containing sequences, in which the terms may be arbitrary objects, are shown to be essentially in one-to-one correspondence with certain position arrays consisting of the positive integers, each occurring exactly once. In Section 4, regular selfcontaining sequences and their duals are defined. Section 5 discusses fractal sequences that naturally arise in connection with the Cantor ternary set and the set of Farey fractions.

In Section 6, normalized fractal sequences are introduced, and a description in terms of permutations of sets of the form {1, 2, 3, …, n} is given. Selection functions and parasequences are defined in Section 7, and dense fractal sequences are discussed in Section 8.

2 Self-containing sequences

A self-containing sequence (SCS) is a sequence (a_{n}) that contains a proper subsequence (a_{n_{i}}) that is identical to (a_{n}), i.e.,

a_{n_{i}} = a_{i} for all i in the set ℕ = {1, 2, 3, …} of natural numbers.

Clearly, an SCS properly contains itself infinitely many times:

a_{n_{i}} = a_{i}, a_{n_{i_{j}}} = a_{i_{j}}, · · · .

The terms may be rational numbers or pebbles or indentations along a coastline, but unless otherwise implied, we shall assume that the terms of each SCS belong to ℕ. In that case, a sequence x = (x_{n}) is an infinitive sequence [6] if for every i,

(F1) x_{n} = i for infinitely many n.

For each i, let T (i, j) be the j^{th} index n for which x_{n} = i.

Clearly, a sequence containing every positive integer is an SCS if and only the sequence is an infinitive sequence. Also clearly, if (a_{n_{i}}) is a proper subsequence of an SCS (a_{n}), then the complement of (a_{n_{i}}), meaning the sequence that remains after the terms a_{n_{i}} are removed from (a_{n_{i}}), is also an SCS.

Example 1. Suppose that (a_{n}) is periodic. Then (a_{n}) is an SCS. In particular, (1, 1, 1, …) is an SCS.

Example 2. Let a_{n} be the number of digits occurring from right to left to reach the first 1 in the base-2 representation of n:

(a_{n}) = (1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, …).

This sequence, \underline{A001511} in the On-Line Encyclopedia of Integer Sequences [10], is an SCS known as the ruler function.

3 Position arrays

We shall show that SCSs are in one-to-one correspondence with certain arrays whose terms are in ℕ.

Definition 3. For m ∈ ℕ, let N_{m} = {1, 2, 3, …, m} and N_{∞} = ℕ. Suppose, for (i, j) ∈ N_{m} × ℕ, where 1 ≤ m ≤ ∞, that T = (T (i, j)) is an array that partitions ℕ into a sequence of increasing sequences; i.e., • (P1) if n ∈ ℕ, then n = T (i, j) for some (i, j);

• (P2) for each i, the sequence (T (i, j)) is increasing;

• (P3) if i_{1} < i_{2}, then no term of (T (i_{1}, j)) is a term of (T (i_{2}, j)).

Then T is the position array of an SCS, (a_{n}), defined as follows: a_{n} = i, where i is the index such that n = T (i, j) for some j. Conversely, an SCS (a_{n}) yields a position array, as follows: let i = n and let j be the number of indices h ≤ n such that a_{h} = a_{n}. Then T (i, j) = n.

Example 4. The position array T for the sequence (a_{n}) in Example 2 is given by

T = ( \begin{matrix}1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & ⋯ \\ 2 & 6 & 10 & 14 & 18 & 22 & 26 & 30 & ⋯ \\ 4 & 12 & 20 & 28 & 36 & 44 & 52 & 60 & ⋯ \\ 8 & 24 & 40 & 56 & 72 & 88 & 104 & 120 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

as in \underline{A054582}.

4 Regular sequences and arrays

A position array is a regular position array if it has infinitely many rows and every column is increasing. A proper self-containing sequence is a regular self-containing sequence (RSCS) if its position array is regular. For example, the sequence (a_{n}) in Example 2 is an RSCS.

Clearly if T is regular, then its transpose, T^{∗}, is regular. If (a_{n}) is an RSCS with position array T, then T^{∗} is the position array of an RSCS, which we denote by (a_{n}^{∗}) and call the dual of (a_{n}). As (T^{∗})^{∗} = T, we have ((a_{n}^{∗})^{∗}) = (a_{n}).

Example 5. Let (a_{n}) = \underline{A001511}, as in Example 2 and Example 4. Then

(a_{n}^{∗}) = (1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 7, 4, 8, 1, 9, 5, 10, 3, …) = \underline{A003602}.

The position array of (a_{n}^{∗}), namely the transpose of the array T in Example 4, is given by \underline{A135764}.

Example 6. If (a_{n}) = \underline{A002260}, then (a_{n}^{∗}) = \underline{A004736}.

Example 7. We begin with the definition [6] of signature sequence: for any irrational number r > 0, let

S(r) = {c + dr : c, d ∈ ℕ},

and let (c_{n}(r) + d_{n}(r)r) be the sequence obtained by arranging the elements of S(r) in increasing order. A sequence a is a signature if there exists a positive irrational number r such that a = (c_{n}(r)). In this case, a is the signature of r.

The dual of a signature is also a signature; specifically, if (a_{n}) is the signature of r, then (a_{n}^{∗}) is the signature of r^{−1}. For example, the signature of 2^{1/2} is

(1, 2, 1, 3, 2, 1, 4, 3, 2, 5, 1, 4, 3, 6, 2, 5, 1, 4, 7, 3, 6, 2, 5, 8, 1, …) = \underline{A007336},

with placement array \underline{A283939}, and the signature of 2^{−1/2} is

(1, 1, 2, 1, 2, 3, 1, 2, 3, 1, 4, 2, 3, 1, 4, 2, 5, 3, 1, 4, 2, 5, 3, 1, …) = \underline{A023115}.

5 Fractal sequences

A search of [10] for “fractal sequence” reveals that in recent years, various different kinds of sequences have been called “fractal” and that what many of them have in common is that they are SCSs. In this article, a fractal sequence is a special kind of RSCS defined ([5, 6, 11]) as an infinitive sequence x as in (F1) such that the following two properties also hold:

• (F2) if i + 1 = x_{n}, then there exists m < n such that i = x_{m};

• (F3) if h < i, then for every j, there is exactly one k such that

T (i, j) < T (h, k) < T (i, j + 1),

where T is the placement array of (x_{n}). According to (F2), the first occurrence of each i > 1 in x must be preceded at least once by each of the numbers 1, 2, ⋯, i − 1, and according to (F3), between consecutive occurrences of i in x, each h less than i occurs exactly once.

Examples of fractal sequences are (a_{n}^{∗}) in Example 5 but not (a_{n}), both (a_{n}) and (a_{n}^{∗}) in Example 6, and all signatures, as in Example 7. Other examples [10] are \underline{A003603}, \underline{A022446}, \underline{A022447}, \underline{A023133}, \underline{A108712}, \underline{A120873}, \underline{A120874}, \underline{A122196}, \underline{A125158}.

Example 8. In the unit interval [0, 1], the classical Cantor set is the set of rational numbers whose base-3 representation consists solely of 0’s and 2’s. This Cantor set is sometimes called the prototype of a (geometric) fractal. We shall arrange the numbers of the Cantor set to form an SCS. First, write the numbers, in base 3, as follows:

0; 0, .2; 0, .02, .2; 0, .02, .2, .22; 0, .002, .02, .2, .22; 0, .002, .02, .2, .202, .22; and so on,

and then concatenate those blocks:

c = (0, 0, .2, 0, .02, .2, 0, .02, .2, .22, 0, .002, .02, .2, .22, 0, .002, .02, .2, .202, …).

Writing c as (c_{n}), assign to each n the least h such that c_{h} = c_{n}, so that h is a function of n, which we denote by a_{n}. This Cantor fractal sequence and its associated interspersion are then given by

(a_{n}) = (1, 1, 2, 1, 3, 2, 1, 3, 2, 4, 1, 5, 3, 2, 4, 1, 5, 3, 2, 6, 4, …) = \underline{A088370}.

and

T = ( \begin{matrix}1 & 2 & 4 & 7 & 11 & 16 & 22 & ⋯ \\ 3 & 6 & 9 & 14 & 19 & 26 & 33 & ⋯ \\ 5 & 8 & 13 & 18 & 24 & 31 & 40 & ⋯ \\ 10 & 15 & 21 & 28 & 35 & 44 & 55 & ⋯ \\ 12 & 17 & 23 & 30 & 39 & 48 & 58 & ⋯ \\ 20 & 27 & 34 & 43 & 53 & 64 & 75 & ⋯ \\ 25 & 32 & 41 & 50 & 61 & 72 & 85 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) = \underline{A131966}.

Example 9. Here we introduce a Farey fractal sequence, much in the spirit of Example 8, as this sequence consists of positions of entries among the Farey fractions, which are represented by the following list:

order 1: \frac{0}{1} \frac{1}{1}

order 2: \frac{0}{1} \frac{1}{2} \frac{1}{1}

order 3: \frac{0}{1} \frac{1}{3} \frac{1}{2} \frac{2}{3} \frac{1}{1}

order 4: \frac{0}{1} \frac{1}{4} \frac{1}{3} \frac{1}{2} \frac{2}{3} \frac{3}{4} \frac{1}{1}

order 5: \frac{0}{1} \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} \frac{1}{1}.

Concatenating those gives the SCS

(\frac{0}{1}, \frac{1}{1}, \frac{0}{1}, \frac{1}{2}, \frac{1}{1}, \frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1}, …) .

Next, replace each fraction in this sequence by the position in which it first appears, where each distinct predecessor is counted only once, getting

( \begin{matrix}1 & 2 \\ 1 & 3 & 2 \\ 1 & 4 & 3 & 5 & 2 \\ 1 & 6 & 4 & 3 & 5 & 7 & 2 \\ 1 & 8 & 6 & 4 & 9 & 3 & 19 & 5 & 7 & 11 & 2 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \end{matrix} ) .  (1)

Concatenating gives the Farey fractal sequence:

(1, 2, 1, 3, 2, 1, 4, 3, 5, 2, 1, 6, 4, 3, 5, 7, 2, 1, 8, 6, 4, 9, 3, 10, 5, 7, …) = \underline{A131967},

with position array (i.e., the associated interspersion)

( \begin{matrix}1 & 3 & 6 & 11 & 18 & ⋯ \\ 2 & 5 & 10 & 17 & 28 & ⋯ \\ 4 & 8 & 14 & 23 & 35 & ⋯ \\ 7 & 13 & 21 & 33 & 48 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) = \underline{A131968}.

6 Normalization and placement sequences

Every fractal sequence a = (a_{n}) can be separated into blocks each of which begins with 1 and includes 1 only at the beginning, as in Example 2. Given such blocks, three things can happen. We shall make certain modifications in all three cases.

First, if a_{2} ≠ 1, place an initial 1 before a_{1} (which is necessarily 1), so that the new sequence begins with 1, 1. Second, a block may be repeated, as in \underline{A023115} in Example 7, where the block (1, 2, 3) occurs twice. In such a case, retain only the first of repeated blocks in each case where repetition occurs. To keep things simple, we abuse notation by letting (a_{n}) denote the sequence (still a fractal sequence) which remains after the first two steps have been applied to the original sequence a.

Third, we arrange for the m^{th} block to be of length m. To begin, the 1st block already consists of 1 by itself. The second block is necessarily a permutation (a_{2}, a_{3}, …, a_{m}) of (1, 2, …, m−1) for some m ≥ 2, where a_{2} = 1. Replace this block with the following blocks, consecutively if m ≥ 4:

(a_{2}, a_{3}), (a_{2}, a_{3}, a_{4}), (a_{2}, a_{3}, a_{4}, a_{5}), …, (a_{2}, a_{3}, a_{4}, a_{5}, …, a_{m}).

Repeat the procedure on the next block, (a_{m+1}, a_{m+2}, …, a_{m+q}), where a_{m+1} = 1, and continue in this manner inductively. The resulting sequence is the normalized fractal sequence of a, denoted by N (a). Although possibly N (a) ≠ a, clearly infinitely many of the blocks of N (a) are also blocks of a, so that in this sense, a is equivalent to N (a).

For all m ∈ ℕ, the m^{th} block of N (a) is a permutation of (1, 2, …, m), so that the (m + 1)^{st} block arises from the m^{th} according to the placement of m + 1 among the available m + 1 places. Let P(a), called the placement sequence of a (and of N (a) and any other fractal sequence b such that N (b) = N (a)), denote the sequence whose m^{th} term is the position of m in the m^{th} block of N (a).

Example 10. Let a be the signature of 2^{1/2}, as in Example 7:

a = (1, 2, 1, 3, 2, 1, 4, 3, 2, 5, 1, 4, 3, 6, 2, 5, 1, 4, 7, 3, 6, 2, 5, 8, 1, …);
N (a) = (1, 1, 2, 1, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 5, 1, 4, 3, 6, 2, 5, 1, 4, 7, 3, 6, 2, …);
P(a) = (1, 2, 2, 2, 5, 4, 3, 8, …).

Example 11. Let a be the Cantor fractal sequence, as in Example 8. In this case, N (a) = a, and

P(a) = (1, 2, 2, 4, 2, 5, 4, 4, 8, 2, 7, 4, 11, 4, …).

Example 12. Let a be the Farey fractal sequence, as in Example 9. Then

N (a) = (1, 1, 2, 1, 3, 2, 1, 4, 3, 2, 1, 4, 3, 5, 2, 1, 6, 4, 3, 5, 2, 1, 6, 4, 3, 5, …);
P(a) = (1, 2, 2, 2, 4, 2, 6, 2, 5, 7, 10, 2, …).

Regarding Examples 11 and 12, in each case the transpose of the placement array is not regular, so that (a_{n}^{∗}), although an SCS, is not a fractal sequence, and N (a^{∗}) and P(a^{∗}) are undefined. Recalling that a placement array T belongs to a fractal sequence if and only if T is a dispersion (or equivalently, an interspersion), it is natural to seek a characterization of dispersions T for which T^{∗} is also a dispersion, so that, for example, (a_{n}^{∗}) is a fractal sequence. Such a characterization is given in [8].

Example 13. Using the sequence

P = (1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, …) = \underline{A004526}

as a placement sequence yields the normalized fractal sequence

a = (1, 1, 2, 1, 3, 2, 1, 3, 4, 2, 1, 3, 5, 4, 2, 1, 3, 5, 6, 4, 2, 1, 3, 5, 7, 6, 4, 2, 1, …),

this being \underline{A194959}, which is related to the Smarandache permutation sequence, \underline{A004741}, in a close and obvious manner.

Example 14. Using the sequence

P = (1, 2, 2, 4, 3, 6, 4, 8, 5, 10, 6, 12, 7, 14, 8, 16, 9, …)

(essentially \underline{A029578}) as a placement sequence yields the normalized fractal sequence

a = (1, 1, 2, 1, 3, 2, 1, 3, 2, 4, 1, 3, 5, 2, 4, 1, 3, 5, 2, 4, 6, 1, 3, 5, 7, 2, 4, 6, 1, …),

which is closely related by \underline{A087467}.

Examples 13 and 14 illustrate the fact that if P = (p_{n}) is a sequence satisfying p_{1} = 1 and 2 ≤ p_{n} ≤ m for all m ≥ 2, then P is the placement sequence of a normalized fractal sequence. Further examples of this sort are shown at \underline{A194959}.

Referring to (F1) in Section 2, the array T is called an interspersion [5, 6].

Clearly, if T is the interspersion of a normalized fractal sequence then each diagonal of T is a permutation of consecutive integers. Specifically, the n^{th} diagonal is a permutation of these integers:

\binom{n}{2} + 1, \binom{n}{2} + 2, …, \binom{n + 1}{2}.

7 Selection functions and parasequences

Definition 15. Suppose that S ⊂ ℕ. A function f : S × S → {0, 1} is a selection function if the following conditions hold:

(1) for some i and j, f(i, 1) = 0 and f(1, j) = 0;

(2) for every (i, j), if f(i, j) = 0 then f(m, i) = 0 for infinitely many m;

(3) for every (i, j), if f(i, j) = 0 then f(j, n) = 0 for infinitely many n.

We shall make use of the minimal excludant function, denoted by mex and defined [3] for any proper subset S of ℕ by the formula

mex(S) = least positive integer not in S.

Definition 16. Let f be a selection function. Let s_{0} = (1), and let

m_{1} = mex{m : f(m, 1) = 0};  n_{1} = mex{n : f(1, n) = 0};  s_{1} = (m_{1}, 1, n_{1});
m_{2} = mex{m : f(m, m_{1}) = 0}; n_{2} = mex{n : f(n_{1}, n) = 0}; s_{2} = (m_{2}, m_{1}, 1, n_{1}, n_{2}).

Define m_{k} and n_{k} inductively in this manner for all k ≥ 1. The f-parasequence is the doubly infinite sequence

(…, m_{3}, m_{2}, m_{1}, 1, n_{1}, n_{2}, n_{3}, …).  (2)

We introduce two representations for a parasequence as a sequence. The first is the concatenation sequence of f, obtained by concatenating the successive blocks in Definition 16; that is,

(1, m_{1}, 1, n_{1}, m_{2}, m_{1}, 1, n_{1}, n_{2}, m_{3}, m_{2}, m_{1}, 1, n_{1}, n_{2}, n_{3}, …).  (3)

Note that (3) is an SCS, and if g(i, j) = 1 − f(i, j), then g may be a selection function. Generally, the g-parasequence is not merely the reversal of the f-parasequence.

The second representation we call the riffle sequence for f (and for the f-parasequence):

(1, m_{1}, n_{1}, m_{2}, n_{2}, m_{3}, n_{3}, m_{4}, n_{4}, m_{5}, n_{5}, …).  (4)

Example 17. Let

f(i, j) = \begin{cases}0, & if i = j; \\ 0, & if i is even and j is odd; \\ 0, & if i, j are even and i > j; \\ 0, & if i, j are odd and i < j; \\ 1, & otherwise. \end{cases}

Then

s_{0} = (1), s_{1} = (2, 1, 3), s_{2} = (4, 2, 1, 3, 5), …,

so that f is the limit, (…, 8, 6, 4, 2, 1, 3, 5, 7, …). The concatenation sequence of f is the Smarandache permutation sequence,

\underline{A004741} = (1, 2, 1, 3, 4, 2, 1, 3, 5, 6, 4, 2, 1, 3, 5, 7, 8, 6, 4, 2, …),

which is alternatively defined [10] as the concatenation of the sequences

(1, 3, …, 2n − 1, 2n, 2n − 2, …, 2).

The riffle sequence for f is \underline{A000027} = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …).

Example 18.

f(i, j) = \begin{cases}0, & if i + j is a prime; \\ 1, & otherwise. \end{cases}

The selection function f can be represented in a table, of which five rows are shown here:

\begin{matrix}i/j & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & ⋯ \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & ⋯ \\ 2 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & ⋯ \\ 3 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & ⋯ \\ 4 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & ⋯ \\ 5 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 1 & ⋯ \end{matrix}

From this table, extended, we read successive blocks

1; 2, 1, 4; 3, 2, 1, 4, 7; 8, 3, 2, 1, 4, 7, 6; 5, 8, 3, 2, 1, 4, 7, 6, 11;

leading to the following parasequence:

(…, 17, 12, 5, 8, 3, 2, 1, 4, 7, 6, 11, 18, 13, …).

The sum of each consecutive pair is a prime, as in \underline{A055265}. It is left to the reader to decide if every positive integer is present and if every odd prime occurs as one of the sums.

The following Mathematica program was used to generate the parasequence in Example 18, and it can be can easily be modified to yield other parasequences:

z = 100; s[1] = {0};
f[i_, j_] := If[PrimeQ[i + j], 0, 1];
m[k_] := m[k] = Select[Range[z], f[#, First[s[2 k - 1]]] == 0
&& ! MemberQ[s[2 k - 1], #] & , 1];
s[q_] := s[q] = If[EvenQ[q], Join[m[q/2], s[q - 1]],
Join[s[q - 1], n[(q - 1)/2]]];
n[k_] := n[k] = Select[Range[z], f[Last[s[2 k]], #] == 0
&& ! MemberQ[s[2 k], #] &, 1];
k = 1; While[k < 100, s[k]; k++]; s[k]

Example 19.

f(i, j) = \begin{cases}0, & if i + j = n(n + 1)/2 for some n ∈ ℕ; \\ 1, & otherwise. \end{cases}

The f-parasequence is

(…, 8, 7, 3, 12, 9, 6, 4, 2, 1, 5, 10, 11, 17, 19, 26, 29, 16, …).

We conjecture that every positive integer is in this parasequence and that if n > 1, then the n^{th} triangular number is the sum of at least one pair of consecutive terms. Example 20.

f(i, j) = \begin{cases}0, & if i + j = n^{2} for some n ∈ ℕ; \\ 1, & otherwise. \end{cases}

The f-parasequence is

(…, 11, 5, 4, 21, 15, 10, 6, 3, 1, 8, 17, 19, 30, 34, 2, 7, …).

We conjecture that every positive integer is in this parasequence and that if n > 1, then n^{2} is the sum of at least one pair of consecutive terms. Example 21.

f(i, j) = \begin{cases}0, & if i and j are relatively prime; \\ 1, & otherwise. \end{cases}

The f-parasequence is

(…, 23, 14, 17, 10, 9, 11, 6, 5, 2, 1, 3, 4, 7, 8, 13, 12, 19, 15, 16, …).

We conjecture that every positive integer is in this parasequence. Example 22. f(i, j) = ⌊\{i\sqrt{2}\} + \{j\sqrt{2}\}⌋. where \{\} denotes fractional part. The fparasequence is

(…, 29, 7, 17, 11, 13, 6, 8, 4, 3, 1, 5, 2, 10, 9, 15, 16, 20, 18, 22, 14, …).

We conjecture that every positive integer is in this parasequence. Example 23.

f(i, j) = \begin{cases}0, & if |i − j| is a prime; \\ 1, & otherwise. \end{cases}

The f-parasequence is

(…, 18, 20, 17, 15, 13, 8, 10, 7, 5, 3, 1, 4, 2, 9, 6, 11, 14, 12, 19, 16, 21, 24, …).

We conjecture that every positive integer is in this parasequence.

Theorem 24. Let α be an irrational number greater than 1, with convergents p_{i}/q_{i} and intermediate convergents p_{i,j}/q_{i,j}, (given by

\frac{p_{i,j}}{q_{i,j}} = \frac{jp_{i+1} + p_{i}}{jq_{i+1} + q_{i}} , j = 1, 2, …, a_{i+2} − 1),

as indicated here:

⋯ < \frac{p_{i}}{q_{i}} < ⋯ < \frac{p_{i,j}}{q_{i,j}} < \frac{p_{i,j+1}}{q_{i,j+1}} < ⋯ < \frac{p_{i+2}}{q_{i+2}} < ⋯ if i is even;  (5)
⋯ > \frac{p_{i}}{q_{i}} > ⋯ > \frac{p_{i,j}}{q_{i,j}} > \frac{p_{i,j+1}}{q_{i,j+1}} > ⋯ > \frac{p_{i+2}}{q_{i+2}} > ⋯ if i is odd;  (6)

(The convergents and intermediate convergents in (5) are called lower, as they converge from below to α; those in (6) are upper, as they converge from above to α.) Let

f(i, j) = \begin{cases}0, & if \{iα\} < \{jα\}; \\ 1, & otherwise. \end{cases}

The f-parasequence is

… m_{k}, m_{k−1}, …, m_{1}, 1, n_{1}, n_{2}, …, n_{k} …,

where 1, m_{1}, m_{2}, … are the denominators of the lower convergents and intermediate convergents to α, and 1, n_{1}, n_{2}, … are the denominators of the upper convergents and intermediate convergents to α.

Proof. A short version follows: apply induction to the indices of the convergents and intermediate convergents, using theorems [7] stated here: The best lower approximates to α are the even-indexed convergents and intermediate convergents to α, and the best upper approximates to α are the odd-indexed convergents and intermediate convergents to α. (Here, the words even and odd pertain only to the index i, not j.

Example 25.

f(i, j) = \begin{cases}0, & if \{ie\} < \{je\}; \\ 1, & otherwise. \end{cases}

The f-parasequence is

(…, 1001, 465, 394, 323, 252, 181, 110, 39, 7, 3, 2, 1, 4, 11, 18, 25, 32, 71, …).

These numbers are the denominators of Farey fraction approximations to e, as in \underline{A119015}. They are also the denominators of the intermediate convergents to e (including the convergents); see \underline{A006259} and \underline{A007677}.

Example 26. Let τ = (1 + \sqrt{5})/2, the golden ratio, and

f(i, j) = \begin{cases}0, & if \{iτ\} < \{jτ\}; \\ 1, & otherwise. \end{cases}

The f-parasequence is

(…, 610, 233, 89, 34, 13, 5, 2, 1, 3, 8, 21, 55, 144, 377, 987, …),

consisting of the Fibonacci numbers, \underline{A000045}, including bisections \underline{A001519} and \underline{A001906}. In this extreme example, as a result of the fact that the continued fraction for τ consists solely of 1s, there are no intermediate convergents. The numbers to the left of 1 in the parasequence are the denominators of the lower convergents to τ, and they are also the numerators of the upper convergents. The numbers to the right of 1 are denominators of the upper convergents, and also the numerators of the lower convergents. Specifically,

\frac{1}{1} < \frac{3}{2} < \frac{8}{5} < \frac{21}{13} < ⋯ < τ < ⋯ < \frac{13}{8} < \frac{5}{3} < \frac{2}{1}.

As suggested by Examples 25 and 26, it is natural to regard a parasequence as a concatenation of a left sequence and a right sequence; referring to (2), the left sequence is (1, m_{1}, m_{2}, m_{3}, …) and the right sequence is (1, n_{1}, n_{2}, n_{3}, …).; (We include 1 in both sequences.) In the next theorem and examples, the two sequences are interestingly related to each other.

Theorem 27. Let

f(i, j) = \begin{cases}0, & if i + j = 2^{h−1} for some h ∈ ℕ; \\ 1, & otherwise. \end{cases}

The parasequence of f is (…, 43, 21, 11, 5, 3, 1, 7, 9, 23, 41, …). Here, the left sequence, (1, 3, 5, 11, …), is given by m_{k} = J(k + 2), where J = \underline{A001045}, the Jacobsthal sequence. The right sequence (with 1 included),

(1, 7, 9, 23, …) = \underline{A083582},

is given by n_{k} =\underline{A083582}(k + 1).

Proof. The sequence (\underline{A001045}(k)), for k ≥ 2, is given by the recurrence relation

a(k) = a(k − 1) + 2a(k − 2),  (7)

with initial values a(2) = 1 and a(3) = 3. The sequence (\underline{A083582}(k)), for k ≥ 1, is given by

(7) with initial values a(1) = 1 and a(2) = 7.

Following Definition 15, let s_{0} = (1). Then

m_{1} = least i ∉ s_{0} such that f(i, 1) = 0, so m_{1} = 3 and s_{1} = (3, 1);
n_{1} = least j ∉ s_{1} such that f(1, j) = 0, so n_{1} = 7 and s_{2} = (3, 1, 7);
m_{2} = least i ∉ s_{2} such that f(i, 3) = 0, so m_{2} = 5 and s_{3} = (5, 3, 1, 7).

So far, we have established that (m_{k}) and (n_{k}) have the required initial values. We turn now to showing that both sequences satisfy (7). For arbitrary k ≥ 3, we have, inductively,

m_{k−1} = least i such that i + m_{k−2} is the least positive power of 2
that is not in {1, 2, …, 2^{k−1}},

so that

m_{k−1} = 2^{k} − m_{k−2}.  (8)

Likewise, m_{k} = 2^{k+1} − m_{k−2}, so that

2^{k+1} = m_{k} + m_{k−1}
= 2m_{k−1} + 2m_{k−2} by (8).

Consequently, m_{k} = m_{k−1} + 2m_{k−2}, as desired, so that m_{k} = \underline{A001045}(k + 2) for k ≥ 1. Meanwhile,

n_{k−1} = least j such that n_{k−2} + j is the least positive power of 2
that is not in {1, 2, …, 2^{k}},

so that n_{k−1} = 2^{k+1} − n_{k−2}, and likewise, n_{k} = 2^{k+2} − n_{k−1}. It follows, as before, that n_{k} = n_{k−1} + 2n_{k−2}, so that n_{k} = \underline{A083582}(k + 1) for k ≥ 1.

Example 28.

f(i, j) = \begin{cases}0, & if i + j = n^{3} for some n ∈ ℕ; \\ 1, & otherwise. \end{cases}

The left sequence is \underline{A015518}, and the right, \underline{A084222} (except for signs).

Example 29.

f(i, j) = \begin{cases}0, & if i + j is a Fibonacci number (\underline{A000045}); \\ 1, & otherwise. \end{cases}

The left sequence is \underline{A000045}, and the right, \underline{A008346}.

Example 30.

f(i, j) = \begin{cases}0, & if i + j is a Lucas number other than 2 (\underline{A000045}); \\ 1, & otherwise. \end{cases}

The left sequence is \underline{A000032}, and the right, \underline{A098600}.

Example 31.

f(i, j) = \begin{cases}0, & if i + j = ⌊n(1 + \sqrt{5})/2⌋ for some n ∈ ℕ (\underline{A000201}); \\ 1, & otherwise. \end{cases}

The left sequence is \underline{A279934}, and the right, \underline{A279933}.

Example 32.

f(i, j) = \begin{cases}0, & if i + j = \binom{2n}{n} for some n ∈ ℕ (\underline{A000984}); \\ 1, & otherwise. \end{cases}

The left sequence is \underline{A349554}, and the right, \underline{A054108}.

8 Dense fractal sequences

A fractal sequence (a_{n}) is dense if for every i ∈ ℕ, there exists h ≥ 2 such that

a_{i} < a_{i+h} < a_{i+1} or a_{i+1} < a_{i+h} < a_{i}.  (9)

A distinctive property of a dense fractal sequences is the opposite of a distinctive property of a parasequence (and its representations as a concatenation or riffle as described in Section 7); viz., if numbers m and n occur consecutively in a parasequence, then they occur consecutively throughout, whereas in a dense fractal sequence, the number of terms between m and n increases without bound.

Lemma 33. Suppose that n ∈ ℕ and that r is a positive irrational number. Let c_{n} be the number of numbers i + jr, where i ∈ ℕ and j ∈ ℕ, such that

n < i + jr < n + 1.  (10)

Then c_{n} = ⌊\frac{n}{r}⌋ − ⌊\frac{r−1}{r}⌋.

Proof. For each i, one of the inequalities (9) holds if and only if

\frac{n − i}{r} < j < \frac{n − i + 1}{r},

and there are exactly

⌊\frac{n − i}{r}⌋ − ⌊\frac{n − i + 1}{r}⌋

such numbers j. Summing over all i for which

⌊\frac{n − i + 1}{r}⌋ ≥ 1

gives

c_{n} = ∑_{i=1}^{⌊n+1−r⌋} ⌊\frac{n − i}{r}⌋ − ⌊\frac{n − i + 1}{r}⌋

= ⌊\frac{n}{r}⌋ − ⌊\frac{r − 1}{r}⌋ .

Corollary 34. In Lemma 33, if r > 1, then c_{n} = ⌊\frac{n}{r}⌋.

Examples for this corollary are \underline{A019446} for r = (1 + \sqrt{5})/2 and \underline{A049474} for r = \sqrt{2}.

Example 35. To construct a dense fractional in a simple combinatorial manner, start with 1, and then surround it using 2, 3 like this: 2, 1, 3. Then surround those three numbers using 4, 5, 6, 7 like this: 4, 2, 5, 1, 6, 3, 7, and so on. Concatenate to obtain the sequence

(1, 2, 1, 3, 4, 2, 5, 1, 6, 3, 7, 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, …) = \underline{A131987}.

Example 36. Suppose that (a_{n}(r)) is the signature of an irrational number r > 1, as in Example 7. We shall show that the fractal sequence (a_{n}(r)) is dense. For each index i, either a_{i} < a_{i+1} or else a_{i} > a_{i+1}. The proof in the second case is essentially the same as that for the first, so we shall assume that a_{i} < a_{i+1}. Taking n = ⌈2r(i + 2)⌉, there are, by Lemma 33, more that 2i + 1 numbers u + vr such that

i < u + vr < i + 1.  (11)

Since r > 1, each interval of length 1 contains at most one number i + vr, for fixed i, so that by (11), there is at least one value of u greater than 1. The number h = u − i then satisfies a_{i} < a_{i+h} < a_{i+1}, with h ≥ 2.

Example 37. Here, initial terms 1,2 are isolated by 3,4 to form 1423, and then 1,4,2,3 are isolated by 5,6,7,8 to form 18472635, and so on. Concatenating these blocks gives

(1, 1, 2, 1, 2, 3, 1, 3, 2, 4, 1, 4, 2, 3, 5, 1, 4, 2, 6, 3, 5, 1, 4, 7, 2, 6, 3, …) = \underline{A132223}.

The corresponding dense normalized fractal sequence is

(1, 1, 2, 1, 2, 3, 1, 4, 2, 3, 1, 4, 2, 3, 5, 1, 4, 2, 6, 3, 5, 1, 4, 2, 6, 4, …) = \underline{A132224},

with placement sequence

(1, 2, 3, 2, 5, 4, 3, 2, 9, 8, 7, 6, 5, 4, 3, 2, 17, 16, 15, 14, 13, 12, …) = \underline{A132226},

formed by concatenating blocks 12, 32, 5432, 98765432, …, where each new block s_{h} after the block 32 is the concatenation s_{h−1}s_{h−2}.

Example 38. Suppose that r is a positive irrational number. For n ∈ ℕ, arrange in increasing order the fractional parts {hr} for h = 1, 2, …, n:

{h_{1}r} < {h_{2}r} < ⋯ < {h_{n}r}.  (12)

From (12), form the block (h_{1}, h_{2}, …, h_{n}), a permutation of (1, 2, …, n), and proceed as in Section 6 to form a fractal sequence. For r = \sqrt{2}, the sequence is \underline{A054073}, with placement sequence \underline{A054072}. For r = (1 + \sqrt{5})/2, the sequence is \underline{A054065}, for which the placement sequence is John Conway’s “left budding sequence”:

(1, 1, 3, 2, 1, 5, 3, 8, 5, 2, 9, 5, 1, …) = \underline{A019587}.

The dense normalized fractal sequence obtained from \underline{A054065} is

(1, 1, 2, 1, 3, 2, 1, 3, 2, 4, 1, 3, 5, 2, 4, 1, 6, 3, 5, 2, 4, 1, 6, 3, 5, 2, 7, 4, …) = \underline{A132283},

with associated interspersion

( \begin{matrix}1 & 2 & 4 & 7 & 11 & ⋯ \\ 3 & 6 & 9 & 14 & 20 & ⋯ \\ 5 & 8 & 12 & 18 & 24 & ⋯ \\ 10 & 15 & 21 & 28 & 36 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) = \underline{A132284}.

References

[1] Anonymous, Doubly infinite sequences, available at

    https://oeis.org/wiki/Doubly_infinite_sequences.

[2] B. Cloitre, Chemins dans un tableau arithmétique. Available at http://www.

    les-mathematiques.net/articles/Chemins.pdf.

[3] A. S. Fraenkel and U. Peled, Harnessing the unwieldy MEX function, in R. J. Nowakowski, ed., Games of No Chance 4, MSRI Publ., Vol. 63, Cambridge University Press, 2015, pp. 77–94.

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

[5] C. Kimberling, Numeration systems and fractal sequences, Acta Arith. 73 (1995) 103– 117.

[6] C. Kimberling, Fractal sequences and interspersions, Ars Combin. 45 (1997) 157–168.

[7] C. Kimberling, Best lower and upper approximates to irrational numbers, Elem. Math. 52 (1997) 122–126.

[8] C. Kimberling and J. E. Brown, Partial complements and transposable dispersions, J. Integer Sequences 7 (2004) Article 04.1.6.

[9] L. Levine, Fractal sequences and restricted Nim, Ars Combin. 80 (2006) 113–127.

[10] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2022. Available

    at https://oeis.org.

[11] E. Weisstein, MathWorld, Infinitive sequence. Available at http://mathworld.

    wolfram.com/InfinitiveSequence.html.

2010 Mathematics Subject Classification: Primary 11B85. Keywords: Cantor fractal sequence, dense fractal sequence, dispersion, Farey fractal sequence, fractal sequence, infinitive sequence, interspersion, normalized fractal sequence, parasequence, self-containing sequence, selection function, signature sequence.

(Concerned with sequences \underline{A000027}, \underline{A000032}, \underline{A000045}, \underline{A000201}, \underline{A000984}, \underline{A001045}, \underline{A001511}, \underline{A001519}, \underline{A001622}, \underline{A001906}, \underline{A002260}, \underline{A003602}, \underline{A003603}, \underline{A004526}, \underline{A004736}, \underline{A004741}, \underline{A006259}, \underline{A007336}, \underline{A007677}, \underline{A008346}, \underline{A015518}, \underline{A019446}, \underline{A019587}, \underline{A022446}, \underline{A022447}, \underline{A023115}, \underline{A023133}, \underline{A029578}, \underline{A049474}, \underline{A054065}, \underline{A054108}, \underline{A054582}, \underline{A055265}, \underline{A083582}, \underline{A084222}, \underline{A087467}, \underline{A088370}, \underline{A007677}, \underline{A108712}, \underline{A098600}, \underline{A119015}, \underline{A120873}, \underline{A120874}, \underline{A122196}, \underline{A125158}, \underline{A131966}, \underline{A131967}, \underline{A131968}, \underline{A131987}, \underline{A132223}, \underline{A132224}, \underline{A132226}, \underline{A132283}, \underline{A132284}, \underline{A135764}, \underline{A194959}, \underline{A279933}, \underline{A279934}, \underline{A283939}, \underline{A349554}.)

Received July 20 2021; revised version received January 6 2022. Published in Journal of Integer Sequences, January 28 2022.

Return to Journal of Integer Sequences home page.