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.

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

Comments

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)?

Links

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

Example

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.

Prog

(MATLAB) See Links section.
(Python)
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

Crossrefs

The entry for A090822 gives further information.

Cf. A091975.

Sequence in context: A156755 A090822 A091975 * A267825 A151902 A094839

Adjacent sequences: A091973 A091974 A091975 * A091977 A091978 A091979

Keyword

nonn

Author

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

Status

approved