Choix de Bruxelles Operation of Order Three

Karol Gryszka Institute of Mathematics Pedagogical University of Kraków Podchora̧żych 2 30-084 Kraków Poland

                  karol.gryszka@up.krakow.pl

Abstract We investigate the “Choix de Bruxelles” operation on integers that replaces the number N by any of the numbers that can be obtained by multiplying or dividing by 3 consecutive digits of the decimal representation of N. Our approach is different from the original one assuming halving or doubling, and while both approaches share some similarities, they also differ in selected features. Our goal is to investigate the modified operation and to describe its graph.

1 Introduction

Let N be a positive integer with decimal representation

N = [d_{1}d_{2} ⋯ d_{k}].

Angelini et al. [1] investigated the so–called “Choix de Bruxelles” operation on integers that replaces N by taking any number [w] represented by a string w = d_{p} ⋯ d_{q} with 1 ≤ p ≤ q ≤ k and d_{p} ≠ 0, and replacing that string by the decimal representation of [2(w)] or, if w is even, by the decimal representation of [2(w)] or [(w)/2]. Choosing an empty string is also allowed. Since d_{p} ≠ 0, the operation is clearly invertible.

The operation applied to N = 1208 provides the following numbers, where one digit is changed:

2208, 1408, 12016, 1108, 1204.

Notice the five-digit number is obtained by replacing 8 with 16. We emphasize that we do not carry 1 to the next decimal place. When we consider strings of length two, the following numbers are possible to get:

2408, 1408, 608, 1108.

The name “Choix de Bruxelles” has the origins briefly described by Angelini et al. [1] and involves “sprouts” (“choux de Bruxelles”) described by Berlekamp et al. [2]. There are many appearances of this operation in Online Encyclopedia of Integer Sequences (OEIS) [3], see for instance sequences \underline{A323454}, \underline{A323286}, and \underline{A323287}.

In this article we investigate a similar operation, but our approach assumes multiplying or dividing a segment by 3. This leads, for example, to the following numbers, that can be obtained from 154 in one step:

354, 1154, 1512, 454, 1162, 462, 54, 118.

The last two numbers are obtained by diving two-digit segments by 3. We give more examples in Table 1. We note that there are other variations of the Choix de Bruxelles operation; we refer the reader to sequences \underline{A337321} and \underline{A337357} in OEIS [3].

\begin{matrix}N & goes to \\ 1 & 1, 3 \\ 6 & 2, 12 \\ 12 & 4, 32, 16, 36 \\ 36 & 16, 32, 12, 96, 318, 108 \\ 243 & 83, 241, 81, 643, 2123, 249, 723, 2129, 729 \\ 608 & 1808, 208, 6024, 1824 \end{matrix}

Table 1: Numbers arising when Choix de Bruxelles operation of order three is applied to some numbers.

Our goal is similar to the one posed by Angelini et al. [1]. We investigate the modified operation and find out what happens when it is iterated. We call it the Choix de Bruxelles operation of order three. In the article we investigate the range of the operation in one or more steps. We also completely describe the graph of the operation and present an algorithm that for a given number identifies its connected component of the graph.

In the article we let N denote a positive integer (which is subject to the Choix de Bruxelles operation of order three). A substring of N is denoted by w (or w_{1}, w_{2} and so on), its decimal representation is denoted by [w] and its length is written |w|. We denote by (123) (or any other number) the string 123. The concatenation of two strings w_{1} and w_{2} is w_{1} · w_{2}. If w is a string, then by (3[w]) (and similar symbols) we understand a string with digits equal to the number represented by 3[w] (if w = 444, then (3[w]) = 1332).

2 Numbers that are reached in one step

Table 2 shows the lowest and the largest numbers that can be reached in one step. They are denoted by M_{l}(N) and M_{u}(N), respectively, for each positive integer N. First, let us

\begin{matrix}N & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ M_{l}(N) & 1 & 2 & 1 & 4 & 5 & 2 & 7 & 8 & 3 & 10 & 11 & 4 & 13 & 14 & 5 \\ M_{u}(N) & 3 & 6 & 9 & 12 & 15 & 18 & 21 & 24 & 27 & 30 & 33 & 36 & 39 & 112 & 115 \end{matrix}

