The Comma Sequence is Finite in Other Bases

Robert Dougherty-Bliss Department of Mathematics Dartmouth College 27 N Main St Hanover, NH 03755 United States

                 rdbliss@dartmouth.edu

Natalya Ter-Saakov Department of Mathematics Rutgers University (New Brunswick) 110 Frelinghuysen Rd Piscataway, NJ 08854 United States

                   nt399@rutgers.edu

Abstract

The comma sequence (1, 12, 35, 94, …) is the lexicographically earliest sequence such that the difference of consecutive terms equals the concatenation of the digits on either side of the comma separating them. The behavior of a “generalized comma sequence” depends on the base in which the numbers are written, as well as the sequence’s initial values. We give a computational proof that all comma sequences in bases 3 through 633 are finite.

Angelini et al. conjectured a generating function formula related to the comma sequence and, from this, predicted that the final element of a comma sequence in base b should be roughly exp(O(b)). We give a combinatorial proof of Angelini’s conjecture, but also numerical evidence that this prediction is wrong. We provide a new random model for the comma sequence that predicts a final term of exp(O(b log b)), which aligns with our simulations.

Dedicated to Éric Angelini, a great friend of the OEIS.

1 Introduction

In 2006, Éric Angelini submitted \underline{A121805}, the “comma sequence,” to the On-Line Encyclopedia of Integer Sequences (OEIS) [?]. It is defined by a peculiar rule, best illustrated by listing the initial terms and their differences:

1 \underbrace{,}_{11} 12 \underbrace{,}_{23} 35 \underbrace{,}_{59} 94 \underbrace{,}_{41} 135 \underbrace{,}_{51} 186 \underbrace{,}_{62} 248 \underbrace{,}_{83} 331 \underbrace{,}_{13} 344, …

The comma sequence is the lexicographically earliest sequence of positive integers such that the difference of consecutive terms equals the concatenation of the digits on either side of the comma separating them. For example, the sequence contains 12, 35, which has a difference of 35 − 12 = 23, the concatenation of 2 (the digit to the left of the comma) and 3 (the digit to the right of the comma). The amazing fact about the comma sequence is that it contains exactly 2,137,453 terms. It starts at 1, reaches 99999945, and then terminates. Naturally, the question is why the sequence persists so long, why it terminated at that number in particular, and what happens if we slightly change the setup.

A (generalized) comma sequence in base b is the lexicographically earliest sequence which satisfies the comma rule with a particular fixed initial value. Angelini et al. [?] studied generalized comma sequences and obtained a number of results that we have extended. First, they proved that all comma sequences in base 3 are finite and conjectured that this is true for all bases. We have extended this to more bases.

Theorem 1. Comma sequences with arbitrary positive initial values are finite in bases 3 through 633.

The proof of this theorem includes reducing the problem to a finite set of cases, then checking them on a large computing cluster with a program written in the Go language. We give the mathematical details of this proof in Section 3, and the computational details in Section ??.

While thinking about the duration of comma sequences in different bases, Angelini et al. conjectured the following, which we have proved [?, Conjecture 7.1].

Theorem 2. The number D(b) of comma sequences in base b with initial values in [b^{m} − b^{2}, b^{m}) (with m ≥ 2) that do not reach b^{m} is independent of m and has ordinary generating function

∑_{b=2}^{∞} D(b)t^{b} = (1 − t)^{−1} (∑_{b=1}^{∞} \frac{t^{b(b+3)/2}}{(1 − t^{b})} − t^{2}) = t^{3} + 2t^{4} + 4t^{5} + 5t^{6} + ⋯  (1)

Angelini et al. (with help from Václav Kotĕs̆ovec) relied on this conjecture to reason that the final element of a base-b comma sequence should be roughly e^{2b}. More precisely, they estimated that a comma sequence ought to survive about 2b/ log(2b) “danger intervals,” which we define in Section 2. This estimate is accurate for small bases, but becomes worse for larger ones. In Section ??, we introduce a model that more accurately matches empirical simulations for large bases, but depends on a probabilistic conjecture that we cannot prove. It predicts that comma sequences should survive about b/2 + 1 intervals, which translates to an estimated length of b^{b/2+1} = e^{O(b log b)}.

We have been unable to prove that all comma sequences in bases other than 2 are finite. We could push our computations further than base 629 by finding small optimizations or using more computing power, but we do not see how this leads to a better theoretical understanding. The main problem remains open.

2 Background and examples

In this section we summarize some relevant background on comma sequences and give a number of examples. We begin with a more explicit definition of generalized comma sequences.

Definition 3. The generalized comma sequence in base-b with initial condition v is the sequence (a(n))_{n≥1} defined as follows: a(1) = v; for n > 1, if x is the least significant base-b digit of a(n − 1), then

a(n) = a(n − 1) + bx + y,  (2)

where y is the most significant digit of a(n) and is the smallest such y, if one exists. If no such y exists, then the sequence terminates.

