A160766 -id:A160766 - cp's OEIS frontend

A090822 Gijswijt's sequence: a(1) = 1; for n>1, a(n) = largest integer k such that the word a(1)a(2)...a(n-1) is of the form xy^k for words x and y (where y has positive length), i.e., the maximal number of repeating blocks at the end of the sequence so far.

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, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 3, 2, 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, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2, 2, 3, 2, 1

Offset: 1

Dion Gijswijt, Feb 27 2004

Here xy^k means the concatenation of the words x and k copies of y.
The name "Gijswijt's sequence" is due to N. J. A. Sloane, not the author!
Fix n and suppose a(n) = k. Let len_y(n) = length of shortest y for this k and let len_x = n-1 - k*len_y(n) = corresponding length of x. A091407 and A091408 give len_y and len_x. For the subsequence when len_x = 0 see A091410 and A091411.
The first 4 occurs at a(220) (see A091409).
The first 5 appears around term 10^(10^23).
We believe that for all N >= 6, the first time N appears is at about position 2^(2^(3^(4^(5^...^(N-1))))). - N. J. A. Sloane and Allan Wilks, Mar 14 2004
For a similar formula, see p. 6 of Levi van de Pol article. - Levi van de Pol, Feb 06 2023
In the first 100000 terms the fraction of [1's, 2's, 3's, 4's] seems to converge, to about [.287, .530, .179, .005] respectively. - Allan Wilks, Mar 04 2004
When k=12 is reached, say, it is treated as the number 12, not as 1,2. This is not a base-dependent sequence.
Does this sequence have a finite average? Does anyone know the exact value? - Franklin T. Adams-Watters, Jan 23 2008
Answer: Given that "...the fraction of [1's, 2's, 3's, 4's] seems to converge, to about [.287, .530, .179, .005]..." that average should be the dot product of these vectors, i.e., about 1.904. - M. F. Hasler, Jan 24 2008
Second answer: The asymptotic densities of the numbers exist, and the average is the dot product. See pp. 56-59 of Levi van de Pol article. - Levi van de Pol, Feb 06 2023
Which is the first step with two consecutive 4's? Or the shortest run found so far between two 4's? - Sergio Pimentel, Oct 10 2016
Answer: The first x such that the x-th and (x+1)-th element are 4, is 255895648634818208370064452304769558261700170817472823... ...398081655524438021806620809813295008281436789493636144. See p. 55 of Levi van de Pol article. - Levi van de Pol, Feb 06 2023

N. J. A. Sloane, Seven Staggering Sequences, in Homage to a Pied Puzzler, E. Pegg Jr., A. H. Schoen and T. Rodgers (editors), A. K. Peters, Wellesley, MA, 2009, pp. 93-110.

N. J. A. Sloane, Table of n, a(n) for n = 1..24000
Andreas Abel and Andres Loeh, Haskell program
Fokko J. van de Bult, Dion C. Gijswijt, John P. Linderman, N. J. A. Sloane and Allan R. Wilks, A Slow-Growing Sequence Defined by an Unusual Recurrence, J. Integer Sequences, Vol. 10 (2007), #07.1.2.
Benjamin Chaffin, John P. Linderman, N. J. A. Sloane, and Allan R. Wilks, On Curling Numbers of Integer Sequences, arXiv:1212.6102 [math.CO], Dec 25 2012.
Benjamin Chaffin, John P. Linderman, N. J. A. Sloane, and Allan R. Wilks, On Curling Numbers of Integer Sequences, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3.
Benjamin Chaffin and N. J. A. Sloane, The Curling Number Conjecture, preprint.
Dion C. Gijswijt, Krulgetallen, Pythagoras, 55ste Jaargang, Nummer 3, Jan 2016, (Article in Dutch about this sequence, see pages 10-13, cover and back cover).
Levi van de Pol, The first occurrence of a number in Gijswijt's sequence, arXiv:2209.04657 [math.CO], 2022.
Levi van de Pol, The Growth Rate of Gijswijt's Sequence, J. Int. Seq. (2025) Vol. 28, Art. No. 25.4.6. See p. 2.
N. J. A. Sloane, Seven Staggering Sequences.
N. J. A. Sloane, Confessions of a Sequence Addict (AofA2017), slides of invited talk given at AofA 2017, Jun 19 2017, Princeton. Mentions this sequence.
Index entries for sequences related to Gijswijt's sequence
Index entries for sequences related to curling numbers

Cf. A091407, A091408, A091409 (records), A091410, A091411, A091579, A091586, A091970, A093955-A093958.
A091412 gives lengths of runs. A091413 gives partial sums.
Cf. also A094004, A160766, A217206, A217207.
Generalizations: A094781, A091975, A091976, A092331-A092335.

Haskell
```
-- See link.
```

K:= proc(L)
local n,m,k,i,b;
m:= 0;
n:= nops(L);
for k from 1 do
  if k*(m+1) > n then return(m) fi;
  b:= L[-k..-1];
  for i from 1 while i*k <= n and L[-i*k .. -(i-1)*k-1] = b do od:
  m:= max(m, i-1);
