On Curling Numbers of Integer Sequences

Benjamin Chan, Intel Processor Architecture, 2111 NE 25th Avenue, Hillsboro, OR 97124, USA, Email: [email protected], John P. Linderman, 1028 Prospect Street, Westeld, NJ 07090, USA, Email: [email protected], N. J. A. Sloane,1 The OEIS Foundation Inc., 11 South Adelaide Avenue, Highland Park, NJ 08904, USA, Email: [email protected], and Allan R. Wilks, 425 Ridgeview Avenue, Scotch Plains, NJ 07076, USA, Email: [email protected]. Abstract2 . Given a nite nonempty sequence S of integers, write it as XY k , where Y k is a power of greatest exponent that is a sux of S : this k is the curling number of S . The curling number conjecture is that if one starts with any initial sequence S , and extends it by repeatedly appending the curling number of the current sequence, the sequence will eventually reach 1. The conjecture remains open. In this paper we discuss the special case when S consists just of 2s and 3s. Even this case remains open, but we determine how far a sequence consisting of n 2s and 3s can extend before reaching a 1, conjecturally for n 80. We investigate several related combinatorial problems, such as nding c(n, k ), the number of binary sequences of length n and curling number k , and t(n, i), the number of sequences of length n which extend for i steps before reaching a 1. A number of interesting combinatorial problems remain unsolved.

The curling number conjecture

Given a nite nonempty sequence S of integers, write it as S = XY k , where X and Y are sequences of integers and Y k is a power of greatest exponent that is a sux of S : this k is the curling number of S , denoted by cn(S ). X may be the empty sequence ; there may be several choices for Y , although the shortest such Y which achieves k (which as we shall see in 3.1 is primitive) is unique. For example, if S = 0 1 2 2 1 2 2 1 2 2, we could write it as XY 2 , where X = 0 1 2 2 1 2 2 1 and Y = 2, or as XY 3 , where X = 0 and Y = 1 2 2. The latter representation is to be preferred, since it has k = 3, and as k = 4 is impossible, the curling number of this S is 3. The following conjecture was stated by van de Bult et al. [2]: Conjecture 1. The curling number conjecture. If one starts with any initial sequence of integers S , and extends it by repeatedly appending the curling number of the current sequence, the sequence will eventually reach 1.
1 2

To whom correspondence should be addressed. A preliminary report on the work in Section 2 was given in [3]

In other words, if S0 = S is any nite nonempty sequence of integers, and we dene Sm+1 to be the concatenation Sm+1 := Sm cn(Sm ) for m 0 , (1) then the conjecture is that for some t 0 we will have cn(St ) = 1. The smallest such t is the tail length of S0 , denoted by (S0 ) (and we set (S0 ) = if the conjecture is false). For example, suppose we start with S0 = 2 3 2 3. By taking X = , Y = 2 3, we have S0 = Y 2 , so cn(S0 ) = 2, and we get S1 = 2 3 2 3 2. By taking X = 2, Y = 3 2 we get cn(S1 ) = 2, S2 = 2 3 2 3 2 2. By taking X = 2 3 2 3, Y = 2 we get cn(S2 ) = 2, S3 = 2 3 2 3 2 2 2. Again taking X = 2 3 2 3, Y = 2 we get cn(S3 ) = 3, S4 = 2 3 2 3 2 2 2 3. Now, unfortunately, it is impossible to write S4 = XY k with k > 1, so cn(S4 ) = 1, S5 = 2 3 2 3 2 2 2 3 1, and we have reached a 1, as predicted by the conjecture. For this example, (S0 ) = 4. (If we continue the sequence from this point, it joins Gijswijts sequence, discussed in 5.) Some of the proofs in van de Bult et al. [2] could be shortened and the results strengthened if the conjecture were known to be true. All the available evidence suggests that the conjecture is true, but it has so far resisted all attempts to prove it. In this paper we report on some extensive investigations into the case when the starting sequence consists of 2s and 3s (although even in this special case the conjecture remains open). In Section 2 we study how far a starting sequence consisting of n 2s and 3s can extend before reaching a 1. Call the maximum such length (n). That is, (n) is the maximal value of the tail length (S0 ) taken over all sequences S0 of 2s and 3s of length n. We determine (n) for all n 48, and conjecturally for all n 80 (Table 1 and Figure 1). The data suggests some properties that should be possessed by especially good starting sequences (Properties P2, P3, P4 in 2.2). Although we have not found any algebraic construction for good starting sequences, Section 2.3 describes a method which sometimes succeeds in building starting sequences of greater length. The algorithm which allowed us to extend the search to length 80 is discussed in 2.4. We would not be surprised if the conjecture in this special case turns out to be a consequence of known results on the unavoidability of patterns in long binary sequenceswe discuss this briey in 2.5. Section 3 is devoted to the combinatorial question: what is the number c(n, k ) of binary sequences of length n and curling number k ? This seems to be a surprisingly dicult problem, and we have succeeded only in relating c(n, k ) to two subsidiary quantities: p(n, k ), the number of such sequences that are primitive, and p (n, k ), the number that are both primitive and robust (see 3.1). The main results of this section are the formulas for c(n, k ) in Theorems 8 and 20. With their help we are able to enumerate the curling numbers of all binary sequences of length n 104. The resulting table can be seen in entry A2169553 in [9]. The number of binary sequences with curling number 1, c(n, 1) (A122536), is especially interesting and is discussed in 3.4. Some further recurrences given there enable us to compute c(n, 1) for n 200 (although we still do not know an explicit formula). We make frequent use of the classical Fine-Wilf theorem, and it and two other preliminary results are given in 3.2. The dierences d(n, k ) := 2 c(n 1, k ) c(n, k ) show the structure of the c(n, k ) table more clearly than the numbers c(n, k ) themselves, and are the subject of 3.6. In Section 4, we study the number t(n, i) of sequences of length n with tail length i, where 0 i (n). By direct search we have determined t(n, i) for n 48 (A217209), although without nding any recurrences (except for t(n, 0), which is the same as c(n, 1)). The terms in each row of the t(n, i) table occur in clumps, at least for n 48. In 4.1 and 4.2 we investigate some statistics of the t(n, i) table, although we are a long way from nding a model which explains the clumps.
3

Throughout this article, six-digit numbers prexed by A refer to entries in the OEIS [9].

Sections 4.3, 4.4, 4.5 discuss some combinatorial questions related to tail lengths. If the starting sequence S0 is suciently long, it seems plausible that prexing S0 with a 2 or 3 is unlikely to decrease the tail length. If one of these prexes decreases the tail length, we call S0 rotten, and if both prexes 2 and 3 decrease the tail length we call it doubly rotten. Rotten sequences certainly exist, but up to length 34 there are no doubly rotten sequences, and we conjecture than none exist of any length (see Conjecture 22). If this conjecture were true, it would explain a certain phenomenon that we observed in 2.2, and it would also imply that (n + 1) (n) for all n, something that we do not know at present. In Section 5 we briey describe Gijswijts sequence (A090822), which was the starting point for this investigation. The last section summarizes the open problems mentioned in the paper. Notation Since the starting sequence S can be any sequence of integers, it seems appropriate in this paper to speak about sequences rather than words over some alphabet. However, we will make use of certain terminology (such as prex, sux) from formal language theory (cf. [7]). Sequences will be denoted by upper case Latin letters. S k means SS S , where S is repeated k times. The length of S is denoted by |S |. denotes the empty sequence. Sets of sequences will be denoted by script letters (e.g., C (n, k )) and their cardinalities by the corresponding lower case Latin letters (e.g., c(n, k )). Greek letters and other lower case Latin letters will also denote numbers. The symbol # denotes the cardinality of a set. The curling number of S is denoted by cn(S ). For a starting sequence S0 := s1 s2 sn of length n, where the si are arbitrary integers, we dene Sm+1 to be the concatenation Sm cn(Sm ) = s1 sn+m+1 for m 0. If cn(St ) = 1 for some t 0, then we call the smallest such t the tail length of S0 , denoted by (S0 ), and the corresponding sequence S (e) := St = s1 sn+t is the extension of S0 . If no such t exists, then we set (S0 ) = , S (e) = S (and the curling number conjecture would be false).

2
2.1

Sequences of 2s and 3s
Maximal tail length (n)