Every positive integer has at most two positive integers which satisfy the comma-concatenation rule. For example, starting with the decimal number 14, we could write either “14, 59” or “14, 60.” The definition says that we always choose the smallest next integer.

The comma sequence corresponds to v = 1 and b = 10. The first ten terms of the base-10 comma sequences with initial values v = 1, 2, …, 10 are as follows:

1, 12, 35, 94, 135, 186, 248, 331, 344, 387 … 2, 24, 71, 89, 180, 181, 192, 214, 256, 319 … 3, 36 (terminates) 4, 48, 129, 221, 233, 265, 318, 402, 426, 490 … 5, 61, 78, 159, 251, 263, 295, 348, 432, 456 … 6, 73, 104, 145, 196, 258, 341, 354, 397, 471 … 7, 85, 136, 197, 269, 362, 385, 439, 534, 579 … 8, 97, 168, 250, 252, 274, 317, 390, 393, 427 … 9, 100, 101, 112, 133, 164, 206, 268, 351, 364 … 10, 11, 23, 58, 139, 231, 243, 275, 328, 412 …

These sequences are all finite. Their lengths are recorded in \underline{A330128}.

The first ten terms of the base-3 comma sequences with initial values v = 1, 2, 3 are as follows (given in base 3):

(1)_{3}, (12)_{3}, (110)_{3}, (111)_{3}, (122)_{3}, (221)_{3}, (1002)_{3}, (1100)_{3}, (1101)_{3}, (1112)_{3} …
(2)_{3}, (100)_{3}, (101)_{3}, (112)_{3}, (211)_{3} (terminates)
(10)_{3}, (11)_{3} (terminates)

(We use the notation (d_{k}, d_{k−1}, …, d_{0})_{b} to represent the integer d_{k}b^{k} + d_{k−1}b^{k−1} + ⋯ + d_{0} in base-b where the d_{i} are base-b digits.) These sequences are also all finite; the first lasts for 17 terms.

The numbers which do not have successors, meaning integers at which comma sequences terminate, were termed landmines by Angelini et al. [?]. They are precisely the integers in base-b of the form

(b − 1, b − 1, …, b − 1, x, y)_{b}

where x and y are nonzero digits which sum to b − 1 [?, Theorem 5.2]. For example, in base-10, the integers 45, 99972, and 9999918 are all landmines. We will call these terminal points or values.

Terminal points live in the following small intervals just to the left of powers of b.

Definition 4. The base-b danger intervals are the intervals [b^{k} − b^{2}, b^{k}) for k ≥ 2.

Some properties about comma sequences are best stated in terms of graphs. Let C_{b} be the directed graph on the positive integers which contains the edge i → j if and only if “i, j” satisfies the comma-concatenation rule in base-b. (This does not mean that the comma sequence starting at i would have j as its next term, just that j could be the next term, provided that it is the smallest option.)

Every vertex in C_{b} has out-degree at most two and in-degree at most 1. The only vertices with in-degree 0 are of the form

(d, 0, 0, …, 0)_{b},

where d ∈ {2, 3, …, b − 1} [?, Theorems 5.4, 5.5].

Angelini et al. also showed that C_{b} is the disjoint union of finitely many directed trees. As a corollary, C_{b} contains an infinite path, meaning that if comma sequences were allowed to pick either of two possible successors, then there would be at least one infinite comma sequence in every base [?, Theorems 5.6].

3 How to prove finiteness

Neil Sloane and Giovanni Resta communicated to us the rough idea behind their proof that all comma sequences in base-3 are finite. In this section we describe their idea and its generalization to arbitrary bases. This section contains primarily mathematical details, while Section ?? contains more details about the computation and its implementation.

3.1 Overview

Angelini et al. proved that the behavior of comma sequences is determined by their values within relatively small intervals. Specifically, if you know the last time a comma sequence is in the interval

[d · b^{k} − b^{2}, d · b^{k}),

then you can predict the last time the sequence is in the “next” interval

[(d + 1) · b^{k} − b^{2}, (d + 1) · b^{k})

without actually computing the intermediate terms.

The idea rests on a simple observation. Here are some terms from the original comma sequence:

997, 1068, 1149, 1240, 1241, 1252, 1273, 1304, 1345, 1396, 1457, 1528, …

Their differences are

71, 81, 91, 01, 11, 21, 31, 41, 51, 61, 71, …

The observation is that, while the leading digit remains 1, the last digit of the difference remains 1, and the first digit follows a simple arithmetic progression. Angelini et al. gave a description of this progression which allows us to predict that the last term in [2000 − 100, 2000) is 1988, given only the information that the last term in [1000 − 100, 1000) is 997. The formula for the arithmetic progression is given in equation (??).

Definition 5. Given a base-b digit d, an integer 0 ≤ u < b^{2}, and a positive integer k, we write (d, u, k) to represent the integer d · b^{k} − u.

