login
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

%I #23 Dec 09 2023 20:47:14

%S 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 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 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 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 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 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 Samuel Harkness, <a href="/A091976/b091976.txt">Table of n, a(n) for n = 1..10000</a>

%H Samuel Harkness, <a href="/A091976/a091976.m.txt">MATLAB program</a>

%H Neal Gersh Tolunsky, <a href="/A091976/a091976.png">Ordinal transform of the first 20000 terms</a>

%H 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 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 <a href="/index/Ge#Gijswijt">Index entries for sequences related to Gijswijt's sequence</a>

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

%o (Python)

%o def k(s):

%o maxk = 1

%o for m in range(1, len(s)+1):

%o i, y, kk = 1, sorted(s[-m:]), len(s)//m

%o if kk <= maxk: return maxk

%o while sorted(s[-(i+1)*m:-i*m]) == y: i += 1

%o maxk = max(maxk, i)

%o def aupton(terms):

%o alst = [1]

%o for n in range(2, terms+1):

%o alst.append(k(alst))

%o return alst

%o print(aupton(105)) # _Michael S. Branicky_, Nov 05 2023

%Y The entry for A090822 gives further information.

%Y Cf. A091975.

%K nonn

%O 1,3

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