One way to approach the conjecture is to consider the simplest nontrivial case, where the initial sequence S0 contains only 2s and 3s, and see how far such a sequence can extend using the rule (1) before reaching a 1. Perhaps if one were suciently clever, one could invent a starting sequence that would never reach 1, which would disprove the conjecture. Of course it cannot reach a number greater than 3, either, for the rst time this happens the next term will be 1. So the sequence must remain bounded between 2 and 3. Unfortunately, even this apparently simple case has resisted our attempts to solve it. At the end of this section (see 2.5) we will mention some slight evidence that suggests the conjecture is true. First we report on our numerical experiments. Let (n) denote the maximal tail length that can be achieved before a 1 appears, for any starting sequence S0 consisting of n 2s and 3s. If a 1 is never reached, we set (n) = . The curling number conjecture would imply (n) < for all n. By direct search, we have found (n) for all n 48. (The values for n 30 were given in [2].) The results are shown in Table 1 and Figure 1, together with lower bounds (which we conjecture are in fact equal to (n)) for 49 n 80. The values of (n) also form sequence A217208 in [9]. In [2], before we began computing (n), we did not know how fast it would growwould it be a polynomial, exponential, or other function of n? Even now we still do not know, since we have only limited data. But up to n = 48, and probably up to n = 80, (n) is a piecewise constant function 3

n (n) n (n) n (n) n (n) n (n) n (n) n (n)

1 0 13 112 25 120 37 120 49 131 61 131 73 132

2 2 14 118 26 120 38 120 50 131 62 131 74 132

3 2 15 118 27 120 39 120 51 131 63 131 75 132

4 4 16 118 28 120 40 120 52 131 64 131 76 133

5 4 17 118 29 120 41 120 53 131 65 131 77 173

6 8 18 118 30 120 42 120 54 131 66 131 78 173

7 8 19 119 31 120 43 120 55 131 67 131 79 173

8 58 20 119 32 120 44 120 56 131 68 132 80 173

9 59 21 119 33 120 45 120 57 131 69 132

10 60 22 120 34 120 46 120 58 131 70 132

11 112 23 120 35 120 47 120 59 131 71 132

12 112 24 120 36 120 48 131 60 131 72 132

Table 1: Lower bounds on (n), the maximal tail length that can be achieved before a 1 appears, for any starting sequence S0 consisting of n 2s and 3s. Entries for n 48 are known to be exact; the other entries are conjectured to be exact.

Figure 1: Scatter-plot of lower bounds on (n), the maximal tail length that can be achieved before a 1 appears, for any starting sequence S0 consisting of n 2s and 3s. Entries for n 48 are known to be exact; the other entries are conjectured to be exact. of n. There are occasional jump points, where (n) > (n 1), but in between jump points (n) does not change. Of course this piecewise constant behavior is not incompatible with polynomial or exponential growth, if the jump points are close enough together, but up to n = 80 this seems

not to be the case. There are long stretches where (n) is at. A probabilistic argument will be given in 4 which suggests (not very convincingly) that, on the average, (n) may be roughly c1 n, for a constant c1 1.34. Up to n = 49, (n) never decreases, although we cannot prove that this is always true (see 4.3). The jump points are at n = 1, 2, 4, 6, 8, 9, 10, 11, 14, 19, 22, 48 and we believe the next three values are 68, 76 and 77 (A160766).

2.2

Properties of good starting sequences

From n = 2 through 48 (and probably through n = 80) the starting sequences S0 which achieve (n) at the jump points are unique. These especially good starting sequences are listed in Tables 2 and 3. For 2 n 48 (and probably for 2 n 80) these sequences S0 also have the following properties: (P2) S0 begins with 2. (P3) S0 does not contain the subword 3 3. (P4) S0 contains no nonempty subword of the form V 4 (and in particular does not contain 2 2 2 2). n 1 2 4 6 8 9 10 11 14 19 22 48 Starting sequence 2 22 2323 222322 23222323 223222323 2323222322 22323222322 22323222322323 2232232322232232232 2322322323222323223223 223223232223222322322232232322232223223222322323

Table 2: Starting sequences consisting of n 2s and 3s for which (n) > (n 1), complete for 1 n 48. These are empirical observations. However, since they certainly hold for the rst 249 1 choices for S0 , we venture to make the following conjecture: Conjecture 2. If a starting sequence S0 of 2s and 3s of length n 2 achieves (n) with (n) > (n 1), then S0 is unique and has properties P2, P3 and P4. We can at least prove one result about these especially good starting sequences. Let S0 = s1 s2 sn be any sequence of integers with extension S (e) = St = s1 sn+t , where cn(St ) = 1. Call S0 weak if each Sr (r = 0, . . . , t 1) can be written as XY sn+r+1 with X = . In other words, S0 is weak if the initial term s1 is not necessary for the computation of the curling numbers sn+1 , . . . , sn+t . This implies that (S0 ) = (s2 sn ), and establishes 5

n Starting sequence 68 2 2 3 2 2 3 2 2 2 3 2 2 3 2 3 2 2 2 3 2 2 2 3 2 2 3 2 2 2 3 2 2 3 2 2 2 3 2 2 3 2 3 2 2 2 3 2 2 23223222322322232232 76 2 3 2 2 2 3 2 2 3 2 2 2 3 2 2 3 2 3 2 2 2 3 2 2 2 3 2 2 3 2 2 3 2 2 2 3 2 2 3 2 2 2 3 2 2 3 2 3 2223222322322322232232223223 77 2 2 3 2 2 2 3 2 3 2 2 2 3 2 2 2 3 2 2 3 2 2 2 3 2 2 2 3 2 3 2 2 2 3 2 2 2 3 2 2 3 2 2 2 3 2 2 2 32322232223223232223223222323 Table 3: Conjectured to be the complete list of starting sequences of n 2s and 3s for which (n) > (n 1), for the range 49 n 80. Lemma 3. If a starting sequence S0 of length n 2 achieves (n) > (n 1), then S0 is not weak. One further empirical observation is worth recording, concerning the starting sequences between jump points. Suppose n0 , n1 are consecutive jump points, so that (n) = (n 1) for n0 < n < n1 ,

and (n) > (n 1) at n = n0 and n1 . Then for n 48 and conjecturally for n 80, if n0 < n < n1 , one can obtain a starting sequence that achieves (n) by taking the starting sequence of length n0 and prexing it by a neutral string of n n0 2s and 3s that do not get used in the computation of (n). Although this is not surprising, we are unable to prove that such neutral prexes must always exist. We return to this topic in 4.3. The large gaps between the jump points at 22 and 48 and between 48 and 68 are especially noteworthy. In particular, we have (n) = 120 for 22 n 47 , and, conjecturally, (n) = 131 for 48 n 67 . (3) The data shown in Tables 1, 2, 3 and Figure 1 for n in the range 49 to 80 were obtained by computer search under the assumption that the starting sequence has the properties P3 and P4 mentioned above, although without making any assumption about uniqueness. As it turned out, assuming P3 and P4, the best starting sequences at the jump points are indeed unique and start with 2. Assuming P3 and P4 greatly reduces the number of starting sequences that must be considered. For example, simply excluding sequences that contain four consecutive 2s or four consecutive 3s reduces the number of candidates of length n from 2n to a constant times cn 2 , where c2 = 1.839 (cf. A135491). However, this by itself is not enough to enable us to reach n = 80. We discuss the algorithm that we used in more detail in 2.4. We should emphasize that in the (we believe unlikely) event that there are starting sequences of length n with 49 n 80 that achieve (n) but do not satisfy properties P3 and P4, it is possible our conjecture that there are jump points at lengths 68, 76, and 77 may be wrong, and there may be better starting sequences than those shown in Table 3. (2)

2.3

A construction for larger n

We have not succeeded in nding any algebraic constructions for good starting sequences. However, one simple construction enables us to obtain lower bounds on (n) for some larger values of n. Let 6

S0 be a sequence of length n that achieves (n), and let S (e) be its extension of length n + (n). Then in some cases the starting sequence S (e) S0 will extend to S (e) S (e) 2 and beyond before reaching a 1. For example, taking S0 to be the length 48 sequence in Table 2, the sequence S (e) S0 has length 179 + 48 = 227 and extends to a total length of 596 before reaching a 1, showing that (227) 369.

