Permutations of ℕ Generated by Left-Right Filling Algorithms

F. M. Dekking Delft University of Technology Faculty EEMCS P. O. Box 5031 2600 GA Delft The Netherlands

                  F.M.Dekking@math.tudelft.nl

Abstract We give an in-depth analysis of an algorithm, introduced by Kimberling in the On-Line Encyclopedia of Integer Sequences, that generates permutations of the natural numbers. It turns out that each example of such a permutation in the Encyclopedia is completely determined by some 3-automatic sequence.

1 Introduction

Let L : ℕ → ℕ and R : ℕ → ℕ be two functions. A left-right filling procedure is an algorithm that may produce an permutation Π of ℕ as follows:

First set Π(1) := 1. Then for each n ≥ 2, set

\begin{cases}Π(n − L(n)) := n, & if Π(n − L(n)) is not yet defined; \\ Π(n + R(n)) := n, & otherwise. \end{cases}

Here we say “may produce” because Π(n) might not be defined for all n.

The simplest example of a pair (L, R) generating a permutation is given by

L(n) = 1, R(n) = 1 for all n.

We find consecutively that

n = 2 ⇒ Π(2 + R(2)) = Π(3) = 2,
n = 3 ⇒ Π(3 − L(2)) = Π(2) = 3,
n = 4 ⇒ Π(4 + R(4)) = Π(5) = 4,

and in general Π(2n) = 2n + 1, Π(2n + 1) = 2n. So this pair (L, R) generates the selfinverse permutation of ℕ given by sequence \underline{A065190} in the On-Line Encyclopedia of Integer Sequences (OEIS) [5].

An example of a pair (L, R) that does not generate a permutation is given by

L(n) = n − 1, R(n) = n − 1 for all n.

Here only the odd arguments of Π become defined: Π(2n + 1) = n + 1 for all n ≥ 0. In this paper, we will be mainly occupied with the pair of functions given by

L(n) = ⌊\frac{n}{2}⌋, R(n) = ⌊\frac{n}{2}⌋ for all n.

This pair was introduced by Kimberling in the On-Line Encyclopedia of Integer Sequences [5] in entry \underline{A026136}. The permutation it generates is

Π = 1, 3, 2, 7, 9, 4, 5, 15, 6, 19, 21, 8, 25, 27, 10, 11, 33, 12, 13, 39, 14, 43, 45, 16, 17, 51, 18, …

We will establish a one-to-one connection of this permutation with a 3-automatic sequence that permits one to prove a number of properties of this Π. We shall next analyze other left-right filling algorithms in a similar way, establishing many relations between the corresponding permutations.

2 Left and right functions

2.1 The pair L(n) = ⌊n/2⌋, R(n) = ⌊n/2⌋.

When L(n) = ⌊n/2⌋, R(n) = ⌊n/2⌋, there are four possibilities for the value of Π(n). Splitting into the cases L(n) = R(n) = n/2 for n even, and L(n) = R(n) = (n − 1)/2 for n odd, one arrives at the following four cases

(I) Π(n) odd, Π(n) > n, Π(n) = 2n − 1;
(II) Π(n) even, Π(n) > n, Π(n) = 2n;
(III) Π(n) odd, Π(n) < n, Π(n) = (2n + 1)/3;
(IV) Π(n) even, Π(n) < n, Π(n) = 2n/3.

We say Π(n) is of type (I), etc., when we are in case (I), etc.

Lemma 1. If the left-right filling procedure is at step 2n, then the natural numbers 1, 2, …, n have already been assigned a Π-value.

Proof. By induction. This is trivially true for n = 1. If we are at step 2(n+1), then 1, 2, …, n have been assigned a Π-value by the induction hypothesis. The number n + 1 be assigned a Π-value in steps 1, 2, …, 2n. If not, then it was assigned the value Π(n + 1) = 2n + 1 at step 2n + 1, since

2n + 1 − ⌊\frac{2n + 1}{2}⌋ = 2n + 1 − n = n + 1.

We use the following terminology. If Π(n − L(n)) = n at step n in the algorithm, then we say we ‘go to the left’, whereas if Π(n + R(n)) = n, then we say we ‘go to the right’.

Lemma 1 excludes the possibility of going to the left at step 2n, so it implies the following proposition.

Proposition 2. For all n ≥ 1, Π(3n) = 2n.

The next task is to determine the type of all entries of Π.

Theorem 3. Let n, k be natural numbers. Then

(a) Π(n) never has type (II).

(b) If n = 3k then Π(n) has type (IV).

(c) If n = 3k + 2 then Π(n) has type (I).

(d) If n = 3k + 1 then Π(n) has type (I) if Π(k + 1) has type (I) and Π(n) has type (III) if Π(k + 1) has type (III) or type (IV).

Proof.

(a) Π(n) is never equal to 2n, since either n has been assigned the value 2n − 1 at step 2n − 1: 2n − 1 − ⌊(2n − 1)/2⌋ = n, or n has been assigned a smaller value at an earlier step.

(b) is a rephrasing of Proposition 2.

(c) follows from part (a) and the observation that both 2n + 1 = 2(3k + 2) + 1 = 6k + 5 and 2n = 6k + 4 are not divisible by 3.

(d) Type (II) is excluded by part (a), and type (IV) is excluded because 2n = 6k + 2 is not divisible by 3. So Π(n) is either 2n − 1 (type (I)), or (2n + 1)/3 (type III). Here (2n + 1)/3 = (6k + 3)/3 = 2k + 1. But 2k + 1 = 2(k + 1) − 1 was already assigned to k + 1 if Π(k + 1) has type(I), so then Π(n) = 2n − 1 has type (I). Conversely, if Π(k + 1) has not type (I), i.e., type (III) or type (IV), then Π(n) has type (III).

Theorem 3 can easily be transformed into the following statement.

Theorem 4. Let σ on the monoid {1, 3, 4}^{∗} be the monoid morphism given by

σ(1) = 114, σ(3) = 314, σ(4) = 314.

Let s = 1141143141141143143141143141141143141141 … be the fixed point of σ with prefix equal to 1. Then s_{n} = 1 iff Π(n) has type (I), s_{n} = 3 iff Π(n) has type (III), and s_{n} = 4 iff Π(n) has type (IV).

This result has several corollaries. A first corollary is a partial self-similarity property of the permutation Π.

Theorem 5. Let E be the sequence of natural numbers defined by

E(3n + 1) = 9n + 1, E(3n + 2) = 9n + 4, E(3n + 3) = 9n + 6 for n ≥ 0.

Then Π(E(n)) = 3Π(n) − 2 for n ≥ 0.

Proof. We split the proof in the three cases for the argument modulo 3 of E. Note that

σ^{2}(1) = 114114314, σ^{2}(3) = 314114314, σ^{2}(4) = 314114314.

From this expression we can read off the type of Π(9n + 1), Π(9n + 4) and Π(9n + 6), using Theorem 3.

• The case Π(9n + 1):

– Subcase Π(9n + 1) has type (I): From Theorem 3 we then obtain that Π(3n + 1) also has type (I). We find Π(9n + 1) = 2(9n + 1) − 1 = 18n + 1, which is equal to 3Π(3n + 1) − 2 = 3(2(3n + 1) − 1) − 2 = 18n + 1.

– Subcase Π(9n + 1) has type (III): From Theorem 3 we then obtain that Π(3n + 1) has type (III), or type (IV). However, type (IV) does not occur, since 3n + 1 is not divisible by 3. We then find Π(9n + 1) = (2(9n + 1) + 1)/3 = 6n + 1, which is equal to 3Π(3n + 1) − 2 = 3((2(3n + 1) + 1)/3) − 2 = 6n + 1.

• The case Π(9n + 4): In this case both Π(9n + 4) and Π(3n + 2) have type (I). We then find Π(9n + 4) = 2(9n + 4) − 1 = 18n + 7, which is equal to 3Π(3n + 2) − 2 = 3(2(3n + 2) − 1) − 2 = 18n + 7.

• The case Π(9n + 6): In this case both Π(9n + 6) and Π(3n + 3) have type (IV). We then find Π(9n + 6) = 2(9n + 6)/3 = 6n + 4, which is equal to 3Π(3n + 3) − 2 = 3(2(3n + 3)/3) − 2 = 6n + 4.

Application 6. Consider the OEIS sequence \underline{A026186}, with name “a(n) = (1/3)*(s(n) + 2), where s(n) is the n-th number congruent to 1 mod 3 in \underline{A026136}”, and with data

“1, 3, 2, 7, 9, 4, 5, 15, 6, 19, 21, 8, 25, 27, 10, 11, … ” .

In the comments we find: “Is this a duplicate of \underline{A026136}? - R. J. Mathar, Aug 26 2019”, and “A026186(n) = A026136(n) for n <= 10∧7. - Sean A. Irvine, Sep 19 2019”.

Translated to our setting, we have to show that

(a) Π(n) ≡ 1 (mod 3) ⇔ n ∈ {E(k) : k ≥ 0}; and

