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

Author

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

Keywords

• nonn

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

Examples

			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.
		

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

Crossrefs

The entry for A090822 gives further information.

Cf. A091975.

Programs

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