2.4

Computational details

Our results are complete for n 48 and are probably complete through n = 80. In order to extend the search this far, the algorithms used were specically tuned to the case of sequences of 2s and 3s. There is no easy way (as far as we know) to avoid the basic process of computing the extension of S (compute cn(S ), append it to S , and repeat until cn(S ) = 1), and so the focus is on computing cn(S ) quickly. In the following discussion we assume that S has length at least 36. The rst step is brute force: look up the curling number cn(sn35 sn ) in a table. Two bits are sucient to record cn, since we only care about whether it is 1, 2, 3 or 4; at two bits per entry, this table occupies 16 gigabytes. This provides a lower bound on cn(S ), and also gives a lower bound for the length of the repeated substring Y which maximizes cn(S ). For example, if cn(sn35 sn ) = 1, then any Y which gives cn(S ) > 1 must be at least 19 digits long, or there would have been two copies within the last 36 digits of S. There is also an upper bound on the length of Y . Since we are looking for that Y which maximizes cn(S ), we are only interested in Y s which could be repeated more times than the current best known value of cn(S ). For example, if we know cn(S ) 3, then we only want a Y which is repeated four times, and so we only need consider lengths up to the length of S divided by 4. We now consider the last n digits of S as a candidate for Y , for all values of n between the lower and upper bounds. The sequences are represented as 128-bit binary numbers, and so looking for repetitions of Y can be done with bit manipulation. A few shifts and ORs generate 4 copies of Y , or as many as will t in 128 bits. Then an XOR nds digits in which this diers from S , a bit scan locates the index of the rst dierence, and we can divide by the length of Y to nd how many times this Y is repeated. (In fact, all divisions are done with precomputed tables.) If some Y increases the best known value for cn(S ), then the upper bound on the length of Y can be revised downwards. If we reach 128 digits and are still going, we resort to a slow string-based routine. In practice this slow routine accounts for less than 1% of the programs execution time. To compute the conjectured values up to length 80, we exclude (most) strings containing 3 3 or a subword V 4 . Obviously we cannot check all 280 strings to see if they violate one of these conditions, so we need an ecient way to avoid considering them at all. To do this, we compute a 256 256 table which lists, for every string of length 8, all the length-8 strings which could legally follow it. We then construct S recursively in 8-digit blocks, ensuring that the rules are not broken within any two consecutive blocks. This is not perfect (it will allow a V 4 to slip by if V is 9 digits long, for example), but it eciently eliminates the vast majority of undesirable cases.

2.5

Unavoidable regularities

One reason we think the curling number conjecture may be true, at least in the special case of sequences of 2s and 3s, is that there are several theorems in formal language theory about the inevitability of regularities in long binary strings. A classical example is Shirshovs theorem [7, Theorem 7.1.4], [8, Theorem 2.4.3]. Unfortunately that does not quite do what we need, but it does oer hope that a proof along these lines may exist. Lyndons theorem [7, p. 67] is another example. Suppose we have a very long sequence of 2s and 3s generated by (1), and consider 7

its canonical decomposition into Lyndon words. There are relatively few Lyndon words that are possible (e.g., 2 2 2 2 is forbidden), but since this attack has not yet led to a contradiction we shall say no more about it.

Number of binary sequences with given curling number

In this section we study the number c(n, k ) of binary sequences of length n and curling number k . For consistency with the other sections, we continue to consider sequences of 2s and 3s, although for this question any alphabet of size 2 (such as {0,1}) would do equally well.

3.1

Primitive and robust sequences

A sequence S is imprimitive (or periodic) if it is equal to T i for some sequence T and an integer i 2. Otherwise, S is primitive [7, p. 7]. Lemma 4. Suppose S has curling number k . Then S can be written as XY k , possibly in several ways. The shortest such Y is primitive and unique, and has curling number < k if k > 1, curling number 1 if k = 1. Proof. Consider all possible ways of writing S = XY k , and let Y denote the set of such Y s of minimal length. Every Y Y is primitive, for if Y = T i , i 2, then S = XT ik , and cn(S ) ik > k , contradicting the denition of Y . To establish uniqueness, we observe that S = X1 Y1 k = X2 Y2 k with |Y1 | = |Y2 | implies Y1 = Y2 . If k > 1 and Y Y has curling number c k > 1, say Y = U V c , |V | 1, then S = X (U V c )k = X V c with c k , |V | < |Y |, a contradiction. Finally, if k = 1, certainly Y cannot have curling number greater than 1, or S would too. We denote the length of this shortest Y by . We let C (n, k, ) (for n 1, 1 k n, 1 n) denote the set of all S with the given values of n, k , and , c(n, k, ) := #C (n, k, ), n/k n/k C (n, k ) := =1 C (n, k, ), and c(n, k ) := #C (n, k ) = =1 c(n, k, ). If S has curling number 1 then the shortest Y for which S = XY is simply the last term of S , so = 1 and S C (n, 1, 1). The sets C (n, 1, ) for > 1 are empty. We let P (n, k ) (for 1 k n) denote the subset of primitive S C (n, k ), and p(n, k ) := #P (n, k ). Note that C (n, = P (n, 1), since curling number 1 implies primitive. 1) k Also let Q(n, k ) := i=1 P (n, i) (for 1 k n) denote the set of primitive sequences with curling number at most k , and q (n, k ) := #Q(n, k ) = k i=1 p(n, i). We also set q (n, 0) := 0 and q (n, k ) := q (n, n) for k > n. By denition, q (n, n) is the total number of aperiodic binary sequences of length n, and it is well known ([5]; see also entry A217943 in [9]) that (n) q (n, n) = 2d , (4) d
d|n

where is the M obius function (q (n, n) is sequence A027375). Call S P (n, k ) robust if no proper sux of S k+1 has curling number k + 1. Examples of non-robust sequences rst appear at length 5, where S = 3 2 2 3 2 C (5, 1) is not robust since S2 = 3 2 2 3 2 3 2 2 3 2 has the sux (2 3 2)2 . At length 8 there are examples with k = 2, such as S = 3 2 2 3 2 2 3 2, for which S 3 has the sux (2 3 2)3 . Let P (n, k ) denote the subset of robust S P (n, k ), and let p (n, k ) := #P (n, k ). 8

Tables 4, 5, 6, and 7 show the initial values of c(n, k ), p(n, k ), q (n, k ), and p (n, k ), respectively. There are far fewer non-robust sequences than robust, and their numbers are shown in Table 8. n\k 1 2 3 4 5 6 7 8 1 2 2 2 2 3 4 2 2 4 6 6 2 2 5 12 12 4 2 2 6 20 26 10 4 2 2 7 40 52 20 8 4 2 2 8 74 110 38 18 8 4 2 2 9 148 214 82 36 16 8 4 2 10 286 438 164 70 34 16 8 4 11 572 876 328 140 68 32 16 8 12 1124 1762 660 286 134 66 32 16 9 10 11 12

2 2 4 8

2 2 4

2 2

Table 4: Table of c(n, k ), the number of binary sequences of length n and curling number k , for 1 k n and n 12 (for an extended table see A216955). n\k 1 2 3 4 5 6 7 8 1 2 2 2 0 3 4 2 0 4 6 4 2 0 5 12 12 4 2 0 6 20 20 8 4 2 0 7 40 52 20 8 4 2 0 8 74 100 36 16 8 4 2 0 9 148 214 76 36 16 8 4 2 10 286 414 160 68 32 16 8 4 11 572 876 328 140 68 32 16 8 12 1124 1722 640 276 132 64 32 16 9 10 11 12

0 2 4 8

0 2 4

0 2

Table 5: Table of p(n, k ), the number of primitive binary sequences of length n and curling number k , for 1 k n and n 12 (for an extended table see A218869).

3.2

Three preliminary theorems

The classical Fine-Wilf theorem ([4]; [1, p. 13], [6], [7, p. 10]) turns out to be very useful for studying curling numbers. Theorem 5. (Fine and Wilf) If sequences S = X i and T = Y j have a common sux U of length |U | |X | + |Y | gcd(|X |, |Y |) , then, for some sequence Z and integers g , h, we have X = Z g , Y = Z h , |Z | = gcd(|X |, |Y |). 9 (5)

n\k 1 2 3 4 5 6 7 8 9 10 11 12 1 2 2 2 2 3 4 6 6 4 6 10 12 12 5 12 24 28 30 30 6 20 40 48 52 54 54 7 40 92 112 120 124 126 126 8 74 174 210 226 234 238 240 240 9 148 362 438 474 490 498 502 504 504 1 286 700 860 928 960 976 984 988 990 990 11 572 1448 1776 1916 1984 2016 2032 2040 2044 2046 2046 12 1124 2846 3486 3762 3894 3958 3990 4006 4014 4018 4020 4020 Table 6: Table of q (n, k ), the number of primitive binary sequences of length n and curling number at most k , for 1 k n and n 12 (for an extended table see A218870).

n\k 1 2 3 4 5 6 7 8 1 2 2 2 0 3 4 2 0 4 6 4 2 0 5 10 12 4 2 0 6 20 20 8 4 2 0 7 36 52 20 8 4 2 0 8 72 98 36 16 8 4 2 0 9 142 214 76 36 16 8 4 2 10 280 414 160 68 32 16 8 4 11 560 870 326 140 68 32 16 8 12 1114 1720 640 276 132 64 32 16

9 10 11 12

0 2 4 8

0 2 4

0 2

Table 7: Table of p (n, k ), the number of robust primitive binary sequences of length n and curling number k , for 1 k n and n 12 (for an extended table see A218875).

10

n\k 1 2 1 0 2 0 0 3 0 0 4 0 0 5 2 0 6 0 0 7 4 0 8 2 2 9 6 0 10 6 0 11 12 6 12 10 2

3 4 5 6 7 8 9 10 11 12

0 0 0 0 0 0 0 0 2 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0

0 0 0 0

0 0 0

0 0

Table 8: The numbers p(n, k ) p (n, k ) of non-robust primitive binary sequences of length n and curling number k , for 1 k n and n 12 (for an extended table see A218876). In most applications all we will need is |U | |X | + |Y | 1, rather than (5) itself. There is an equivalent denition of robustness that is easier to check. Theorem 6. If S P (n, k ) is not robust, implying that S k+1 has a proper sux T k+1 for some T , then T k+1 is in fact a proper sux of S 2 . Proof. The assertion is trivially true if k = 1, so we assume k 2. The hypotheses imply t := |T | < n. Now S k+1 and T k+1 have a common sux of length (k + 1)t. If it were the case that (k + 1)t n + t 1, by Theorem 5 we would have S = Z g , T = Z h , for some Z, g, h with g > h, implying g 2 and so S would be imprimitive, a contradiction. So (k + 1)t < n + t 1 < 2n, as required. It follows that S P (n, k ) is robust if and only if no proper sux of S 2 has curling number k + 1. This greatly simplies the computation of the numbers p(n, k ). A trivial but useful observation is that prexing a sequence with a single number cannot increase the curling number by more than 1: Theorem 7. If S C (n, k ) then 2S (and equally 3S ) is in either C (n + 1, k ) or C (n + 1, k + 1). Proof. If, for example, 2S C (n + 1, l) with l k + 2, then 2S = U V l for some U, V, l, and V l1 (at least) is a sux of S , contradicting the fact that S has curling number k .

3.3

A recurrence for c(n, k )

The rst main theorem of this section expresses the n-th row of the c(n, k ) table in terms of the (n 1)st row and much earlier rows of the p(n, k ) and p (n, k ) tables. Theorem 8. The numbers c(n, k ) have the following properties: c(n, k ) = 0 for n k 1,

11

c(n, k ) = 2 for n = k and k + 1, and, for n k + 2, c(n, k ) = 2 c(n 1, k ) ( (n ) (n )) + [k | n ] p ,k 1 + q ,k 2 k ( ( ) k ( )) n n [k + 1 | n] p ,k + q ,k 1 , k+1 k+1 (6) where the Iverson bracket [R] is 1 if the relation R is true, 0 otherwise. Proof. We assume k 1 and n k + 2. Suppose S C (n, k ) and let T denote S with its left-most term deleted. We consider the cases cn(T ) = k and cn(T ) < k separately. In the rst case, if T is any sequence in C (n 1, k ), and S is 2T or 3T , then, by Theorem 7, S is in either C (n, k ) or C (n, k + 1). So we will obtain 2c(n 1, k ) sequences in C (n, k ), except that we must exclude from the count those T C (n 1, k ) with the property that 2T or 3T = V k+1 for some primitive V of length n/(k + 1). This can only happen when n is a multiple of k + 1. These V s are primitive sequences of length n/(k + 1), with curling number l k , and are such that no proper sux of V k+1 has curling number greater than k . If l = k , the number of such V s is (by denition) p (n/(k + 1), k ). On the other hand, if 1 l k 1, any V P (n/(k + 1), l) has the property that no proper sux of V k+1 has curling number greater than k (and the number of these is p(n/(k + 1), l)). This follows from the Fine-Wilf theorem (Theorem 5). For if V k+1 has a proper sux of the form U k+1 , then these two sequences overlap in the last (k + 1)u terms, where u = |U |, and also u < v , where v = |V | = n/(k + 1). Since V has curling number l < k , the right-most k copies of U are not a sux of V , and so ku > v . This implies (k + 1)u v + u 1 , (7)

and so by Theorem 5, V = Z g , U = Z h , h < g , g 2. But V k = Z 2g is a sux of T , so cn(T ) 2k > k , a contradiction. (Further applications of the Fine-Wilf theorem will follow this same pattern, and we will not give as much detail.) In the second case we must consider sequences S = V k where cn(T ) < k . Now n must be a multiple of k , and V P (n/k, l) for 1 l k 1 is such that no proper sux of V k has curling number k . If l = k 1, the number of such V s is (by denition) p (n/k, k 1). On the other hand, if 1 l k 2, the condition that no proper sux of V k has curling number k follows from the Fine-Wilf theorem by an argument similar to that given above (except that k + 1 is replaced by k ), and the number is p(n/k, l). This completes the proof of the theorem.

3.4

Sequences with curling number 1

For the purpose of investigating the curling number conjecture, we are particularly interested in the rst three columns of the c(n, k ) table, since they determine the probabilities that a random sequence of 2s and 3s has curling number 1, 2, 3, or 4 (see 4.2). The values of c(n, 1) are especially intriguing, as this is a combinatorial problem of independent interest. The rst 30 terms of c(n, 1) were contributed to [9] by G. P. Srinivasan in 2006, who described it as the number of binary sequences of length n with no initial repeats, which is equivalent to our denition (see A122536). However, we have been unable to nd a formula for c(n, 1)4 , or even a recurrence that
4

Apart from the conjectured asymptotic estimate (27).

12

expresses c(n, 1) in terms of the values of c(m, 1) for m < n. Theorem 8 says only that c(n, 1) = 2c(n 1, 1) [2 | n] p (n/2, 1), (8)

p (n/2, 1) being the number of robust primitive binary sequences of length n/2 and curling number 1. Use of (8) enables n terms of the c(, 1) sequence to be obtained from n/2 terms of the p (, 1) sequence. In practice, this limits us to about 100 terms of the former sequence. In order to obtain more terms, we introduce some further terminology (which will be used only in this section). If S has length n, let S [i] denote its length-i sux, for 1 i < n. Then we dene A(n, i) := {S C (n, 1) | cn(S [i] S ) = 1}, B (n, i) := {S C (n, 1) | cn(S S [i] S ) = 1}, E (n, i, j ) := {S C (n, 1) | S S B (n + i, j )},
[i]

1 i < n, 1 i < n, 1 i < n, 1 j < n + i ,

