cp's OEIS Frontend

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.

%I A091976 #23 Dec 09 2023 20:47:14
%S A091976 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,
%T A091976 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,
%U A091976 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
%N 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.
%C A091976 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).
%C A091976 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)?
%H A091976 Samuel Harkness, <a href="/A091976/b091976.txt">Table of n, a(n) for n = 1..10000</a>
%H A091976 Samuel Harkness, <a href="/A091976/a091976.m.txt">MATLAB program</a>
%H A091976 Neal Gersh Tolunsky, <a href="/A091976/a091976.png">Ordinal transform of the first 20000 terms</a>
%H A091976 F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane and Allan Wilks, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">A Slow-Growing Sequence Defined by an Unusual Recurrence</a>, J. Integer Sequences, Vol. 10 (2007), #07.1.2.
%H A091976 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 [<a href="http://neilsloane.com/doc/gijs.pdf">pdf</a>, <a href="http://neilsloane.com/doc/gijs.ps">ps</a>].
%H A091976 <a href="/index/Ge#Gijswijt">Index entries for sequences related to Gijswijt's sequence</a>
%e A091976 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.
%o A091976 (MATLAB) See Links section.
%o A091976 (Python)
%o A091976 def k(s):
%o A091976     maxk = 1
%o A091976     for m in range(1, len(s)+1):
%o A091976         i, y, kk = 1, sorted(s[-m:]), len(s)//m
%o A091976         if kk <= maxk: return maxk
%o A091976         while sorted(s[-(i+1)*m:-i*m]) == y: i += 1
%o A091976         maxk = max(maxk, i)
%o A091976 def aupton(terms):
%o A091976     alst = [1]
%o A091976     for n in range(2, terms+1):
%o A091976         alst.append(k(alst))
%o A091976     return alst
%o A091976 print(aupton(105)) # _Michael S. Branicky_, Nov 05 2023
%Y A091976 The entry for A090822 gives further information.
%Y A091976 Cf. A091975.
%K A091976 nonn
%O A091976 1,3
%A A091976 J. Taylor (integersfan(AT)yahoo.com), Mar 15 2004