OFFSET
1,2
COMMENTS
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
REFERENCES
M. Lothaire, Algebraic combinatorics on words, Cambridge University Press, Cambridge, 2002.
LINKS
Jiří Balun, Tomáš Masopust, and Petr Osička, Speed Me up if You Can: Conditional Lower Bounds on Opacity Verification, arXiv:2304.09920 [cs.FL], 2023.
J. Cooper and D. Rorabaugh, Bounds on Zimin Word Avoidance, arXiv:1409.3080 [math.CO], 2014; Congressus Numerantium, 222 (2014), 87-95.
L. J. Cummings and M. Mays, A one-sided Zimin construction, Electron. J. Combin. 8 (2001), #R27.
A. I. Zimin, Blocking sets of terms, Math. USSR Sbornik, 47 (1984), No. 2, 353-364.
FORMULA
a(n) = 2*a(n-1) + ceiling(log_10(n+1)).
G.f.: sum(j>=1, x^(10^j))/(1-3*x+2*x^2). - Robert Israel, Sep 18 2014
EXAMPLE
The Zimin words are defined by Z_1 = 1, Z_n = Z_{n-1}nZ_{n-1}.
So the Zimin words are 1, 121, 1213121, 121312141213121 ...
MAPLE
A[1]:= 1:
for i from 2 to 100 do A[i]:= 2*A[i-1]+ilog10(i+1) od:
seq(A[i], i=1..100); # Robert Israel, Sep 18 2014
PROG
(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
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Dmitry Kamenetsky, Sep 29 2006
EXTENSIONS
More terms from Vincenzo Librandi, Sep 26 2015
STATUS
approved