and let a(n, i) = #A(n, i), b(n, i) = #B (n, i), e(n, i, j ) = #E (n, i, j ). S T will mean that T is a sux of S , and S T that T is a proper sux of S . The following two theorems give a canonical form (see (9)) for non-robust sequences with curling number 1. Theorem 9. If cn(S ) = 1 but cn(T S ) > 1 for some T with S T , then there exist X = , Y = with S = XY X, where cn(X ) = 1, T Y, and X Y . (9) Proof. Since cn(T S ) > 1, T S ZZ for some Z with |Z | < |S |, and therefore S Z . We write S = XZ and observe that T XZ ZZ , so T X Z . Therefore either X Z or Z X . The former implies cn(S ) > 1, a contradiction. So Z X , say Z = Y X , and S = XY X . Since S X , cn(X ) = 1. Also T X Z = Y X , so T Y . It remains to show that X Y . Now S T Y and S X , so either Y X or X Y . The former implies Y = W X for some W , and then S = XY X = XW XX , contradicting cn(S ) = 1. So X Y . For example, S = 33223 22333223 has curling number 1 (the conspicuous substring 333 makes it easy to check this). If T = 2333 223, then T S = 2333 Z 2 , where Z = 223 33223 (the spaces in these strings are for legibility). Then, following the steps of the proof, we write S = XZ , which denes X = 33223, and then write Z = Y X , which denes Y = 223, and so nally we have S = XY X = 33223 223 33223 , as claimed. Theorem 10. If S = XY X = U V U , with X Y = , U V = , X = U , then cn(S ) > 1. Proof. Without loss of generality, U X . Since both X and U are prexes of S , we have U = XZ for some Z = , and S XZ . Now 2|Z | = |S | 2|X | |V | < |S | 2|X | = |Y | < |X |, so |X | > |Z |. This implies X Z (they are both suxes of S ), say X = AZ , so S = U V U = U V XZ = U V AZZ , contradicting cn(S ) = 1. Theorems 9 and 10 say that a non-robust sequence S with curling number 1 can be written in a unique way as S = XY X , where Y is a sux of X .

13

Corollary 11. (i) For 1 i < n/3, there is a bijection between the sets C (n, 1) \ A(n, i) and
(n1)/2

B(m, n 2m) .

m=(ni)/2

(ii) For n/3 i < n, there is a bijection between the sets C (n, 1) \ A(n, i) and
(n1)/2

B (m, n 2m) .

m=1+n/3

Proof. Fix i, where 1 i < n. First, suppose that S is in C (n, 1) \ A(n, i). Taking T = S [i] in Theorem 9 we may write S = XY X where m := |X | 1, X C (m, 1), n 2m = |Y | |S [i] | = i and m = |X | > |Y | = n 2m 1. Hence X B(m, n 2m) for some m satisfying the three conditions: m (n i)/2, m > n/3 and m (n 1)/2. By Theorem 10, X belongs to only one such B(m, n 2m). Conversely, if m satises these three conditions and X B (m, n 2m) then let S = XX [n2m] X . By the denition of B (m, n 2m), S must be in C (n, 1) and since m (n i)/2, we have S [i] S S [n2m] S = (Y X )2 , so that S is not in A(n, i). This establishes a bijection between C (n, 1) \ A(n, i) and the union of B (m, n 2m) for m satisfying the three earlier conditions. The proof is completed by observing that (n i)/2 > n/3 if and only if n > 3i, which is the condition that separates cases (i) and (ii) of the Corollary. Since the unions in Corollary 11 are clearly disjoint, we immediately obtain the following formulas for a(n, i). Corollary 12. (i) For 1 i < n/3,
(n1)/2

a(n, i) = c(n, 1) (ii) For n/3 i < n, a(n, i) = c(n, 1)

b(m, n 2m) .

(10)

m=(ni)/2

(n1)/2

b(m, n 2m) .

(11)

m=1+n/3

The next three theorems give a further renement of non-robust sequences, and lead to the set bijections and formulas in Corollaries 16 and 17. We postpone their proofs to the Appendix. The proof that Corollary 16 follows from Theorems 13 through 15 is similar to the proof of Corollary 11 and is omitted. Theorem 13. If X Y , cn(Y X ) = 1, and cn(XY X ) > 1, then there exist S and T such that Y X = ST S with X T , S T , cn(S ) = 1. Furthermore, either |S | = |Y | or |S | > 2|Y |. Theorem 14. If n/2 < i < n then there is a bijection between A(n, i) \ B (n, i) and B(i, n i). Theorem 15. If 1 i < n/3 then A(n, i) \ B (n, i) is a disjoint union of E (m i, i, n + i 2m), where max(2i, 1 + (n + i)/3) < m (n + i 1)/2.

14

Corollary 16. (i) For 1 i < n/5, there is a bijection between A(n, i) \ B (n, i) and the disjoint union of E (m i, i, n + i 2m), where 2i < m (n + i 1)/2. (ii) For n/5 i < n/3, there is a bijection between A(n, i) \ B (n, i) and the disjoint union of E (m i, i, n + i 2m), where (n + i)/3 < m (n + i 1)/2. (iii) For n/3 i n/2, B (n, i) is empty. (iv) For n/2 < i < n, there is a bijection between A(n, i) \ B (n, i) and B(i, n i). Corollary 17. (i) For 1 i < n/3,
(n+i1)/2

b(n, i) = a(n, i) (ii) b(n, i) = 0 (iii)

e(m i, i, n + i 2m) .

(12)

m=max(2i,1+(n+i)/3)

for n/3 i n/2 . for n/2 < i < n .

(13) (14)

b(n, i) = a(n, i) b(i, n i)

Observing that p (n/2, 1) = a(n/2, n/2 1), equations (8) and (10) through (14) can be used recursively to compute values of c(n, 1), using brute force to determine e(m, i, j ) only for relatively small values of m (see 3.7). We have briey investigated the possibility of generalizing the approach in this section to deal with curling numbers k greater than one. The following theorems replace Theorems 9 and 10: Theorem 18. Suppose S P (n, k ) \ P (n, k ), where k > 1. Then there exist X and T with S = X (T X )k and S T . Proof. By Theorem 6, S 2 = P Qk+1 with P = . If (k + 1)|Q| n + |Q| 1, then Theorem 5 would imply that S is periodic. So k |Q| < n 1, and k copies of Q lie properly inside S , say S = XQk with |X | < |Q|, X = . Dene T by Q = T X and we have S = X (T X )k . Also P Qk+1 = SXQk , so P Q = P T X = SX and S T . Theorem 19. The representation S = X (T X )k obtained in Theorem 18 is unique. Since we will not make any use of Theorem 19, we omit the somewhat tedious proof. Because S P (n, k ), we know that S can be written as XY k , where Y is primitive, possibly in several ways. Theorems 18 and 19 say that if S is not robust, then exactly one of these Y s has the corresponding X as a sux. We have not pursued the generalizations of Theorems 1315 and Corollaries 1617 to this case.

3.5