Table 2: The largest and the lowest number that can be obtained in one step.

investigate the bounds of functions M_{u} and M_{l}.

Theorem 1. The largest number M_{u}(N) that can be obtained from

N = [d_{1}d_{2}d_{3} ⋯ d_{k}]

by the Choix de Bruxelles operation is either 3N, if d_{i} < 4 for all i, and otherwise is obtained by multiplying by 3 the number [w] = [d_{p} ⋯ d_{k}], where d_{p} is the right-most digit not less than 4, and replacing [w] with 3[w] in N.

Proof. If d_{i} < 4 for all i, then |3N| = |N| and M_{u}(N) = 3N.

If d_{i} ≥ 4 for at least one i, then |3d_{i}| = 2. We choose any string starting with such d_{i}. Let M denote the number obtained from N by replacing d_{i} with 3d_{i}. Then |M| = |N| + 1.

Notice that if x is the number represented by the farthest substring to the right starting with d_{i} ≥ 4, then we should multiply x by 3. This is because if the first digit of the substring is not less than 4, then the tripled one starts with 1 or 2 and that is less than 4. More formally, if d_{p} ⋯ d_{k} is the right-most string starting with d_{p} ≥ 4, then we can obtain

M = d_{1}d_{2} ⋯ d_{p−1} · 1 · (3d_{p} − 10) · A, d_{p} ∈ {4, 5, 6}

or

M = d_{1}d_{2} ⋯ d_{p−1} · 2 · (3d_{p} − 20) · B, d_{p} ∈ {7, 8, 9}

for some (possibly empty) strings of numbers A and B. On the other hand, if there is a digit d_{s} ≥ 4 with s < p, then let

M′ = d_{1} ⋯ d_{s−1} · (3[d_{s}]) · d_{s+1} ⋯ d_{k}

and s-th digit of M′ is less than the one of M, so M′ < M.

Finally, if d_{p} is the right-most digit that is at least 4, then let N_{p} denote the number obtained by Choix de Bruxelles on a substring d_{p} ⋯ d_{q} with q ≤ k. Then

N_{p} = d_{1} ⋯ d_{p−1} · (3[d_{p} ⋯ d_{q}]) · d_{q+1} ⋯ d_{k}

and the number N_{p} is maximized by taking q = k.

We illustrate Theorem 3 with three examples.

Example 2. (1) Let N = 113. Since all digits are at most 3, we have M_{u}(N) = 3N = 339. (2) Let N = 56234234. The right-most digit is at least 4, hence M_{u}(N) = 562342312.

(3) Let N = 67542. The right-most digit that is at least 4 is 4 (the tens place), hence we multiply 42 by 3 and M_{u}(N) = 675126.

We follow the notion of “greedy algorithm” from the article by Angelini et al. [1] for the algorithm in Theorem 1, that is, for a given number N the algorithm described in the theorem returns the largest possible number M_{u}(N).

A similar theorem holds for the lowest number M_{l}(N).

Theorem 3. The lowest number M_{l}(N) that can be obtained from

N = [d_{1}d_{2}d_{3} ⋯ d_{k}]

by the Choix de Bruxelles operation is either

1. N, if there is no substring of N that is divisible by 3,

2. otherwise, among all indexes r and s with d_{r} ∈ {1, 2} and [w] = [d_{r} ⋯ d_{s}] such that [w] is divisible by 3, first select the largest r possible and then for such r select the largest s possible, finally replace [w]/3 with [w] in N,

3. otherwise, among all indexes r and s with d_{r} ≥ 3 and [w] = [d_{r} ⋯ d_{s}] such that [w] is divisible by 3, first select the lowest r possible and then for such r select the largest s possible, finally replace [w]/3 with (w) in N.

Proof. We mimic the argument in the proof of Theorem 1.

We illustrate Theorem 3 with three examples.

Example 4. (1) Let N = 116. Only one string is divisible by 3, hence M_{l}(N) = 112.

(2) Let N = 56234234. We have two substrings starting with 2 that are divisible by 3: 234 and 234234. We can obtain three different strings from that:

                      56 · 78 · 234, 56 · 234 · 78, 56 · 78078.

