A091975 -id:A091975 - 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

A091976 a(1)=1; for n>1, a(n) = largest integer k such that the word a(1)a(2)a(3)...a(n-1) is of the form x(y_1)(y_2)...(y_k) where each y_i is of positive length and any y_i and y_j are related by y_i=P(y_j) for some permutation P.

Original entry on oeis.org

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

Offset: 1

J. Taylor (integersfan(AT)yahoo.com), Mar 15 2004

nonn

In the definition (and example), multiplication denotes concatenation of words. This is similar to Gijswijt's sequence A090822 except that we accept blocks as being equivalent if they are merely permutations of each other, not necessarily via the identity permutation (as is the case in A090822).

Question: Is it true that for all m, a(1)a(2)a(3)...a(m) above shows up somewhere in Gijswijt's sequence (A090822)?

			Up to "1 1 2 1 1 2 2 2 3 1 1 2 1 1 2 2 2 3 2", this agrees with A090822. But the next term of A090822 is 1, while the next term here is 2: because [1 1 2 1 1] [2 2 2 3 1 1 2] [1 1 2 2 2 3 2] = x y P(y) where P is a permutation.

Samuel Harkness, Table of n, a(n) for n = 1..10000
Samuel Harkness, MATLAB program
Neal Gersh Tolunsky, Ordinal transform of the first 20000 terms
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].
Index entries for sequences related to Gijswijt's sequence

The entry for A090822 gives further information.

Cf. A091975.

MATLAB
```
See Links section.
```

def k(s):
    maxk = 1
    for m in range(1, len(s)+1):
        i, y, kk = 1, sorted(s[-m:]), len(s)//m
        if kk <= maxk: return maxk
        while sorted(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(105)) # Michael S. Branicky, Nov 05 2023

A092331 For S a string of numbers, let F(S) = the sum of those numbers. Let a(1)=1. For n>1, a(n) is the largest k such that the string a(1)a(2)...a(n-1) can be written in the form [x][y_1][y_2]...[y_k], where each y_i is positive (but not necessarily all the same) length and F(y_i)=F(y_j) for all i,j<=k.

Original entry on oeis.org

1, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 2, 4, 3, 3, 3, 4, 1, 3, 2, 2, 3, 3, 3, 3, 4, 2, 3, 3, 4, 2, 5, 2, 2, 4, 3, 2, 5, 2, 3, 3, 2, 4, 2, 3, 3, 2, 3, 3, 3, 3, 4, 2, 3, 3, 4, 4, 4, 3, 3, 4, 4, 4, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 3, 4, 3, 2, 3, 3, 2, 3, 4, 4, 3, 3, 5, 3, 3, 3, 4, 5, 3, 3, 3, 4, 3, 3, 5, 3, 6, 3, 3, 4, 6, 2

Offset: 1

J. Taylor (integersfan(AT)yahoo.com), Mar 17 2004

nonn

Here multiplication denotes concatenation of strings. This is Gijswijt's sequence, A090822, except that the 'y' blocks count as being equivalent whenever the sum of their digits is equal.

			From _Rémy Sigrist_, Feb 08 2023: (Start)
The first terms, alongside an appropriate partition of prior terms, are:
  n   a(n)  Prior terms
  --  ----  -----------------
   1     1  N/A
   2     1  1
   3     2  1|1
   4     2  1 1|2
   5     3  1 1|2|2
   6     1  1 1 2 2 3
   7     2  1 1|2 2|3 1
   8     2  1 1 2 2|3 1 2
   9     3  1 1|2 2|3 1|2 2
  10     2  1|1 2 2 3|1 2 2 3
(End)

Rémy Sigrist, Table of n, a(n) for n = 1..10000
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].
Rémy Sigrist, C program
Index entries for sequences related to Gijswijt's sequence

Cf. A090822, A091975, A091976.

C
```
See Links section.
```

A092335 Let a(1)=1. For n>1, a(n) is the greatest k such that a(1)a(2)...a(n-1) can be written in the form [x][y_1][y_2]...[y_k] where each y_i is of positive and equal length and for any i,j, y_i and y_j agree at every other term starting from the left (see example).

Original entry on oeis.org

1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 1, 3, 2, 1, 2, 1, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2, 2, 3, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2, 2, 3, 2, 2, 3, 2, 2, 2, 3, 3, 3, 3, 4, 2, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 1, 3, 2, 1, 2, 1, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2, 2, 3, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2, 2, 3, 2, 2, 3, 2, 2, 2, 3, 3, 3, 3, 4, 2, 2

Offset: 1

J. Taylor (integersfan(AT)yahoo.com), Mar 17 2004

nonn

Multiplication here denotes concatenation of strings. This is Gijswijt's sequence, A090822, except when checking if 'y' blocks are 'equal', we only compare every other term and ignore the others

			For example, [1 2 3 4 5] and [1 0 3 100 5] count as being equal because both are of the form [1 ? 3 ? 5]

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].
Index entries for sequences related to Gijswijt's sequence

Cf. A090822, A091975, A091976.

A092332 For S a string of numbers, let F(S) = the product of those numbers. Let a(1)=1. For n>1, a(n) is the greatest k such that a(1)a(2)...a(n-1) can be written in the form [x][y_1][y_2]...[y_k] where each y_i is of positive (but not necessarily all the same) length and F(y_i)=F(y_j) for all i,j<=k.

Original entry on oeis.org

1, 1, 2, 1, 1, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2, 4, 2, 2, 3, 2, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3, 2, 4, 2, 2, 2, 3, 2, 3, 3, 2, 3, 2, 4, 4, 3, 2, 2, 2, 3, 3, 2, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 3, 4, 4, 2, 3, 2, 2, 2, 3, 3, 3, 3, 4, 2, 2, 3, 4, 3, 3, 2, 2, 4, 3, 5, 1, 1, 2, 1, 1, 2, 2, 3, 1, 1, 2, 1

Offset: 1

J. Taylor (integersfan(AT)yahoo.com), Mar 17 2004

nonn

Here [x][y] denotes concatenation of strings. This is Gijswijt's sequence, A090822, except that the 'y' blocks count as being equivalent whenever the product of their digits is the same.

For actually calculating this sequence, compare prime compositions of the products, not the products themselves, as those grow far too fast.

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].
Index entries for sequences related to Gijswijt's sequence

Cf. A090822, A091975, A091976.

A092333 For S a string of numbers, let F(S) = the sum of those numbers. Let a(1)=1. For n>1, a(n) is the largest k such that the string a(1)a(2)...a(n-1) can be written in the form [x][y_1][y_2]...[y_k] where each y_i is of positive (but not necessarily equal) length and for any i=F(y_(i+1)).

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 7, 8, 7, 8, 6, 7, 7, 8, 8, 9, 8, 9, 8, 9, 9, 10, 9, 10, 8, 9, 9, 10, 10, 11, 9, 10, 10, 11, 11, 12, 10, 11, 11, 12, 12, 13, 11, 12, 12, 13, 13, 14, 10, 11, 11, 12, 12, 13, 11, 12, 12, 13, 13, 14, 13, 14, 13, 14

Offset: 1

J. Taylor (integersfan(AT)yahoo.com), Mar 17 2004

nonn

Here multiplication denotes concatenation of strings. This is Gijswijt's sequence, A090822, except we accept 'y' blocks as upholding Gijswijt's axiom whenever they satisfy the inequality above.

Question: Is there any integer U such that a(M)<=a(M+1) for all M>U?

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].
Index entries for sequences related to Gijswijt's sequence

Cf. A090822, A091975, A091976.

A092334 For S a finite string of numbers, let M(S) denote the maximal number among them. Let a(1)=1. For n>1, a(n) is the greatest k such that the string a(1)a(2)...a(n-1) can be written in the form [x][y_1][y_2]...[y_k] where each y_i is of positive (but not necessarily equal) length and M(y_i)=M(y_j) for all i,j.

Original entry on oeis.org

1, 1, 2, 1, 1, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 3, 2, 2, 2, 3, 3, 4, 1, 1, 2, 1, 1, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 3, 2, 2, 2, 3, 3, 4, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 3, 4, 3, 3, 3, 3, 4, 4, 5, 1, 1, 2, 1, 1, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 3, 2, 2, 2, 3, 3, 4, 1, 1, 2, 1, 1, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 3, 2, 2

Offset: 1

J. Taylor (integersfan(AT)yahoo.com), Mar 17 2004

nonn

Here multiplication denotes concatenation of strings. This is Gijswijt's sequence, A090822, except we count 'y' blocks as being equivalent as long as their maximal elements are identical.

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].
Index entries for sequences related to Gijswijt's sequence

Cf. A090822, A091975, A091976.

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

A091976 a(1)=1; for n>1, a(n) = largest integer k such that the word a(1)a(2)a(3)...a(n-1) is of the form x(y_1)(y_2)...(y_k) where each y_i is of positive length and any y_i and y_j are related by y_i=P(y_j) for some permutation P.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

Python

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

A092335 Let a(1)=1. For n>1, a(n) is the greatest k such that a(1)a(2)...a(n-1) can be written in the form [x][y_1][y_2]...[y_k] where each y_i is of positive and equal length and for any i,j, y_i and y_j agree at every other term starting from the left (see example).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Views

Author

Keywords

Comments

Links

Crossrefs

A092333 For S a string of numbers, let F(S) = the sum of those numbers. Let a(1)=1. For n>1, a(n) is the largest k such that the string a(1)a(2)...a(n-1) can be written in the form [x][y_1][y_2]...[y_k] where each y_i is of positive (but not necessarily equal) length and for any i=F(y_(i+1)).

Views

Author

Keywords

Comments

Links

Crossrefs

Views

Author

Keywords

Comments

Links

Crossrefs