The second main theorem of this section gives an expression for c(n, k ) in the range k n that involves the partial sum function q (m, k ). Theorem 20. We have c(n, n) = 2 for all n, c(n, n 1) = 2 for n 2, and, for n 4 and k n, { n 2n(k+1) (2 1) q (, k 1), if 1 k+1 , c(n, k, ) = (15) n+1 n k 2 q (, k 1), if k+1 n k, n/k and c(n, k ) = =1 c(n, k, ). 15

The values of c(n, k ) for k n

 Proof. We assume n 4 and k n 2. Note that k n is equivalent to k + 1 > n. We consider the cases n (k + 1) 1 and n (k + 1) separately. First, if n (k + 1) 1 , we have n n+1 . k+1 k Let us write S = X Y k , where Y is minimal and has length . Then n (k + 1) 1 implies |X | < . By Lemma 4, Y Q(, k 1). There are 2nk choices for X , and q (, k 1) choices for Y , and we claim that the resulting sequence X Y k always has curling number k . For suppose it has curling number > k , so that we have X Y k = U V k+1 , with u = |U |, v = |V |. There are two sub-cases. If (k + 1)v k , then we have (k + 1) > |S | (k + 1)v , implying > v . The two dierent representations of S have a common sux Y k of length k , which, since k 2, satises k v + 1 . (16)

By Theorem 5, Y = Z g , V = Z h , with g > h, so g 2, and Y is imprimitive, a contradiction. On the other hand, suppose (k + 1)v < k . Again > v . Since cn(Y ) < k , kv > . Now the common sux has length (k + 1)v , our inequalities imply (k + 1)v v + 1 , (17)

and, again by Theorem 5, Y is imprimitive, a contradiction. So the number of sequences S of this type is 2nk q (, k 1), as claimed. Second, if n (k + 1) , we have n . 1 k+1 Let us write S = XBY k , (18) where X has length n (k + 1) , B has length , and Y Q(, k 1). Certainly B = Y (B stands for blocker, the purpose of which is to ensure that Y is repeated only k times). There are potentially 2n(k+1) choices for X , 2 1 choices for B , and q (, k 1) choices for Y . We claim that the assumption k n guarantees that all choices result in a sequence with curling number k . For suppose on the contrary that S (in (18)) is also equal to U V k+1 , with u = |U |, v = |V |. Again there are two sub-cases. If (k + 1)v k , then we have (k + 1)2 > n (k + 1)v k , so k + 1 > v , k v . The two dierent representations of S have a common sux of length k , and our inequalities imply (16). On the other hand, suppose (k + 1)v < k . Again we have kv > , and the common sux satises (17). In both cases Theorem 5 now leads to a contradiction. This complete the proof of the theorem. The formulas in Theorem 20 cover a large portion of the c(n, k ) table. However, although with more work they could be extended so as to apply to slightly smaller values of k , it seems unlikely that this approach will lead to a formula for c(n, k, ) for small values of k .

16

n\k 1 2 2 2 2 3 0 2 4 2 2 5 0 0 6 4 2 7 0 0 8 6 6 9 0 6 10 10 10 11 0 0 12 20 10

10

11

12

2 2 2 0 2 2 2 0 2 2 0 0 0 2 2 2 2 0 0 2 2 6 0 0 0 0 2 2 0 2 2 0 0 0 2 2 0 0 0 0 0 0 0 2 2 4 6 2 2 0 0 0 0 2 2

Table 9: The dierence table d(n, k ) dened by (19) (for an extended table see A217943).

3.6

The dierence table d(n, k )

In the c(n, k ) table (Table 4), if we look at the dierence between each row and twice the previous row, we obtain a much simpler table.5 We dene d(n, k ) := 2 c(n 1, k ) c(n, k ) , (19)

for n 2, 1 k n 1, with d(n, n) = 2. The initial values are shown in Table 9. We see that if one ignores the initial entries in each row, most of the remaining entries are zero, except for diagonal lines of pairs of nonzero entries. More precisely, it appears that d(2k, k 1) = d(2k, k ) = 2, d(3k, k 1) = d(3k, k ) = 6, d(4k, k 1) = d(4k, k ) = 12, d(5k, k 1) = d(5k, k ) = 30, k 4, k 5, k 6, k 7, (20) and so on. Only the rst of these diagonal lines can be seen in Table 9, but they are all visible in the extended table that is given in entry A217943 in [9]. These expressions all follow from Theorem 20: Theorem 21. In the range k n, the only nonzero entries in the d(n, k ) table are d(mk, k 1) = d(mk, k ) = q (m, m), for m 1, k m + 2 . (21)

Proof. This follows easily from Theorem 20. We prove the second assertion in (21) as an illustration. We have d(mk, k ) = 2c(mk 1, k ) c(mk, k ) . (22) From (15), c(mk, k ) =
5

m 1 =1

c(mk, k, ) + c(mk, k, m) ,

(23)

It was by studying the d(n, k ) table that we were led to Theorems 8 and 20.

17

c(mk 1, k ) =

m 1 =1

c(mk 1, k, ) .

(24)

Each summand in (23) (see (15)) is exactly twice the corresponding term in (24), and c(mk, k, m) = q (m, k ) = q (m, m), so d(mk, k ) = q (m, m). Note that whereas the expression for c(n, k ) in Theorem 20 involves the general function q (, k ), the expression for d(n, k ) in the range k n is fully explicit, since q (m, m) is given by (4). Theorem 8 gives another formula for d(n, k ): ( ( ) ( )) ( (n ) (n )) n n d(n, k ) = [k +1 | n] p ,k + q ,k 1 [k | n] p ,k 1 + q ,k 2 , k+1 k+1 k k (25) and in particular, d(n, 1) = [2 | n] p (n/2, 1) , d(n, 2) = [3 | n] (p (n/3, 2) + p(n/3, 1)) [2 | n] p (n/2, 1) . (26)

The rst of these is nicely checked by noticing that the nonzero entries in the rst column of the d(n, k ) table, namely 2, 2, 4, 6, 10, 20, are also the entries in the rst column of the p (n, k ) table (Table 7). It is also worth mentioning that if p is prime then c(p, k ) = 2c(p 1, k ) for all k (see (8)) and so d(p, k ) = 0.

3.7

Computation of c(n, k )

We constructed an extensive table of values of c(n, k ), hoping that it would lead to additional insight into these numbers. First, by direct enumeration, using a number of dierent programs and dierent computers (including a four-day computation on a cluster of 64 SPARC processors), we calculated c(n, k ) for n 51. Second, we tabulated e(n, i, j ) for n 23. This was sucient for the recurrences (8) and (10)(14) to give c(n, 1) for n 200. These values suggest the conjecture that
n

lim

c(n, 1) = 0.27004339525895354325 . 2n

(27)

From Equation (8) we have c(n, 1) 2c(n 1, 1) [2 | n] c(n/2, 1) , which implies, using the known values of c(n, 1), that c(n, 1) > 0.27 2n for n 200 . (28)

We omit the proof. But we have no comparable upper bound for c(n, 1) (other than 2n ), nor a proof that the limit (27) exists. Third, we used a dierent approach, which enabled us to take a table of the curling numbers of all sequences of length n n0 , and from this produce a table of c(n, k ) for all n 2n0 , without having to compute the curling numbers of all 22n0 sequences of length 2n0 . The idea underlying this approach is the following. Consider a sequence S of length n with n0 n 2n0 , and let M be its length-n0 sux. As a rst approximation, we set cn(S ) = cn(M ) = l (say). This approximation 18

will be wrong if for some sux T of M it should happen that T l+1 is a sux of S . If so, we must increase cn(S ) by 1 for all S having sux T l+1 . There are complications if there is more than one such T to be considered, but the Fine-Wilf theorem (Theorem 5) shows that this can only happen when l = 1. We omit discussion of the details. Using this approach (with n0 = 32) we were able to extend the table of values of c(n, k ) and p(n, k ) to n = 64. Finally, we tabulated p (n, k ) for n 36. This, together with the 200 terms of c(n, 1), was sucient for the recurrence in Theorem 8 to give the rst 104 rows of the c(n, k ) table. These results can be seen in A216955 and A122536.

4
4.1

Tail lengths of {2,3}-sequences

Distribution of tail lengths

Let t(n, i) denote the number of starting sequences S0 of n 2s and 3s which have tail length i, where i ranges from 0 to (n). The initial values are shown in Table 10. Since the rows rapidly increase in length (cf. Table 1), we end this table at n = 9. Note that the entries for i = 9 through 55 (which are all zero) have been compressed into a single column. Rows n = 22 and 32 are shown in Tables 11 and 12. Entry A217209 in [9] gives the rst 48 rows in full. The rst column is the same as the rst column of the c(n, k ) table, and contains the numbers c(n, 1) that are the subject of 3.4. n\i 0 1 1 2 2 2 1 3 4 2 4 6 5 5 12 9 6 20 18 7 40 34 8 74 71 9 148 139 2 3 4 5 6 7 8 9-55 56 57 58 59

1 2 3 1 1 6 2 3 12 6 7 0 25 11 14 1 47 24 28 1 95 48 56 6

0 0 3 4

0 1 2 3

1 2 3 6

0 0

0 2

2 3

1 1

Table 10: Table of t(n, i), the number of sequences of n 2s and 3s with tail length i, for 0 i (n) (A217209). As can be seen from Tables 1012, the values in each row are distributed into clumps, with each clump gradually thickening as n increases. Table 11 shows the distribution of tail lengths at length 22, the rst time that a tail of length 120 is reached (note the nal 1, indicating that the starting sequence was unique). By length 32 (Table 12), the clumps have thickened but still end at 120. A tail of length greater than 120 does not appear until length 48, when the greatest tail length jumps to 131. The powers of 2 in Tables 11 and 12 suggest that the clumps tend to grow by prexing good starting sequences of shorter length by random strings of 2s and 3s. However, we do not have a satisfactory model which explains this distribution. The mean value of the nth row, (n) 1 i t(n, i) , 2n
i=0

19

0-8 9-17 18-26 27-35 36-44 45-53 54-62 63-71 72-80 81-89 90-98 99-107 108-116 117-120

1133200 6388 1 0 0 24 5891 463 1 0 0 0 64 139

1140102 6096 1 0 0 50 7687 299 0 0 0 0 128 282

768386 1031 3 0 0 98 9230 32 0 0 0 1 256 8

417081 2074 6 0 0 198 14622 0 0 0 0 1 512 1

479224 516 12 0 0 394 12983 0 0 0 0 2 1024

47190 807 7 0 0 786 6486 0 0 0 0 4 17

33440 67 0 0 1 1316 2659 0 0 0 0 8 17

32283 0 0 0 7 2633 642 0 0 0 0 16 34

51035 0 0 0 16 5121 1099 0 0 0 0 32 70

Table 11: Distribution of tail lengths t(22, i), 0 i 120, for all starting sequences of length 22 (22 is the rst time a tail of length 120 is reached). Note the three clumps.
0-8 9-17 18-26 27-35 36-44 45-53 54-62 63-71 72-80 81-89 90-98 99-107 108-116 117-120 1159845258 6585936 836 99 72 25219 6034490 487704 770 0 0 128 65536 146237 1167273283 6286710 1547 194 130 50438 7874728 309650 0 0 1 256 131072 292601 786757853 1088875 3092 0 198 100876 9455010 32814 0 0 1 512 262144 8798 427198253 2157877 6184 0 394 201752 14977616 28 0 0 2 1024 524288 1144 490970976 553922 11843 0 788 403504 13308516 24 0 1 4 2048 1048544 48399112 848516 7303 2 1576 804960 6658834 48 0 2 8 4096 18331 34266983 69469 206 9 3153 1347868 2742615 96 0 5 16 8192 18265 33065461 519 28 21 6305 2695736 676305 193 0 10 32 16384 36530 52260747 1038 57 34 12610 5244019 1153446 385 0 20 64 32768 73119

Table 12: Distribution of tail lengths t(32, i), 0 i 120, for all starting sequences of length 32. The clumps have thickened. at least for n 48, is converging to a value around 2.741 (see A216813). That is, if a starting sequence consisting of n 2s and 3s is chosen at random, it will reach a 1 on average after only 2.741 steps. This is in sharp contrast to the behavior of the best starting sequences, as we see from Table 1. Of course if the curling number conjecture is false for sequences of 2s and 3s, the mean will be innite beyond some point.

4.2

A probabilistic model
(n)

Let k := c(n, k )/2n denote the probability that a randomly chosen sequence consisting of n 2s and 3s has curling number k . The available data (n 200 for k = 1, n 104 for k > 1) suggests that as n increases these probabilities are converging to the values 1 .270, 2 .434, 3 .162, k .134 .
k4

When we extend a sequence S by appending the curling number k = cn(S ), if it were the case that the concatenation Sk were independent of S , we could model this process as a two-state Markov chain with states curling number is 2 or 3 and curling number is 1 or 4. The probability of 20

staying in the 2 or 3 state would be 2 + 3 .596 and the probability of leaving that state would be .404 . If the starting sequence is randomly chosen from all 2n possibilities, this model would imply that the maximal number of steps before reaching the 1 or 4 state for the rst time would be about log 2 t n 1.34 n . log(1/.596) This Markov model certainly does not apply at the beginning of the appending process, but it could conceivably be valid once the sequence has been extended for a while, so we think it is worth mentioning.

4.3

Rotten sequences: prex decreases tail

Let S0 be an arbitrary sequence of 2s and 3s of length n, with tail length (S0 ) = i, say. It seems plausible that if n is large, then prexing S0 by a single 2 or 3 will not change (S0 ), i.e., that (2 S0 ) = (3 S0 ) = (S0 ). But could doing this actually decrease the tail length? Choosing an adjective not normally used in mathematics, we will call S0 rotten if either (2 S0 ) < (S0 ) or (3 S0 ) < (S0 ), and doubly rotten if both (2 S0 ) < (S0 ) and (3 S0 ) < (S0 ) hold. There are surprisingly few rotten sequences of length up through 34. The rst few examples are shown in Table 13, and the numbers of rotten sequences of lengths 1 through 34 are given in Table 14. If (e) S0 = 3 2 3 2 3, for example, then S0 = 3 2 3 2 3 2 3 3 2, and (S0 ) = 4. But if we prex S0 with a 2, so the starting sequence is 2 S0 = 2 3 2 3 2 3, the extension is 2 3 2 3 2 3 3 2, so (2 S0 ) = 2, and S0 is rotten.
22 23222322 2232223222 3323323323 333 23223223 2232223223 22322232223 32323 33233233 2232223232 22322232232 323232 223222322 2322232223 22322232322 2323232 223222323 2322322322 22322322232 3232323 232223222 2332332332 22322322322 22322232 332332332 3322332233 22323222322

Table 13: The rst 28 rotten sequences (A216730). 0 1 1 0 1 1 2 4 4 8 14 11 18 30 26 24 40 35 58 69 48 84 158 67 139 287 215 242 490 323 624 919 516 1072 Table 14: Number of rotten sequences of lengths 1 through 34 (A216950). However, up to length 34 there are no doubly rotten sequences. Conjecture 22. Doubly rotten sequences do not exist. If this conjecture were true, it would imply that one can always prex a starting sequence S0 by one of {2, 3} without decreasing the tail length. This would explain the observation made in 2.2 about the behavior of (n) between jump points. It would also imply that (n + 1) (n) for all n, something that we do not know at present.

4.4

Sequences in which rst term is essential

A statistic that is relevant to the study of rotten sequences is the following. If a starting sequence S0 of length n is chosen at random, and has curling number k , this means we can write S0 = XY k 21

for suitable sequences X, Y . What is the probability that we must necessarily take X to be the empty sequence, i.e., that the only such representation goes all the way back to the beginning of S0 (and so the rst term is essential for the computation of the curling number)? The sequence 2 2 3 2 2 3 is an example, since here k = 2, and X = , Y = 2 2 3 is the only representation. But 2 3 3 2 3 3 is not, since k = 2 and we can either take X = , Y = 2 3 3 or X = 2 3 3 2, Y = 3, and the latter representation avoids using X = . The number of such sequences of length n for 1 n 35 is given in Table 15. If n is prime, the number is 2, but the limit supremum of these numbers appears to grow exponentially. 2 2 2 4 2 8 2 10 8 14 2 40 2 40 32 88 2 192 2 324 100 564 2 1356 32 2226 370 4564 2 9656 2 17944 1450 35424 152 Table 15: Number of sequences of lengths 1 through 35 whose curling number representation X Y k requires X = (A216951).

4.5

Sequences where prex increases tail

In contrast to rotten sequences, we also investigated starting sequences S0 for which either (2 S0 ) > (S0 ) or (3 S0 ) > (S0 ). The sequence S0 = 2 2 3 2 2 is an example, since (S0 ) = 2, (2 S0 ) = 8, (3 S0 ) = 2. The numbers of such sequences of lengths 1 through 30 are shown in Table 16. There are rather more of these than there are rotten sequences, although we found no example where both (2 S0 ) > (S0 ) and (3 S0 ) > (S0 ) hold. 2 1 2 1 5 3 12 9 19 16 38 20 59 42 104 65 213 111 400 245 765 439 1563 820 3046 1731 5955 3292 12078 6343 Table 16: Number of sequences S0 of lengths 1 through 30 such that (2 S0 ) > (S0 ) or (3 S0 ) > (S0 ) (A217437).

Gijswijts sequence

If we simply start with S0 = 1, and generate an innite sequence by continually appending the curling number of the current sequence, as in (1), we obtain G := 1 1 2 1 1 2 2 2 3 1 1 2 1 1 2 2 2 3 2 1 1 2 1 1 2 2 2 3 1 1 2 1 1 . This is Gijswijts sequence, A090822, invented by D. Gijswijt in 2004, and analyzed by van de Bult et al. [2]. The rst time a 4 appears in G is at term 220. One can calculate quite a few million terms without nding a 5 (as the authors of [2] discovered), but in [2] it was shown that a 5 eventually appears for the rst time at about term 23 1010 .

22

Van de Bult et al. [2] also show that G is in fact unbounded, and conjecture that the rst time that a number m 6 appears is at about term number 2
4 23
m1

a tower of height m 1. The fairly complicated arguments used in [2] could be considerably simplied and extended if the curling number conjecture were known to be true. Our nal theorem shows that if the curling number conjecture is true, any starting sequence S that does not contain a 1 must eventually merge with G. Theorem 23. Assume the curling number conjecture is true. Let S be an initial sequence not containing a 1, let S (e) be its extension (dened in 1), and let S () be its innite continuation. Then S () = S (e) G. Proof. By denition, S (e) does not contain a 1 but is immediately followed by a 1. Suppose S () = S (e) G, and suppose they rst dier at a position where S () is n, say, whereas S (e) G is m < n. This n must be the curling number of some portion of S () that begins with a sux X , say, of S (e) . Let S (e) = W X . Then S () = W (XT )n n for some prex T of G, whereas G = T (XT )n1 m . If n = 2, m = 1, we have G = T XT 1 . The curling number of the rst copy of T is the rst term of X , which is not 1, but the curling number of the second T is 1, a contradiction. On the other hand, if n 3, G = T XT XT XT m , and the initial T XT X has curling number at least 2 and cannot be followed by T (which begins with 1), again a contradiction. We do not know if the theorem is still true if S is allowed to contain a 1 but does not end with 1.

Open questions and topics for future research

1. Is the curling number conjecture (even just for the case of sequences of 2s and 3s) true? 2. It would be nice to have some further exact values of (n), beyond n = 48, even though they will require extensive computations. 3. What is the asymptotic behavior of (n)? 4. Can the especially good starting sequences shown in Tables 2 and 3 (in particular those of lengths 22, 48 and 77) be generalized? What makes them so special? 5. Can the properties of good starting sequences mentioned in Conjecture 2 be justied? 6. Can Shirshovs theorem (see 2.5) be modied so as to apply to our problem? 7. Are there analogs of Theorems 8 and 20 for p(n, k ) (the number of primitive sequences) or p (n, k ) (the number of primitive and robust sequences) ? 8. Are there formulas for c(n, k ) that are more explicit than those given in Theorems 8 and 20? Is there a formula that matches the 200 known terms of the c(n, 1) sequence? 9. Are there formulas or recurrences for the numbers t(n, i) of starting sequences with tail length i? 23

10. Is there a probabilistic model that better explains the distribution of values of t(n, i) visible in Tables 1012 and A217209? The model presented in 4.2 is certainly inadequate. 11. Do doubly rotten sequence exist? (See Conjecture 22.) 12. The question implicit in the last sentence of 5.

7
7.1

Appendix: Proofs of Theorems 13, 14, 15

Theorem 13

Proof. The rst statement follows immediately from Theorem 9, taking S and T in that theorem to be Y X and X respectively. To prove the second statement, let x := |X |, y := |Y |, s := |S |, t := |T |, and note that Y X = ST S implies x + y = 2s + t. Also X = BY (say), with B = . We are to show that s = y or s > 2y . First, suppose that y < s 2y . Since s > y , there exists a sequence U with |U | = s y such that S = Y U . Then we have the following chains of implications [the successive assertions are enclosed in square brackets]: [s > y ] [s > y t] [x = 2s + t y > s] [X S U ], and [s 2y ] [s y y ] [|Y | |U |] [Y U (since Y X = Y BY = ST Y U )] [Y = CU (say)] [X S = CU U ] [cn(X ) > 1], a contradiction. Second, suppose that s < y . Then there exists U = with |U | = y s such that Y = SU . But x > y > s and Y X = ST S imply X S , and since X Y then X U also. If S U then Y X = Y BSU X U U , which contradicts cn(Y X ) = 1. Hence [U S ] [s < y s] [2s < y ] [x + y = 2s + t < y + t y + x] , since X T . Since this is impossible, s < y is also impossible. Note that the condition |S | = |Y | is equivalent to 2|Y | > |X |: if s = y then x = y + t, which implies 2y = s + y > t + y (since t > s). Conversely, if s = y then s > 2y , which implies x + y = 2s + t > 4y + t, x > 3y + t, so x 2y . Similar reasoning shows that the condition |S | > 2|Y | is equivalent to 3|Y | < |X |.

7.2

Theorem 14

Proof. If X A(n, i) \ B (n, i) then we may apply Theorem 13 to X , taking Y = X [i] , with |X | = n, |Y | = i, where n/2 < i < n. So there exist S , T with Y X = ST S , Y T , S T , and either |S | = |Y | or |S | > 2|Y |. We cannot have |S | > 2|Y |, since that implies |S | > n, 2|S | > 2n > |Y X |, which contradicts Y X = ST S . So |S | = |Y |, Y = S , X = T Y , and |T | = n i. Also cn(Y X ) = 1 by denition of A(n, i), i.e., cn(Y T Y ) = 1, so Y B (i, n i). The map from X to Y is one-to-one, since X determines Y . To show it is onto, take Y B (i, n i), let Q = Y [ni] , and dene P by Y = P Q and set X := QY = QP Q. Then we have cn(Y QY ) = cn(Y X ) = 1, so X A(n, i). Also XY X = QP Q P Q QP Q has curling number at least 2, so X / B (n, i). Hence X A(n, i) \ B (n, i).

7.3

Theorem 15

Proof. Since the sets E in the sum are clearly disjoint, we just need to establish a bijection between the elements of A(n, i) \ B (n, i) and the disjoint union of the E sets dened by the range of m. As in the previous proof, if X A(n, i) \ B (n, i), then we may apply Theorem 13 to X , taking Y = X [i] , with |X | = n, |Y | = i, where now 1 i < n/3. There exist S , T with Y X = ST S , Y T , S T , and either |S | = |Y | or |S | > 2|Y |. Let |S | = m, |T | = n + i 2m. As before, S B (m, |T |). There are three conditions that m must satisfy: (i) |T | 1 implies m (n + i 1)/2; 24

(ii) |S | > |T | implies m > (n + i)/3; (iii) m = i < n/3 is incompatible with Y X = ST S , so m > 2i. Since m > i, we may write S = Y U , with |U | = m i. Since m > 2i, m i > i and |U | > |Y |. Now X S , so X U and therefore U Y . Since S = Y U B (m, |T |), U E (m i, i, |T |). The mapping X U is one-to-one since X determines Y = X [i] , S and T are unique by Theorem 10, m = |S |, and S = Y U determines U . To show the map is onto, suppose U E (m i, i, n + i 2m) for some m satisfying conditions (i)-(iii) above. Then set Y = U [i] , S = Y U , T = S [n+i2m] , and X = U T S . Then Y X = ST S so that U E (m i, i, n + i 2m) implies Y X A(n, i). But XY X = XST S T ST S , so cn(XY X ) > 1 and therefore XY X / B (n, i).

Acknowledgments

We thank the referees for several helpful comments.

References
[1] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge Univ. Press, 2003. [2] F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane, and A. R. Wilks, A slowgrowing sequence dened by an unusual recurrence, J. Integer Sequences, 10 (2007), #07.1.2. [3] B. Chan and N. J. A. Sloane, The Curling Number Conjecture, http://arxiv.org/abs/ 0912.2382. [4] N. J. Fine and H. S. Wilf, Uniqueness theorems for periodic sequences, Proc. Amer. Math. Soc., 16 (1965), 109114. [5] E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657665. [6] A. Lentin and M. P. Sch utzenberger, A combinatorial problem in the theory of free monoids, pp. 128144 of R. C. Bose and T. A. Dowling, eds., Combinatorial Mathematics and its Applications, Univ. North Carolina Press, Chapel Hill, 1969. [7] M. Lothaire, Combinatorics on Words, Addison-Wesley, 1983. [8] A. de Luca and S. Varricchio, Finiteness and Regularity in Semigroups and Formal Languages, Springer, 1998. [9] The OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, http://oeis. org.

2010 Mathematics Subject Classication: Primary 68R15; Secondary 11B37. Keywords: curling number, Gijswijt sequence, sequences, conjectures, Fine-Wilf theorem.

25

(Concerned with sequences A027375, A090822, A122536, A135491, A160766, A216730, A216813, A216950, A216951, A216955, A216955, A217208, A217209, A217437, A217943, A218869, A218870, A218875, and A218876.)

26