A123121 - OEIS

%I #30 Apr 28 2023 17:03:57

%S 1,3,7,15,31,63,127,255,511,1024,2050,4102,8206,16414,32830,65662,

%T 131326,262654,525310,1050622,2101246,4202494,8404990,16809982,

%U 33619966,67239934,134479870,268959742,537919486,1075838974,2151677950,4303355902,8606711806

%N Length of the n-th Zimin word (A082215(n)).

%C The length of the n-th Zimin word on a countably infinite alphabet {x_1, x_2, x_3, ...} with Z_{n+1} = Z_n x_{n+1} Z_n (as opposed to the use of base 10 in A082215) is 2^n-1. - _Danny Rorabaugh_, Mar 12 2015

%D M. Lothaire, Algebraic combinatorics on words, Cambridge University Press, Cambridge, 2002.

%H Jiří Balun, Tomáš Masopust, and Petr Osička, <a href="https://arxiv.org/abs/2304.09920">Speed Me up if You Can: Conditional Lower Bounds on Opacity Verification</a>, arXiv:2304.09920 [cs.FL], 2023.

%H J. Cooper and D. Rorabaugh, <a href="http://arxiv.org/abs/1409.3080">Bounds on Zimin Word Avoidance</a>, arXiv:1409.3080 [math.CO], 2014; Congressus Numerantium, 222 (2014), 87-95.

%H L. J. Cummings and M. Mays, <a href="https://doi.org/10.37236/1571">A one-sided Zimin construction</a>, Electron. J. Combin. 8 (2001), #R27.

%H A. I. Zimin, <a href="http://mi.mathnet.ru/eng/msb2889">Blocking sets of terms</a>, Math. USSR Sbornik, 47 (1984), No. 2, 353-364.

%F a(n) = 2*a(n-1) + ceiling(log_10(n+1)).

%F G.f.: sum(j>=1, x^(10^j))/(1-3*x+2*x^2). - _Robert Israel_, Sep 18 2014

%e The Zimin words are defined by Z_1 = 1, Z_n = Z_{n-1}nZ_{n-1}.

%e So the Zimin words are 1, 121, 1213121, 121312141213121 ...

%p A[1]:= 1:

%p for i from 2 to 100 do A[i]:= 2*A[i-1]+ilog10(i+1) od:

%p seq(A[i],i=1..100); # _Robert Israel_, Sep 18 2014

%o (Magma) [n le 1 select 1 else 2*Self(n-1) + Ceiling(Log(n+1)/Log(10)): n in [1..40]]; // _Vincenzo Librandi_, Sep 26 2015

%Y Cf. A082215.

%K nonn,base

%O 1,2

%A _Dmitry Kamenetsky_, Sep 29 2006

%E More terms from _Vincenzo Librandi_, Sep 26 2015