The tuples (d, u, k) represent points in the intervals [d · b^{k} − u, d · b^{k}). The observation of Angelini et al. amounts to saying that we can compute a map

(d, u, k) → (d′, u′, k′)

which tells us how comma sequences move from one interval to the next. For example, the jump from 997 to 1988 is represented as (1, 3, 2) → (2, 12, 3).

Our contribution is that the map (d, u, k) → (d′, u′, k′) is determined by only finitely many k. Specifically, for each base b there exists a finite graph G′_{b} which contains a cycle if and only if there are infinite base-b comma sequences. Figure ?? is a drawing of G′_{3}, which has no cycles. Figure ?? is a condensed drawing of G′_{4}, which also does not contain a cycle. Therefore, all comma sequences in bases 3 and 4 are finite. The only exception we know of is b = 2; see Figure ??.

3.2 Infinite graph construction

Here we construct an infinite directed graph that represents the comma map

(d, u, k) → (d′, u′, k′).

We first need a technical lemma which says that we do not need to consider all (d, u, k).

Let us first illustrate this with an example. If a base-10 comma sequence reaches the value (1, 99, 3), then it proceeds as follows:

(1, 99, 3) → (1, 80, 3) → (1, 71, 3).

The last point is the last value the sequence takes in the interval [900, 1000). It turns out that comma sequences behave identically on all danger interval. For example, if a base-10 comma sequence reaches (1, 99, 7), then it proceeds as follows:

(1, 99, 7) → (1, 80, 7) → (1, 71, 7).

All that has changed is k, but the behavior of the u’s are the same. The below lemma states that this is true in general.

Lemma 6 (Minimal u’s). For any base b, any integer k > 2, and any nonzero base-b digit d, there exists a smallest finite set U(b, d) that satisfies the following properties:

(a) If a base-b comma sequence has a value in [d · b^{k} − b^{2}, d · b^{k}), then its final value in this interval is d · b^{k} − u for some u ∈ U(b, d).

(b) U(b, d) is independent of k.

(c) If d ≠ 1, then

U(b, d) = {(r, s)_{b} | r + s < b, 0 < s < b} ∪ {(r, s)_{b} | r + s = b, s < d}.

(d) If d = 1, then

U(b, 1) = {(r, s)_{b} | r + s ≤ b, 0 < s < b}.

Proof. Begin with d > 1. The final value of a base-b comma sequence in [d · b^{k} − b^{2}, d · b^{k}) has the form (d − 1, b − 1, …, b − 1, x, y)_{b} for some 0 ≤ x, y < b. Because this is the last term in the interval, the next term is

(d − 1, b − 1, …, b − 1, x, y) + (y, d)_{b},

The relationship between (x, y) and (r, s) is

(x, y)_{b} + (r, s)_{b} = b^{2}.

There are two cases: First, x + y ≥ b. Since y > 0, we have (r, s) = (b − 1 − x, b − y) and the inequality x + y ≥ b is equivalent to r + s ≤ b − 1 and s > 0.

Second, x + y = b − 1 and y + d ≥ b. Note that

(d − 1, b − 1, …, b − 1, x, y) + (y, d − 1)_{b}

is also no longer in the interval, so y + d − 1 ≥ b. This again implies y > 0, and so (r, s) = (b − 1 − x, b − y), and the conditions

x + y = b − 1
y + d ≥ b + 1

are equivalent to

r + s = b
s < d.

The reasoning for d = 1 is similar. The only difference is in the second case, when the inequality y + d − 1 ≥ b becomes y + b − 1 ≥ b. The rest of the argument is identical.

As an example of the lemma, here are the sets U(3, d):

U(3, 1) = {1, 2, 4, 5, 7}
U(3, 2) = {1, 2, 4, 7}.

Definition 7. The digraph G_{b} consists of vertices labeled (d, u, k) with base-b digit d, a minimal u ∈ U(b, d), and an integer k ≥ 0. The edge (d, u, k) → (d′, u′, k′) exists if the latter is the immediate image of the former under the comma map.

An infinite comma sequence in base b corresponds to an infinite path in G_{b}. Therefore, our main goal is to determine whether such paths exist.

3.3 Finiteness of the comma map

We now study the comma map (d, u, k) → (d′, u′, k′) in more detail.

Given (d, u, k) which is not a terminal point, we want to compute the next value (d′, u′, k′) as a function of (d, u, k). For example, if we have a base-10 sequence at the value (6, 8, 3) (also known as 5992), where does it go next? Both d′ and k′ are easy:

d′ = \begin{cases}d + 1 & if d < b − 1; \\ 1 & otherwise, \end{cases}

k′ = \begin{cases}k & if d < b − 1; \\ k + 1 & otherwise. \end{cases}

So a partial answer is (6, 8, 3) → (7, u′, 3). The main difficulty is determining u′.