The algorithm says we should pick the right-most string 234 and the lowest possible number is 5623478.

(3) Let N = 67542. There is no substring starting with 1 or 2 that is divisible by 3, so we find the longest substring that is divisible by 3 and starts farthest to the left. We have several choices: 6, 675, 67542, and they give numbers 27542, 22542 and 22514, respectively. The last one, 22514, is the lowest one possible possible one according the algorithm. It is easy to check that by hand as well.

With what we have just proven we can get precise bounds on the range of numbers generated by the Choix de Bruxelles operation of order three.

Theorem 5. The numbers M obtained by the Choix de Bruxelles operation to N lie in the range

\frac{N}{10} < M < 10N

and there are values of N for which M is arbitrarily close to the either of the bounds.

Proof. Since the operation is invertible, it is sufficient to prove the lower bound (the upper bound follows by switching the roles of M and N).

For the lower bound we can assume the case 2. in Theorem 3, otherwise we obtain M_{l}(N) ≥ \frac{N}{3} .

Let

N = A · C · B, or N = [A] · 10^{j} + [C] · 10^{j+r−s−1} + [B]

for some j ≥ 1, strings A, B and C with

C = d_{r} ⋯ d_{s}, d_{r} ∈ {1, 2}

and C is the string described in the case 2. in Theorem 3. Then the left-most digit of [C]/3 is at least 3 and

M_{l}(N) = [A] · 10^{j−1} + \frac{[C]}{3} · 10^{j+r−s−1} + [B],

so we have M_{l}(N) > \frac{N}{10}.

For the optimal bound take N = 10^{k} + 12 with k ≥ 2. Then M_{l}(N) = 10^{k−1} + 4 and we have

lim_{N→+∞} \frac{M_{l}(N)}{N} = \frac{1}{10}.

3 The graph G of the Choix de Bruxelles operation of order three

Let G denote the undirected graph, whose vertices are positive integers and two vertices are connected by an edge if and only if one vertex (represented by a number or a string) can be obtained by a valid Choix de Bruxelles operation of order three from the other vertex. We have for instance the following partial graph of G (see Figure 1). The graph is undirected since the operation is symmetric (invertible). We do not draw edges corresponding to empty strings.

We also represent the graph with the following simplified notation, that we will use frequently throughout the article:

5 − 15 − 35 − 95 − 275 − 815 − 85.

5 15 35 95 275 815 85

Figure 1: Subgraph of G.

We show that the graph has infinitely many components and we describe how to find the corresponding component for a given number N.

We start with the simple case – the number which the right-most digit is 0. Whenever we write “number can be reduced to” we mean that after some number of iterations, a given number can be reduced with the Choix de Bruxelles operations to another number. To “reduce the number of digits” means to iterate the operation on N so that the number M which we obtain has |M| < |N|.

Let Z(ℓ) denote a string of ℓ zeroes. For example, Z(3) = 000. The following lemma describes the numbers N that are of the form N = A · Z(ℓ).

Lemma 6. Any number N of the form N = A · Z(ℓ) with ℓ > 0 and k not divisible by 10 cannot be reduced to k′ · Z(ℓ′) with ℓ′ < ℓ and k not divisible by 10.

Proof. Note that the right-most digit of k′, say d, would have to satisfy d · 3 ≡ 0 (mod 10), which is impossible.

Lemma 6 says that the number of zeroes at the end of the number N stays fixed under the operation. This has a major consequence for the graph of the operation.

Theorem 7. The graph G has infinitely many connected components.

Proof. This is an obvious consequence of Lemma 6.

Since the graph has infinitely many components, it is interesting to find a description for each component by some sort of “root” number, that is, the numbers N that cannot be reduced to a lower number. We do that with the help of the following definition.

Definition 8. The vertices labeled with the numbers 1 · 10^{ℓ}, 2 · 10^{ℓ} and 5 · 10^{ℓ} where ℓ is a non-negative integer, are called the roots of the graph G.

We now describe all components of the graph G. Its partial description is based on Lemma 6. We show that each number can be reduced by the Choix de Bruxelles operation of order three to one of the roots of G and each root describes a different connected component. According to Lemma 6, it is enough to solve the cases where 10 does not divide N.