od:
end proc:
A[1]:= 1:
for i from 2 to 220 do
  A[i]:= K([seq(A[j],j=1..i-1)])
od:
seq(A[i],i=1..220); # Robert Israel, Jul 02 2015

ClearAll[a]; reversed = {a[2]=1, a[1]=1}; blocs[len_] := Module[{bloc1, par, pos}, bloc1 = Take[reversed, len]; par = Partition[ reversed, len]; pos = Position[par, bloc_ /; bloc != bloc1, 1, 1]; If[pos == {}, Length[par], pos[[1, 1]] - 1]]; a[n_] := a[n] = Module[{an}, an = Table[{blocs[len], len}, {len, 1, Quotient[n-1, 2]}] // Sort // Last // First; PrependTo[ reversed, an]; an]; A090822 = Table[a[n], {n, 1, 99}] (* Jean-François Alcover, Aug 13 2012 *)

A090822(n,A=[])={while(#Ak||break; k=m);A=concat(A,k));A} \\ M. F. Hasler, Aug 08 2018

def k(s):
    maxk = 1
    for m in range(1, len(s)+1):
        i, y, kk = 1, s[-m:], len(s)//m
        if kk <= maxk: return maxk
        while s[-(i+1)*m:-i*m] == y: i += 1
        maxk = max(maxk, i)
def aupton(terms):
    alst = [1]
    for n in range(2, terms+1):
        alst.append(k(alst))
    return alst
print(aupton(99)) # Michael S. Branicky, Mar 28 2022

A216730 List of "rotten" strings in {2,3}* (in the curling number sense).

Original entry on oeis.org

22, 333, 32323, 323232, 2323232, 3232323, 22322232, 23222322, 23223223, 33233233, 223222322, 223222323, 232223222, 332332332, 2232223222, 2232223223, 2232223232, 2322232223, 2322322322, 2332332332, 3322332233, 3323323323, 22322232223, 22322232232, 22322232322, 22322322232, 22322322322, 22323222322, 23222322232, 23223223223

Offset: 1

Benjamin Chaffin and N. J. A. Sloane, Sep 16 2012

The "curling number" k = k(S) of a string of numbers S = s(1), ..., s(m) is defined as follows. Write S as XY^k for strings X and Y (where Y has positive length) and k is maximized, i.e., k = the maximal number of repeating blocks at the end of S.
The "tail length" t(S) of S is defined as follows: start with S and repeatedly append the curling number (recomputing it at each step) until a 1 is reached; t(S) is the number of terms that are appended to S before a 1 is reached.
If a 1 is never reached, set t(S)=oo (the Curling Number Conjecture says this will never happen).
A sequence S in {2,3}* is called "rotten" if either of t(2S) or t(3S) (or both) is strictly less than t(S).
Example: S = 32323 has curling number k=2, so we get 323232; now k=3, so we get 3232323; now k=3, so we get 32323233; now k=2, so we get 323232332; now k=1 so we stop. We added 4 terms before reaching 1, so t(S)=4.
On the other hand, 2S = 232323 only extends to 232323321..., so t(2S)=2 which means S is rotten.

Benjamin Chaffin, Table of n, a(n) for n = 1..2400
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, arXiv:1212.6102, Dec 25 2012.
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3.
Index entries for sequences related to curling numbers

Cf. A094004, A160766, A216950.

A094004 a(n) = (conjectured) length of longest string that can be generated by a starting string of 2's and 3's of length n, using the rule described in the Comments lines.

Original entry on oeis.org

1, 4, 5, 8, 9, 14, 15, 66, 68, 70, 123, 124, 125, 132, 133, 134, 135, 136, 138, 139, 140, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 200, 201, 202, 203, 204, 205, 206, 207, 209, 250, 251, 252, 253

Offset: 1

N. J. A. Sloane, May 31 2004. Revised by N. J. A. Sloane, Sep 17 2012

Start with an initial string of n numbers s(1), ..., s(n), all = 2 or 3. The rule for extending the string is this:
To get s(i+1), write the string s(1)s(2)...s(i) as xy^k for words x and y (where y has positive length) and k is maximized, i.e. k = the maximal number of repeating blocks at the end of the sequence so far (k is the "curling number" of the string). Then set s(i+1) = k if k >=2, but if k=1 you must stop (without writing down the 1).
The "Curling Number Conjecture" is that if one starts with any finite string and repeatedly extends it by appending the curling number k, then eventually one must reach a 1. This has not yet been proved.
The values shown for n >= 49 are only conjectures, because certain assumptions used to cut down the search have not yet been rigorously justified. However, we believe that ALL terms shown are correct. - N. J. A. Sloane, Sep 17 2012

			a(3) = 5, using the starting string 3,2,2, which extends to 3,2,2,2,3, of length 5.
a(4) = 8, using the starting string 2,3,2,3, which extends to 2,3,2,3,2,2,2,3 of length 8.
a(8) = 66: start = 23222323, end = 232223232223222322322232223232223222322322232223232223222322322332.
a(22) = 142: start = 2322322323222323223223: see A116909 for trajectory.

F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane and Allan Wilks, A Slow-Growing Sequence Defined by an Unusual Recurrence, J. Integer Sequences, Vol. 10 (2007), #07.1.2.
F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane and Allan Wilks, A Slow-Growing Sequence Defined by an Unusual Recurrence [pdf, ps].
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, arXiv:1212.6102 [math.CO], Dec 25 2012.
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3.
Benjamin Chaffin and N. J. A. Sloane, The Curling Number Conjecture, preprint.
Index entries for sequences related to curling numbers

Cf. A091787, A090822, A093369, A094005, A116909, A160766, A216730, A217208.

a(27)-a(30) from Allan Wilks, Jul 29 2004
a(31)-a(36) from Benjamin Chaffin, Apr 09 2008
a(37)-a(44) (computed in 2008) from Benjamin Chaffin, Dec 04 2009
a(45)-a(48) from Benjamin Chaffin, Dec 18 2009
a(49)-a(50) from Benjamin Chaffin, Dec 26 2009
a(51)-a(52) from Benjamin Chaffin, Jan 10 2010
a(53)-a(80) from Benjamin Chaffin, Jan 10 2012

A217208 a(n) = (conjectured) length of longest tail that can be generated by a starting string of 2's and 3's of length n before a 1 is reached, using the rule described in the Comments lines.

Original entry on oeis.org

0, 2, 2, 4, 4, 8, 8, 58, 59, 60, 112, 112, 112, 118, 118, 118, 118, 118, 119, 119, 119, 120, 120, 120, 120, 120, 120, 120, 120, 120, 120, 120, 120, 120, 120, 120, 120, 120, 120, 120, 120, 120, 120, 120, 120, 120, 120, 131, 131, 131, 131, 131, 131, 131, 131, 131, 131, 131, 131, 131, 131, 131, 131, 131, 131, 131, 131, 132, 132, 132, 132, 132, 132, 132, 132, 133, 173, 173, 173, 173

Offset: 1

N. J. A. Sloane, Sep 29 2012; revised Oct 02 2012

Start with an initial string S of n numbers s(1), ..., s(n), all = 2 or 3. The rule for extending the string is this:
To get s(i+1), write the current string s(1)s(2)...s(i) as XY^k for words X and Y (where Y has positive length) and k is maximized, i.e. k = the maximal number of repeating blocks at the end of the sequence so far (k is the "curling number" of the string). Then set s(i+1) = k.
The "tail length" t(S) of S is defined as follows: start with S and repeatedly append the curling number (recomputing it at each step) until a 1 is reached; t(S) is the number of terms that are appended to S before a 1 is reached. If a 1 is never reached, set t(S)=oo .
The "Curling Number Conjecture" is that if one starts with any finite string and repeatedly extends it by appending the curling number k, then eventually one must reach a 1. This has not yet been proved.
The values shown for n >= 49 are only conjectures, because certain assumptions used to cut down the search have not yet been rigorously justified. However, we believe that ALL terms shown are correct.

			a(3) = 2, using the starting string 3,2,2, which extends to 3,2,2,2,3, of length 5.
a(4) = 4, using the starting string 2,3,2,3, which extends to 2,3,2,3,2,2,2,3 of length 8.
a(8) = 58: start = 23222323, end = 232223232223222322322232223232223222322322232223232223222322322332.
a(22) = 120: start = 2322322323222323223223: see A116909 for trajectory.

F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane and Allan Wilks, A Slow-Growing Sequence Defined by an Unusual Recurrence, J. Integer Sequences, Vol. 10 (2007), #07.1.2. [pdf, ps]
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3. arXiv:1212.6102
Benjamin Chaffin and N. J. A. Sloane, The Curling Number Conjecture, preprint.
Index entries for sequences related to curling numbers

a(n) = length of n-th row of A217209.
a(n) = A094004(n) - n.
Cf. A091787, A090822, A093369, A094005, A116909, A160766, A216730, A216813.

cp's OEIS Frontend

A090822 Gijswijt's sequence: a(1) = 1; for n>1, a(n) = largest integer k such that the word a(1)a(2)...a(n-1) is of the form xy^k for words x and y (where y has positive length), i.e., the maximal number of repeating blocks at the end of the sequence so far.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

A216730 List of "rotten" strings in {2,3}* (in the curling number sense).

Views

Author

Keywords

Comments

Links

Crossrefs

A094004 a(n) = (conjectured) length of longest string that can be generated by a starting string of 2's and 3's of length n, using the rule described in the Comments lines.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A217208 a(n) = (conjectured) length of longest tail that can be generated by a starting string of 2's and 3's of length n before a 1 is reached, using the rule described in the Comments lines.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs