login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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.
8
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, MATLAB program
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].
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
KEYWORD
nonn
AUTHOR
J. Taylor (integersfan(AT)yahoo.com), Mar 15 2004
STATUS
approved