Lemma 9. The number 2 cannot be reduced to 1 or 5. The number 5 cannot be reduced to 1.

Proof. Any valid operation on 2 or its iterates gives a number m ≡ 0 (mod 2). Furthermore, any valid operation on 5 or its iterates gives a number m ≡ 5 (mod 10).

Lemma 9 and Lemma 6 show that any number of the form 1 · 10^{ℓ}, 2 · 10^{ℓ} and 5 · 10^{ℓ} belongs to a different component of the graph. We now describe which numbers belong to which component. For this, it is enough to find all numbers that can be reduced to a given root.

Lemma 10. Any number of the form N = 10a + 5 can be reduced to 5.

Proof. The proof goes by induction on the number of digits of N. If |N| ≤ 2, then we use Figure 2 to reduce such number to 5 (the reduction is optimal).

5 15 35 95 275 815 85 45 125 165 55 225 75 115 135 195 65 25

Figure 2: Subgraph of G with optimal reduction path for all odd two-digit numbers divisible by 5.

If |N| > 2 and N = k · 10^{ℓ} + 5, then ℓ ≥ 2 and the number can be reduced by one digit as follows (first step is to multiply a whole number by 3):

k · Z(ℓ − 1) · 5 − (3k) · Z(ℓ − 2) · 15 − k · Z(ℓ − 2) · 15 − k · Z(ℓ − 2) · 5.

Obviously,

|k · Z(ℓ − 2) · 5| = |N| − 1.

If |N| > 2 and two right-most digits of N differ from 05, then we can reduce the string of these digits to 5 according to the subgraph (Figure 2). In this case we also reduce N by one digit.

By the principle of induction the reduction is possible for an arbitrarily long number.

Example 11. Let N = 705. Then, according to Lemma 10, we need at most 9 iterations to reduce the number to 5. Indeed:

705 − 2115 − 715 − 75 − 225 − 275 − 95 − 35 − 15 − 5.

Interestingly, this back-and-forth jumping between two and three-digit numbers is an optimal path for 705. This result comes from computer analysis of all possible numbers that can be reached in a specified number of steps.

We now consider the numbers that are not divisible by 5. Among all numbers that have to be reduced to one of the roots, we find some cases that do not follow the general rule of reduction. These are the numbers which have a substring w = d_{p} … d_{k} with d_{k} ≠ 0 and d_{k−1} = 0. We cover them in the following two lemmas.

Lemma 12. Any number N of the form N = k · 10^{ℓ} + d, where d ∈ {1, 3, 7, 9} and ℓ ≥ 2, can be reduced by at least one digit.

Proof. The proof uses induction and is similar to the one of Lemma 10. Let N = k·Z(ℓ−1)·d and d ∈ {7, 9}. Since ℓ ≥ 2, the number N can be reduced by one digit as follows:

k · Z(ℓ − 1) · d − (3k) · Z(ℓ − 2) · (3d) − k · Z(ℓ − 2) · (3d) − k · Z(ℓ − 2) · d  (1)

and

|k · Z(ℓ − 2) · d| = |N| − 1.

The remaining cases are when d = 3 or d = 1. Since we have the reduction

k · Z(ℓ − 1) · 1 − k · Z(ℓ − 1) · 3 − k · Z(ℓ − 1) · 9,

we can use operations in (1) to reduce the last number again to a shorter one.

Lemma 13. Any number N of the form N = k · 10^{ℓ} + d, where d ∈ {2, 4, 6, 8} and ℓ ≥ 2 can be reduced by at least one digit.

Proof. The proof is up to obvious modification the same as for Lemma 12. The case d = 2 can be reduced to the case d = 6 and the cases d ∈ {4, 6, 8} are reduced like in (1).

Theorem 14. Any odd number N that is not divisible by 5 reduces to 1.

Proof. Figure 3 in Appendix A is a partial graph connecting all at most two-digit numbers (and some with more digits if necessary) to 1.

By Lemma 12 it is enough to prove the result for at most two-digit numbers. Indeed, if the number has more digits, we either apply Lemma 12 to remove the string 0 · d or use the diagram in Figure 3 (see Appendix A) to reduce the number from right to left by at least one digit. Then we use recursion to reduce the number to 1.

Theorem 15. Any even number N that is not divisible by 5 reduces to 2.

Proof. Figure 4 in Appendix A is a partial graph connecting all two-digit numbers with 2.

By Lemma 13 it is enough to prove the result for at most two-digit numbers. Indeed, if the number has more digits, we either apply Lemma 13 to remove the string 0 · d or use the diagram in Figure 4 (see Appendix A) to reduce the number from right to left by at least one digit. Then we use recursion to reduce the number to 2.

Let us summarize the results obtained in this section.

Theorem 16. Let N be a positive integer and N = k · 10^{ℓ} for some k > 0 and ℓ ≥ 0. Then:

1. if k is odd and not divisible by 5, then N reduces to the root 10^{ℓ},

2. if k is even and not divisible by 5, then N reduces to the root 2 · 10^{ℓ},

3. if k is odd and divisible by 5, then N reduces to the root 5 · 10^{ℓ}.

Furthermore, each root defines a distinct connected component of the graph G of the Choix de Bruxelles operation of order three.

4 Numbers that are reached in n steps

For the part of calculation presented in this article we used the script written in Python. The script is provided in the accompanying file. With the aid of that script we find the cardinality of the set of all numbers that can be reached in n steps. We gather them in Table 3.

Iteration  Starting number
1  2  5
3  4  6  15
4  7  18  58
5  18  74  269
6  58  368 1401
7  259 2128 8243
8  1534 14511 55438
9  11329 112298 423551
10  95438

Table 3: How many numbers can be reached in n iterations?

5 Counting steps

Let τ(N) be the minimal number of steps to reach N from 1, 2 or 5 using the Choix de Bruxelles operation of order three. The values for small N are gathered in Table 4. Note that in this section we do not consider numbers that are divisible by 10.

We now provide upper and lower bounds on τ(N) for large values of N. Let τ_{1}, τ_{2} and τ_{5} be the functions counting steps for those numbers which root is 1, 2 and 5, respectively.

First, we discuss upper bounds.

Lemma 17. Any number of the form N = 10a + 5 can be reduced to 5 in at most 6 · |N| − 6 operations. In particular, τ_{5}(N) ≤ 6 · |N| − 6 for all admissible N.

\begin{matrix}N & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ τ(N) & 0 & 0 & 1 & 8 & 0 & 1 & 10 & 9 & 2 \\ N & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 \\ τ(N) & 11 & 7 & 10 & 7 & 1 & 6 & 9 & 2 & 9 \\ N & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 \\ τ(N) & 9 & 9 & 8 & 8 & 6 & 8 & 3 & 9 & 7 \end{matrix}

Table 4: The number of steps to reach N from one of the roots. Multiples of 10 are not included.

Proof. It is enough to count the number of iterations required to reduce the number N by one digit. We consider the cases and use Figure 2 and Lemma 10:

1. the number that does not end with 05 requires up to 6 operations to be reduced by one digit,

2. the number that does end with 05 requires exactly 3 operations to be reduced by one digit.

In any case reduction by at least one digit requires at most 6 iterations, hence at most 6 · (|N| − 1) operations are required to reach 5 from N.

Proposition 18. The reduction of numbers of the form N = 10a + 5 can be improved to 2 digits per at most 9 iterations.

Proof. This proof is computer assisted. With the aid of the algorithm written in Python we can check that all three-digit numbers can be reduced to 5 with at most 9 iterations. Moreover, we can also check that all four-digit numbers of the form d_{1} · 0 · d_{3} · 5 can be reduced to a two-digit number with at most 9 steps. Then, for the remaining numbers, we can use recursion to reduce the number from right to left by two digits unless string Z(ℓ) · A with |A| = 2 and ℓ ≥ 2 appears.

The case A = 05 is covered by Lemma 10 and requires exactly 6 iterations to reduce by 2 digits.

The remaining cases are the numbers of the form N = B ·Z(ℓ)·d·5 with d ∈ {1, 2, …, 9} and ℓ ≥ 2. If d ≥ 3, then we use the following reduction:

B · Z(ℓ) · (10d + 5) − (3[B]) · Z(ℓ − 1) · (30d + 15)− − B · Z(ℓ − 1) · (30d + 15) − B · Z(ℓ − 1) · (10d + 5)

and we have

|B · Z(ℓ − 1) · (10d + 5)| = |N| − 1.

If d < 3, then we multiply d by 3 once to get to the previous case.

From the above it follows that any string of the form B · Z(2) · A can be reduced to B · A′ with |B · Z(2) · A| ≥ |B · A′| + 2 in at most 7 iterations, which is sufficient for the statement of proposition.

Example 19. We use Proposition 18 to reduce 30015 by two zeroes in 7 steps. We have the following chain:

30015 − 30035 − 90105 − 30105 − 3035 − 9105 − 3105 − 335.

Lemma 20. Any odd number N that is not divisible by 5 can be reduced to 1 in at most 12 · |N| operations. In particular, τ_{1}(N) ≤ 12 · |N| for all admissible n.

Proof. Follows directly from Theorem 14 and Lemma 12, where the reduction by at least one digit of any at least two-digit number and the reduction of any single-digit number to 1 can be can be done in at most 12 iterations.

Lemma 21. Any even number N that is not divisible by 5 can be reduced to 2 in at most 10 · |N| operations. In particular, τ_{2}(N) ≤ 10 · |N| for all admissible n.

Proof. Follows directly from Theorem 15 and Lemma 13, where the reduction by at least one digit of any at least two-digit number and the reduction of any single-digit number to 2 can be can be done in at most 10 iterations.

Remark 22. Bounds for τ_{5} can be improved via Proposition 18, giving the following:

τ_{5}(N) ≤ \begin{cases}9k, & if |N| = 2k + 1 for some k ≥ 0; \\ 9k − 3, & if |N| = 2k for some k > 0. \end{cases}

These imply the following simple estimation:

τ_{5}(N) ≤ 4.5 · |N| − 3.

Let us discuss lower bounds. To do this, we first look at the greedy algorithm described in Theorem 1. With the aid of that algorithm we can reach the following numbers. Let r_{i}(n) be the largest number obtainable according to that theorem after n iterations with the starting number i ∈ {1, 2, 5}.

Notice that:

1. by Table 5 we have

r_{1}(n + 4) = [6124 · (r_{1}(n))] for each n ≥ 5,

2. by Table 6 we have

r_{2}(n + 4) = [3189 · (r_{2}(n))] for each n ≥ 5,

\begin{matrix}n & r_{1}(n) & n & r_{1}(n) \\ 0 & 1 & 10 & 61246189 \\ 1 & 3 & 11 & 612461827 \\ 2 & 9 & 12 & 6124618221 \\ 3 & 27 & 13 & 61246124663 \\ 4 & 221 & 14 & 612461246189 \\ 5 & 663 & 15 & 6124612461827 \\ 6 & 6189 & 16 & 61246124618221 \\ 7 & 61827 & 17 & 612461246124663 \\ 8 & 618221 & 18 & 6124612461246189 \\ 9 & 6124663 & 19 & 61246124612461827 \end{matrix}

Table 5: Values of r_{1} for small n.

\begin{matrix}n & r(n) & n & r(n) \\ 0 & 2 & 10 & 318936318 \\ 1 & 6 & 11 & 3189363124 \\ 2 & 18 & 12 & 31893631212 \\ 3 & 124 & 13 & 318931893636 \\ 4 & 1212 & 14 & 3189318936318 \\ 5 & 3636 & 15 & 31893189363124 \\ 6 & 36318 & 16 & 318931893631212 \\ 7 & 363124 & 17 & 3189318931893636 \\ 8 & 3631212 & 18 & 31893189318936318 \\ 9 & 31893636 & 19 & 318931893189363124 \end{matrix}

Table 6: Values of r_{2} for small n.

3. by Table 7 we have r_{5}(n + 1) = [1 · (r_{5}(n))] for each n ≥ 1.

The last case can be expressed for n ≥ 0 as

r_{5}(n) = ∑_{k=0}^{n} 10^{k} + 4 = \frac{10^{n+1} − 1}{9} + 4 = \frac{10^{n+1} + 35}{9}.

With the above in mind we can formulate the range in which the numbers r_{i}(n) are possible.