(b) \frac{1}{3}(Π(E(n) + 2) = Π(n) for n ≥ 0.

One side of (a) follows from Theorem 4, and the formula for σ^{2} above:

Π(9n + 2) has type (I) ⇒ Π(9n + 2) = 2(9n + 2) − 1 = 18n + 3 ≡ 0 (mod 3);
Π(9n + 3) has type (IV) ⇒ Π(9n + 3) = 2(9n + 3)/3 = 6n + 2 ≡ 2 (mod 3);
Π(9n + 5) has type (I) ⇒ Π(9n + 5) = 2(9n + 5) − 1 = 18n + 9 ≡ 0 (mod 3);
Π(9n + 7) has type (III) ⇒ Π(9n + 7) = (2(9n + 7) + 1)/3 = 6n + 5 ≡ 2 (mod 3);
Π(9n + 8) has type (I) ⇒ Π(9n + 8) = 2(9n + 2) − 1 = 18n + 15 ≡ 0 (mod 3);
Π(9n + 9) has type (IV) ⇒ Π(9n + 9) = 2(9n + 9)/3 = 6n + 6 ≡ 0 (mod 3).

Since all six are not equal to 1 modulo 3, but they are equal for the remaining three cases modulo 9 by Theorem 5, this proves part (a).

Part (b) follows directly from Theorem 5.

We call an element Π(n) of the permutation Π a record if Π(n) > Π(k), for all k < n. Let R_{pos} = \underline{A026138} be the sequence of positions of records in Π:

R_{pos} = 1, 2, 4, 5, 8, 10, 11, 13, 14, 17, 20, 22, 23, 26, 28, 29, 31, 32, 35, 37, 38, 40, 41, …

The sequence R_{rec} = \underline{A026139} of records in Π defined by R_{rec}(n) = Π(R_{pos}(n)) is given by

R_{rec} = 1, 3, 7, 9, 15, 19, 21, 25, 27, 33, 39, 43, 45, 51, 55, 57, 61, 63, 69, 73, 75, 79, 81, …

In the sequel we write Δx for the sequence of first differences (x(n + 1) − x(n)) of a sequence x.

Proposition 7. Let τ be the morphism given by τ(1) = 12, τ(2) = 132, τ(3) = 1332. Let t = 12132121332132 ⋯ be the unique fixed point of τ. Then ΔR_{pos} = t, and ΔR_{rec} = 2t.

Proof. The records in Π are exactly given by the Π(n) of type (I). So the positions of these records are given by the positions of 1 in s. To obtain these, one considers the return words of the word 1 in s. These are 1, 14 and 143. Since

σ(1) = 1 14, σ(14) = 1 143 14, σ(143) = 1 143 143 14,

the induced derived morphism is equal to τ, where we code the return words by their lengths. Since we code the return words by their lengths, this gives that R_{pos}(n+1)−R_{pos}(n) = t(n), where t is the unique fixed point of τ. The second equation follows from the fact that all records are of type (I), and so

R_{rec}(n+1)−R_{rec}(n) = Π(R_{pos}(n+1))−Π(R_{pos}(n)) = 2R_{pos}(n+1)−1−(2R_{pos}(n)−1) = 2t(n).

Remark 8. The proposition states that \underline{A026141} = \frac{1}{2}ΔR_{rec} = t. Also, let \underline{A026140}(n) := \frac{1}{2}(R_{rec}(n) − 1) = 0, 1, 3, 4, 7, 9, 10, 12, 13, 16, 19, 21, 22, . . .. It is easy to see that Proposition 7 gives Δ\underline{A026140} = t, again.

2.2 Changing the rules: Π_{even}

In sequence \underline{A026172} in the OEIS, Kimberling varies the left-right filling procedure by adding the condition that one always goes to the right if n is even. The resulting permutation of ℕ is denoted by Π_{even}. We still have L(n) = ⌊n/2⌋ = R(n), but the procedure is changed to a(n + R(n)) = n if n even or a(n − L(n)) already defined, else a(n − L(n)) = n.

Surprisingly, changing the procedure in this way does not change the permutation.

Proposition 9. Π_{even} = Π.

Proof. This follows immediately from Lemma 1.

Proposition 9 implies the equality of many pairs of sequences in the OEIS, such as

\underline{A026136} = \underline{A026172},
\underline{A026137} = \underline{A026173},
\underline{A026138} = \underline{A026174},
\underline{A026139} = \underline{A026175},
\underline{A026141} = \underline{A026176},
\underline{A026184} = \underline{A026208},
\underline{A026188} = \underline{A026212},
\underline{A026182} = \underline{A026206}, and
\underline{A026186} = \underline{A026210}.

These equalities have been implemented in the OEIS at the beginning of 2020 (based on a preprint of the present paper), declaring one of the two sequences in each pair as ‘dead’.

2.3 Changing the rules: Π_{odd}

Still L(n) = ⌊n/2⌋ = R(n), but now one always goes to the right if n is odd; see \underline{A026177}: a(n + R(n)) = n if n odd or a(n − L(n)) already defined, otherwise a(n − L(n)) = n. The resulting permutation of ℕ is denoted by Π_{odd}. Thus

Π_{odd} = 1, 4, 2, 3, 10, 12, 5, 16, 6, 7, 22, 8, 9, 28, 30, 11, 34, 36, 13, 40, 14, 15, 46, 48, 17, 52, 18, …

One verifies that the Π_{odd}(n) have the same four types as in Section 2.1, but this time it is Type (I) that does not occur, and the records occur at Type (II).

Theorem 10. Let n, k be natural numbers. Then

(a) Π_{odd}(n) never has type (I).

(b) If n = 3k + 1 then Π_{odd}(n) has type (III).

(c) If n = 3k + 2 then Π_{odd}(n) has type (II).

(d) If n = 3k then Π_{odd}(n) has type (II) if Π_{odd}(k) has type (II) and Π_{odd}(n) has type (IV) if Π_{odd}(k) has type (III) or type (IV).

Proof.

(a) Π_{odd}(n) is never equal to 2n − 1, since the algorithm always chooses the right side at the odd numbers.

(b) i.e., Π_{odd}(3k +1) = 2k +1 is also forced by the ‘always to the right at the odd numbers’ rule: 2k + 1 + ⌊(2k + 1)/2⌋ = 3k + 1.

(c) follows from part (a) and the observation that both 2n + 1 = 2(3k + 2) + 1 = 6k + 5 and 2n = 6k + 4 are not divisible by 3.

(d) Type (I) is excluded by part (a), and type (III) is excluded because 2n + 1 = 6k + 1 is not divisible by 3. So Π_{odd}(n) is either 2n (type (II)), or 2n/3 (type IV). Here 2n/3 = 6k/3 = 2k. But 2k would have been assigned to k if Π_{odd}(k) has type(II), so if Π_{odd}(n) has type (IV) then Π_{odd}(k) has type (III) or (IV). Conversely, if Π_{odd}(k) has type (III) or (IV), then Π_{odd}(n) must have type (III): in 2k you do not go the left, since 2k − ⌊2k/2⌋ = k, and Π_{odd}(k) has already been assigned a value. Going to the right in 2k yields Π_{odd}(2k + k) = 2k.

Let Π_{odd}(1) = 1 have Type (III) by definition. Then Theorem 10 can easily be transformed into the following result.

Theorem 11. Let σ on the monoid {2, 3, 4}^{∗} be the monoid morphism given by

σ(2) = 322, σ(3) = 324, σ(4) = 324.

Let s_{odd} = 32432232432432232232432232432 ⋯ be the unique fixed point of σ. Then s_{odd}(n) = 2 iff Π_{odd}(n) has type (II), s_{odd}(n) = 3 iff Π_{odd}(n) has type (III), and s_{odd}(n) = 4 iff Π_{odd}(n) has type (IV).

Let R_{opos} = \underline{A026179} be the sequence of positions of records in Π_{odd}:

R_{opos} = 1, 2, 5, 6, 8, 11, 14, 15, 17, 18, 20, 23, 24, 26, 29, 32, 33, 35, 38, 41, 42, 44, …

The sequence R_{orec} = \underline{A026180} of records in Π defined by R_{orec}(n) = Π_{odd}(R_{opos}(n)) is given by

R_{orec} = 1, 4, 10, 12, 16, 22, 28, 30, 34, 36, 40, 46, 48, 52, 58, 64, 66, 70, 76, 82, 84, …

Proposition 12. Let τ be the morphism given by τ(1) = 12, τ(2) = 312, τ(3) = 3312. Let t = 12312331212312331233121231212312 ⋯ be the fixed point of τ starting with 1. Let T denote the shift operator. Then T (ΔR_{opos}) = T^{2}(t), and T (ΔR_{orec}) = 2T^{2}(t).

Proof. The records in Π_{odd} are exactly given by the Π(n) of type (II). So the positions of these records are given by the positions of 2 in s_{odd}. To obtain these, one considers the return words of the word 2 in s_{odd}. These are 2, 23 and 243. We have

σ(2) = 32 2, σ(23) = 32 23 24 σ(243) = 32 23 243 24.

If we code the return words by their lengths, then the induced descendant morphism σ_{desc}, obtained by conjugating σ with the word 3, (see the paper [4]) is equal to

σ_{desc}(1) = 12, σ_{desc}(2) = 123, σ_{desc}(3) = 1233.

The ‘right’ morphism however, is τ, given by

τ(1) = 12, τ(2) = 312, τ(3) = 3312.

To prove this, avoiding confusions of symbols, we write τ on the alphabet {a, b, c}:

τ(a) = ab, τ(b) = cab, τ(c) = ccab.

Let x_{τ} = abcabcc ⋯ be the fixed point of τ starting with a, and let δ be the morphism given by

δ(a) = 2, δ(b) = 23, δ(c) = 243.

Note that the images of δ are the return words of 2, with lengths 1,2, and 3, so the proposition will be proved if we show that

T^{2}(δ(x_{τ})) = T (s_{odd}) = 2432232432 · · · .

As in the paper [3], we call δ(x_{τ}) a decoration of x_{τ}. It is well-known that such a decoration is again a morphic sequence, see, e.g., the monograph by Allouche and Shallit [1, Corollary 7.7.5]. We perform what is called the ‘natural algorithm’ in the paper [3], to find the morphism and the letter-to-letter map which yield δ(x_{τ}) as a morphic sequence. Consider the alphabet {a, b, b′, c, c′, c′′}, and define a block-substitution by

a → abb′, bb′ → cc′c′′abb′, cc′c′′ → cc′c′′cc′c′′abb′.

We obtain from this a morphism on {a, b, b′, c, c′, c′′} by splitting the images of bb′ and cc′c′′ in the block-substitution (in the most efficient way):

a → abb′, b → cc′c′′, b′ → abb′, c → cc′c′′, c′ → cc′c′′, c′′ → abb′.

Here efficient means that as many as possible symbols can be merged, respecting the letter to letter map a → 2, b → 2, b′ → 3, c → 2, c′ → 4, c′′ → 3, obtained by identifying a, bb′ and cc′c′′ with the return words 2, 23 and 243. We merge b and c, renaming this as \overline{2}, and we merge b′ and c′′, renaming the resulting symbol as 3. Also renaming a as 2, and c′ as 4, we obtain a morphism θ on the alphabet \{2, \overline{2}, 3, 4\}, and a letter to letter map which is the identity, except that \overline{2} is mapped to 2. Thus θ is given by

θ(2) = 2\overline{2}3, θ(\overline{2}) = \overline{2}43, θ(3) = 2\overline{2}3, θ(4) = \overline{2}43.

To obtain the claim above we have to shift the fixed point of θ by 2. The way to generate that sequence is to pass to the words of length 3 of the language of θ, and to project these on the third symbol. There are 8 words of length 3:

1 := 2\overline{2}3, 2 := \overline{2}32, 3 := \overline{2}3\overline{2}, 4 := \overline{2}43, 5 := 32\overline{2}, 6 := 3\overline{2}4, 7 := 432, 8 := 43\overline{2}.

The induced 3-block morphism (cf. the paper [2]) is given by

1 → 136, 2 → 475, 3 → 475, 4 → 486, 5 → 125, 6 → 136, 7 → 475, 8 → 475.

The projection on the third symbol is given by

1 → 3, 2 → 2, 3 → \overline{2}, 4 → 3, 5 → \overline{2}, 6 → 4, 7 → 2, 8 → \overline{2}.

We see that we can consistently merge 7 and 2, and also 8 and 3. The 3-block morphism with these symbols merged is then given by

1 → 136, 2 → 425, 3 → 425, 4 → 436, 5 → 125, 6 → 136.

We now see that we can merge 1 and 4 (both map to 3), and then also 3 and 5 (both map to \overline{2}), which leads to the morphism

1 → 136, 2 → 123, 3 → 123, 6 → 136.

Equivalently, on the ‘third symbol’ alphabet \{2, \overline{2}, 3, 4\}:

3 → 3\overline{2}4, 2 → 32\overline{2}, \overline{2} → 32\overline{2}, 4 → 3\overline{2}4.

We can then merge 2 and \overline{2} to 2, obtaining the morphism

3 → 324, 2 → 322, 4 → 324,

which is nothing else than the morphism σ generating s_{odd}. Since the first 2 in s_{odd} occurs at the second index, we thus proved that T^{2}(δ(x_{τ})) = T (s_{odd}) = 2432232432 · · ·.

The second equation follows from the fact that all records are of type (II), and so

R_{orec}(n+1)−R_{orec}(n) = Π_{odd}(R_{opos}(n+1))−Π_{odd}(R_{opos}(n)) = 2R_{opos}(n+1)−2R_{opos}(n) = 2t(n).

2.4 Changing the rules: rule 42

Here L(n) = [(n + 1)/2] = R(n), and a(n − L(n)) = n if a(L) not yet defined, else a(n + R(n)) = n.

The resulting permutation of ℕ is denoted by Π_{42}, which is sequence \underline{A026142} in the encyclopedia [5], given by

Π_{42} = 1, 4, 2, 8, 3, 12, 14, 5, 6, 20, 7, 24, 26, 9, 10, 32, 11, 36, 38, 13, 42, 44, 15, 16, ….

One verifies that the Π_{42}(n) have four types slightly different from those in Section 2.1:

(I) Π_{42}(n) odd, Π_{42}(n) > n, Π_{42}(n) = 2n + 1
(II) Π_{42}(n) even, Π_{42}(n) > n, Π_{42}(n) = 2n
(III) Π_{42}(n) odd, Π_{42}(n) < n, Π_{42}(n) = (2n − 1)/3
(IV) Π_{42}(n) even, Π_{42}(n) < n, Π_{42}(n) = 2n/3.

The next task is to determine the type of all entries of Π.

Theorem 13. Let n, k be natural numbers. Then

(a) Π_{42}(n) never has type (I).

(b) If n = 3k + 1 then Π_{42}(n) has type (II).

(c) If n = 3k + 2 then Π_{42}(n) has type (III).

(d) If n = 3k + 3 then Π_{42}(n) has type (II) if Π_{42}(k + 1) has type (II) and Π_{42}(n) has type (IV) if Π_{42}(k + 1) has type (III) or type (IV).

Proof.

(a) Π_{42}(n) is never equal to 2n, since either n has been assigned the value 2n + 1 at step 2n + 1: 2n + 1 − ⌊(2n + 2)/2⌋ = n, or n has been assigned a smaller value at an earlier step.

(b) follows from part (a) and the observation that both 2n − 1 = 2(3k + 1) − 1 = 6k + 1 and 2n = 6k + 2 are not divisible by 3.

(c) is a rephrasing of the version of Proposition 2 for rule 42: Π(3n + 2) = 2n + 1, which is a consequence of the version of Lemma 1 for rule 42 (‘if the procedure is at step 2n+1, then the numbers 1, …, n have already been assigned a Π-value.’)

(d) Type (I) is excluded by part (a), and type (III) is excluded because 2n − 1 = 6k + 5 is not divisible by 3. So Π_{42}(n) is either 2n (type (II)), or 2n/3 (type IV). Here 2n/3 = (6k + 6)/3 = 2k + 2. But 2k + 2 = 2(k + 1) was already assigned to k + 1 if Π(k + 1) has type (II), so Π_{42}(n) = 2n/3 has type (II) when k + 1 has Π(k + 1) has type(II). Conversely, if Π(k + 1) has not type (II), i.e., type (III) or type (IV), then Π_{42}(n) has type (IV).

For the next result we need a fifth type. We say Π_{42}(n) has type (V) if Π_{42}(n) = n. Actually the only Π_{42}(n) of type (V) is Π_{42}(1). This way one arrives at the following result.

Theorem 14. Let σ on the monoid {2, 3, 4, 5}^{∗} be the monoid morphism given by

σ(2) = 232, σ(3) = 234, σ(4) = 234, σ(5) = 524.

Let s = 5, 2, 4, 2, 3, 2, 2, 3, 4, 2, 3, 2, 2, 3, 4, 2, 3, 2, 2, 3, 2, 2, 3, 4, 2, 3, 4, 2, 3, 2, 2, 3, 4 … be the fixed point of σ starting with 5. Then for all n > 1: s_{n} = 2 iff Π_{42}(n) has type (II), s_{n} = 3 iff Π_{42}(n) has type (III), and s_{n} = 4 iff Π_{43}(n) has type (IV).

Let R_{pos} = \underline{A026144} be the sequence of positions of records in Π_{42}:

R_{pos} = 1, 2, 4, 6, 7, 10, 12, 13, 16, 18, 19, 21, 22, 25, 28, 30, 31, 34, 36, 37, 39 …

The sequence R_{rec} = \underline{A026145} of records in Π defined by R_{rec}(n) = Π_{42}(R_{pos}(n)) is given by

R_{rec} = 1, 4, 8, 12, 14, 20, 24, 26, 32, 36, 38, 42, 44, 50, 56, 60, 62, 68, 72, 74, 78, 80, …

Except for the first one, the records are always even, because they are generated by type (II) elements of the permutation.

Proposition 15. Let τ be the morphism on {1, 2, 3, 4}^{∗} given by

τ(1) = 21, τ(2) = 213, τ(3) = 2133, τ(4) = 4213.

Let t = 421321321213321321213321321213212 … be the fixed point of τ starting with 4. Then ΔR_{pos}(n + 1) = t(n), for n ≥ 2 and ΔR_{rec}(n + 1) = 2t(n), for n ≥ 2.

Proof. The records in Π are exactly given by the Π(n) of type (II). So the positions of these records are given by the positions of 2 in s. To obtain these, one considers the return words of the word 2 in s. These are 2, 23, 24 (only at the beginning) and 234. Since

σ(2) = 23 2, σ(23) = 23 2 234, σ(24) = 23 2 234, σ(234) = 23 2 234 234,

the induced derived morphism is equal to τ, where we code the return words by their lengths, and we added a ‘starting’ letter 4 at the beginning. Since we coded the return words by their lengths, this gives that R_{pos}(n + 1) − R_{pos}(n) = t(n), for n ≥ 2 where t is the fixed point of τ starting with 4. The second equation follows from the fact that all records are of type (II), and so

R_{rec}(n + 1) − R_{rec}(n) = Π(R_{pos}(n + 1)) − Π(R_{pos}(n)) = 2R_{pos}(n + 1) − 2R_{pos}(n) = 2t(n).

2.5 Comparing two permutations

The permutation Π_{36} := Π from Section 2.1 and Π_{42} from Section 2.4 have many entries in common, as observed in the OEIS sequence

\underline{A026222} = 1, 3, 9, 15, 24, 27, 33, 42, 45, 51, 60, 69, 72, …,

which gives the first 66 numbers n satisfying Π_{36}(n) = Π_{42}(n). Here we prove that there are infinitely many of such entries. More precisely, let this ‘coincidence’ sequence be C given by: n is in {C(k) : k ∈ ℕ} if and only if Π_{36}(n) = Π_{42}(n). We show that the difference sequence ΔC is 3-automatic.

Theorem 16. Let C be the ‘coincidence’ sequence of Π_{36} and Π_{42}. Then C = I_{4}, where I_{4} is the sequence of natural numbers with type (IV) in Π_{42}.

Proof. To generate the ‘coincidence’ sequence C, we have to consider the product of the two morphisms generating the types of the two permutations Π_{36} and Π_{42}. This product is defined on the set of product symbols {1, 2, 3, 4} × {1, 2, 3, 4}. Not all product symbols occur. By writing out the images of the product symbols under the product substitutions one produces a list of the relevant ones:

(\begin{matrix}1 \\ 5 \end{matrix}) , (\begin{matrix}1 \\ 2 \end{matrix}) , (\begin{matrix}4 \\ 4 \end{matrix}) , (\begin{matrix}1 \\ 3 \end{matrix}) , (\begin{matrix}4 \\ 2 \end{matrix}) , (\begin{matrix}3 \\ 2 \end{matrix}) .

One has, for example,

(\begin{matrix}1 \\ 5 \end{matrix}) → (\begin{matrix}1 \\ 5 \end{matrix}) (\begin{matrix}1 \\ 2 \end{matrix}) (\begin{matrix}4 \\ 4 \end{matrix}) , (\begin{matrix}1 \\ 2 \end{matrix}) → (\begin{matrix}1 \\ 2 \end{matrix}) (\begin{matrix}1 \\ 3 \end{matrix}) (\begin{matrix}4 \\ 2 \end{matrix}) , (\begin{matrix}4 \\ 4 \end{matrix}) → (\begin{matrix}3 \\ 2 \end{matrix}) (\begin{matrix}1 \\ 3 \end{matrix}) (\begin{matrix}4 \\ 4 \end{matrix}) .

From the observation that a coincidence ( \begin{matrix}4 \\ 4 \end{matrix} ) occurs if and only if a 4 occurs in the ‘lower’ sequence Π_{42}, the theorem now follows.

The next result identifies the sequence I_{4} in terms of its first differences. We do need again an extra symbol 4 to deal with the beginning of I_{4}.

Proposition 17. Let κ be the morphism on {1, 2, 3, 4}^{∗} given by

κ(1) = 12, κ(2) = 123, κ(3) = 1233, κ(4) = 423.

Let k = 4231231233 … be the fixed point of κ starting with 4. Then ΔI_{4}(n + 1) = λ(k(n)) for n ≥ 1, where λ is the letter-to-letter map 1 → 3, 2 → 6, 3 → 9, 4 → 6.

Proof. Let s_{42} = 5, 2, 4, 2, 3, 2, 2, 3, 4, 2, 3, 2, 2, 3, 4, 2, 3, 2, 2, 3, be the sequence of types of Π_{42} given by Theorem 14, which gives s_{42} as fixed point of the morphism σ defined by

σ(2) = 232, σ(3) = 234, σ(4) = 234, σ(5) = 524.

The three return words of the word 4 in s are a := 423, b := 423223 and c := 423223223. We cannot apply the descendant algorithm of the paper [4], since the sequence s is not a minimal sequence, not only because of the unique appearance of s_{42}(1) = 5 at the beginning, but also because of the unique appearance of s_{42}(2)s_{42}(3) = 24, s_{42}(3) … s_{42}(14) = bb, etc.

We compute the images of the return words under σ.

σ(a) = 23 b 4, σ(b) = 23 bc 4, σ(c) = 23 bcc 4.

We see from this that if we write

s_{42} = σ(s_{42}) = 52 b′bcabcabcc …,

where b′ = 423223, then the sequence s_{42}(3)s_{42}(4)s_{42}(5) … is a fixed point of the morphism given by

a → ab, b → abc, b′ → b′bc, c → abcc.

The proposition now follows by changing the alphabet {a, b, c, b′} to {1, 2, 3, 4}, and noting that |a| = 3, |b| = |b′| = 6, |c| = 9.

We remark that the main, primitive part of κ is given by \underline{A106036}.

2.6 Changing the rules: Π(1)

One might get rid of the requirement Π(1) := 1 by defining a new permutation Π_{⊕} by

Π_{⊕}(n) := Π(n + 1) − 1 for n = 1, 2, ….

For the rule of Section 2.1 given by L(n) = ⌊n/2⌋, R(n) = ⌊n/2⌋, this transforms

Π = 1, 3, 2, 7, 9, 4, 5, 15, 6, 19, 21, 8, 25, 27, 10, 11, 33, 12, 13, 39, 14, 43, 45, 16, 17, 51, …

into

Π_{⊕} = 2, 1, 6, 8, 3, 4, 14, 5, 18, 20, 7, 24, 26, 9, 10, 32, 11, 12, 38, 13, 42, 44, 15, 16, 50 ….

There is a remarkable connection with the permutation Π_{odd}. In the following proposition the sequence s appears as \underline{A026215} in the OEIS.

Proposition 18. Let Π = Π_{36} be the permutation of Section 2.1, and let Π_{odd} be the permutation of Section 2.3, then Π_{⊕}(n) is the position of n in the sequence (s(n)/2), where s(n) is the n^{th} even number in Π_{odd}.

Proof. The positions of the even numbers in Π_{odd} are given by the entries 2 and 4 of the fixed point s_{odd} = 32432232432432232232432232432 … of the morphism σ_{odd} given by

σ_{odd}(2) = 322, σ_{odd}(3) = 324, σ_{odd}(4) = 324.

See Theorem 11. We see from the form of σ_{odd} that the positions of the even numbers in Π_{odd} are then exactly given by the union of the two arithmetic sequences (3n + 2 : n ≥ 0) and (3n + 3 : n ≥ 0). This implies that

s(2n + 1) = Π_{odd}(3n + 2) and s(2n + 2) = Π_{odd}(3n + 3) for n = 0, 1, 2, ….

So we have to prove for j = 1, 2 that

Π_{⊕}^{−1}(2n + j) = \frac{1}{2}Π_{odd}(3n + j + 1) ⇔ Π_{⊕}(\frac{1}{2}Π_{odd}(3n + j + 1)) = 2n + j.

Here the case j = 1 is the simplest: we see from the form of σ_{odd} that all n which are 2 modulo 3 have type (II), hence Π_{odd}(3n+2)/2 = (6n+4)/2 = 3n+2, and also Π_{⊕}(3n+2) = Π(3n + 3) − 1 = 2n + 1, since all multiples of 3 in the permutation Π have type (IV), by Theorem 3.

The case j = 2 is similar, but more involved. We must see that Π_{⊕}(Π_{odd}(3n + 3)/2) = 2n + 2, which holds, replacing n + 1 by n, if and only if

Π(\frac{1}{2}Π_{odd}(3n) + 1) = 2n + 1.

There are two possible types for Π_{odd}(3n): (A) type (IV), and (B) type (II).

In case (A) we have Π_{odd}(3n) = 2n, so then we have to see that Π(n + 1) = 2n + 1, which means that Π(n + 1) should have type (I). Using Theorem 3, part d), this holds if and only if Π(3n + 1) has type (I).

In case (B) we have Π_{odd}(3n) = 6n, so then we have to see that Π(3n + 1) = 2n + 1, which means that Π(3n + 1) should have type (III). We should therefore prove the following.

(A) Π(3n + 1) has Type (I) iff Π_{odd}(3n) has Type (IV)
(B) Π(3n + 1) has Type (III) iff Π_{odd}(3n) has Type (II) .

Let σ =: σ_{36} be the morphism generating the sequence s_{36} of types of Π. The sequence T s_{36} = s_{36}(2)s_{36}(3) … is also 3-automatic, and a simple computation yields that T s_{36} is the fixed point of the morphism τ on {1, 3, 4} given by

τ(1) = 141, τ(3) = 143, τ(4) = 143.

Now consider the product morphism τ × σ_{odd} on the relevant subset of {1, 3, 4} × {2, 3, 4}. Starting with the first symbol (1, 3) of the fixed point of the product morphism, one finds quickly that these relevant symbols are (1, 3), (4, 2), (1, 4) and (3, 2). It is also easy to see that at entries which are a multiple of 3, only the two symbols (1, 4) and (3, 2) occur. This proves (A) and (B).

3 Conclusion

We have introduced a frame work to analyze permutations generated by a left-right filling algorithm. This has lead to a compact description of sequences \underline{A026136}, \underline{A026142}, \underline{A026172}, and \underline{A026177} in the OEIS. We leave the permutation given in \underline{A026166} to the interested reader. There are numerous relations that can be derived from this description as we showed, for example, at the end of Section 2.2. Here is one conjecture on the basic permutation Π = Π_{36} in Section 2.1: R_{pos} and R_{rec} seem to be disjoint sequences. The complement of their union: \{6, 12, 16, 18, 24, 30, …\}, divided by 2: \{3, 6, 8, 9, 12, 15, …\} is equal to \underline{A189637}, the positions of 1 in \underline{A116178}, where \underline{A116178} is Stewart’s choral sequence, the unique fixed point of the morphism 0 → 001, 1 → 011.