\begin{matrix}n & r(n) \\ 0 & 5 \\ 1 & 15 \\ 2 & 115 \\ 3 & 1115 \\ 4 & 11115 \\ 5 & 111115 \\ 6 & 1111115 \end{matrix}

Table 7: Values of r_{5} for small n.

Theorem 23. For all admissible n, the following estimates hold:

6.124 · 10^{n−3} < r_{1}(n) < 6.125 · 10^{n−3},  n ≥ 9,
3.189 · 10^{n−2} < r_{2}(n) < 3.190 · 10^{n−2},  n ≥ 9,

r_{5}(n) = \frac{10^{n+1} + 35}{9},  n ≥ 0.

Let R_{i}(n) be the largest number that is possible to obtain from i in n steps according to the Choix de Bruxelles operation. Note that R_{i} differs from r_{i}, since r_{i} follows greedy algorithm. We now prove the following theorem.

Theorem 24. For all i ∈ {1, 2, 5} and for all n we have r_{i}(n) = R_{i}(n).

Proof. By the computer calculation, the result is true for all n ≤ 9.

Assume n ≥ 10. The candidates for R_{i}(n) are the numbers that can be obtained from all numbers that are reached in at most n − 1 iterations of the operation. Since we are looking for the largest number, we can, according to Theorem 5, discard all numbers that are less than r_{i}(n)/10.

Let us start with the case i = 1. The set of remaining candidates forms a pattern of period 4 starting at ninth iteration.

iteration number (in string representation)
5 + 4b K · 663
6 + 4b K · 6189
7 + 4b K · 61827

                    8 + 4b K · 618221

Here, the concatenation of b ≥ 1 copies of the string 6124 is denoted by K. In each iteration the largest number that is obtained comes from the largest number obtained in the previous iteration, hence R_{1}(n) = r_{1}(n). We skip the remaining numbers (there are many numbers starting with the block K).

Let i = 2. As above, we obtain a period 4 pattern of the largest numbers in each iteration, starting from ninth iteration.

iteration number (in string representation)
5 + 4b L · 3636
6 + 4b L · 36318

                    7 + 4b L · 363124
                    8 + 4b L · 3631212

Here, the concatenation of b ≥ 1 copies of the string 3189 is denoted by L. In each iteration the largest number that is obtained comes from the largest number obtained in the previous iteration, hence R_{2}(n) = r_{2}(n).

The case i = 5 is simple, since in each iteration the largest numbers, after discarding the ones that are less than r_{i}/10, form a pattern. Let O(ℓ) denote the string of ℓ ones. Then the pattern looks as follows:

1 · O(ℓ) · 5,  4 · O(ℓ − 2) · 5,  34 · O(ℓ − 3) · 5,  334 · O(ℓ − 4) · 5, ⋯

and in each such step the largest number that can be obtained in the next step comes from the last one (where O(ℓ − k) is an empty string). Hence, R_{5}(n) = r_{5}(n).

Remark 25. The equality r_{i}(n) = R_{i}(n) is true for all n and i ∈ {1, 2, 5}. The original Choix de Bruxelles operation (recall that in that case the string is doubled or halved) considered by Angelini et al. [1] does not have this property, since r(7) = 448 but R(7) = 512.

The estimates provided in Theorem 23 also provide the least amount of iterations of the Choix de Bruxelles operation of order three to reach a certain number. Recall that τ_{i}(N) measures the number of steps required to reach the number N from i ∈ {1, 2, 5} for all admissible N.

Theorem 26. For all admissible N, the following estimates hold:

2.21 + log_{10} N < τ_{1}(N),  N ≥ 6124663,
1.49 + log_{10} N < τ_{2}(N),  N ≥ 31893636,
log_{10}(9N − 35) − 1 ≤ τ_{5}(N),  N ≥ 5.

Proof. The estimates follow from the bounds in Theorem 23 and the coincidence of functions r_{i} and R_{i} described in Theorem 24. For instance, if

r_{2}(n) < 3.19 · 10^{n−2},

then by rearranging we see that to reach the number N from 2 we need at least

2 + log_{10} \frac{N}{3.19} > 2 + log_{10} N − 0.503 > 1.49 + log_{10} N

steps.

Remark 27. The bounds for τ_{1} and τ_{2} are not sharp since the bounds in Theorem 23 can be improved with more decimal places. The bounds for τ_{5}(N) are sharp since we have equality for numbers r_{5}(n) in Theorem 23.

We can now summarize the bounds that we obtained in this section.

Theorem 28. For all admissible N, the following estimates hold:

2.21 + log_{10} N <τ_{1}(N) ≤ 12 · |N|,  N ≥ 6124663,
1.49 + log_{10} N <τ_{2}(N) ≤ 10 · |N|,  N ≥ 3189363,
log_{10}(9N − 35) − 1 ≤τ_{5}(N) ≤ 4.5 · |N| − 3,  N ≥ 5.

6 Final remarks

We conclude the article with three important remarks. Remark 29. The Choix de Bruxelles operation of order three is invertible by the assumption d_{p} ≠ 0. Otherwise, if we allowed substrings starting with zero to be divided by 3, all initial zeros would be removed from that string. For instance, the number 15 would be possible to obtain directly from 1000015. This modification would simplify some reasoning presented in the article, for instance the way we can reduce a number with long strings of zeroes in it. This however would not improve any of the provided bounds in general due to “extreme cases” with no digit 0. Remark 30. It is interesting to notice the major difference between the original operation described by Angelini et al. [1] and the one modified one. With a simple change of multiplier/divider the structure of the graph of the operation is vastly different. This is most likely due to the following facts:

• the numbers 3 and 10 are coprime, whereas 2 and 10 are not,

• the multiplication or division of numbers by 3 divides residue classes modulo 10 into four disjoint sets (see Lemma 6 and Lemma 9), where if the number is in one of the sets, it cannot be reduced to the number from the other set; in the original case all residue classes form just one such set.

Remark 31. It is interesting to investigate the Choix the Bruxelles operation of arbitrary order. If we, for example, pick order five, then we could find the graph has only two roots: 1 (all odd numbers) and 2 (all even numbers). Order seven and other prime orders, on the other hand, seem to have infinitely many roots.

7 Acknowledgments

The author would like to thank the editor and the referee for valuable comments that helped him improve a paper.

Appendix

A Diagrams of optimal reductions

91 93 99 297 237 217 2121 71 211 231 77 721 241 97 291 89 83 81 31 33 39 19 57 521 561 11 13 47 421 1261 49 41 43 129 187 67 27 9 3 1 53 51 17 121 123 321 37 1247 1741 1581 527 59 621 207 69 63 61 221 261 87 29 23 21 7 2181 727 79 73

Figure 3: Optimal reduction for all odd not divisible by 5 two-digit numbers. The numbers that are on the same level require the same number of reductions to reach 1. The reduction is optimal (but not unique).

372 1112 1332 1992 664 264 88 164 1192 1572 524 58 1216 1248 188 68 28 84 1212 404 1204 168 56 52 12 4 124 324 108 36 32 92 96 72 76 44 132 192 64 24 8 2 6 18 54 154 118 16 48 138 198 66 62 162 122 42 46 14 34 94 38 98 294 234 78 26 22 214 74 278 818 86 82

Figure 4: Optimal reduction for all even and not divisible by 5 two-digit numbers. The numbers that are on the same level require the same number of reductions to reach 1. The reduction is optimal (but not unique).

References

[1] É. Angelini, L. Blomberg, Ch. Neder, R. Sigrist, and N. J. A. Sloane, “Choix de Bruxelles”: a new operation on positive integers, Fibonacci Quart. 57 (2019), 195–200.

[2] E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Academic Press, 1982.

[3] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, available at

   https://oeis.org, 2020.

2010 Mathematics Subject Classification: Primary 11Y55; Secondary 11B37, 05C40. Keywords: Choix de Bruxelles operation, decimal representation, integer sequence, iteration, recurrence, graph.

(Concerned with sequences \underline{A323286}, \underline{A323287}, \underline{A323454}, \underline{A337321}, and \underline{A337357}.)

Received September 7 2020; revised versions received December 4 2020; January 5 2021. Published in Journal of Integer Sequences, January 30 2021.

Return to Journal of Integer Sequences home page.