References

[1] J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.

[2] F. M. Dekking, Morphisms, symbolic sequences, and their standard forms, J. Integer Sequences 19 (2016), Article 16.1.1.

[3] F. M. Dekking, Morphic words, Beatty sequences and integer images of the Fibonacci language, Theoret. Comput. Sci. 809 (2020), 407–417.

[4] C. Holton and L. Q. Zamboni, Descendants of primitive substitutions, Theory Comput. Syst. 32 (1999), 133–157.

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

   at https://oeis.org.

2010 Mathematics Subject Classification: Primary 11B85, Secondary 68R15. Keywords: morphic word, permutation of ℕ, 3-automatic sequence.

(Concerned with sequences \underline{A026136}, \underline{A026137}, \underline{A026138}, \underline{A026139}, \underline{A026140}, \underline{A026141}, \underline{A026142}, \underline{A026143}, \underline{A026144}, \underline{A026145}, \underline{A026146}, \underline{A026166}, \underline{A026167}, \underline{A026168}, \underline{A026169}, \underline{A026170}, \underline{A026171}, \underline{A026172}, \underline{A026173}, \underline{A026174}, \underline{A026175}, \underline{A026176}, \underline{A026177}, \underline{A026178}, \underline{A026179}, \underline{A026180}, \underline{A026181}, \underline{A026182}, \underline{A026183}, \underline{A026184}, \underline{A026185}, \underline{A026186}, \underline{A026187}, \underline{A026188}, \underline{A026189}, \underline{A026190}, \underline{A026191}, \underline{A026192}, \underline{A026193}, \underline{A026194}, \underline{A026195}, \underline{A026196}, \underline{A026197}, \underline{A026198}, \underline{A026199}, \underline{A026200}, \underline{A026201}, \underline{A026202}, \underline{A026203}, \underline{A026205}, \underline{A026206}, \underline{A026208}, \underline{A026209}, \underline{A026210}, \underline{A026211}, \underline{A026212}, \underline{A026213}, \underline{A026214}, \underline{A026215}, \underline{A026216}, \underline{A026217}, \underline{A026218}, \underline{A026219}, \underline{A026220}, \underline{A026221}, \underline{A026222}, \underline{A026223}, \underline{A026224}, \underline{A026225}, \underline{A026226}, \underline{A026227}, \underline{A026228}, \underline{A026229}, \underline{A026230}, \underline{A026231}, \underline{A026232}, \underline{A065190}, \underline{A106036}, \underline{A116178}, and \underline{A189637}.)

Received January 26 2020; revised version received April 4 2020. Published in Journal of Integer Sequences, May 5 2020.

Return to Journal of Integer Sequences home page.