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

1, 3, 7, 15, 31, 63, 127, 255, 511, 1024, 2050, 4102, 8206, 16414, 32830, 65662, 131326, 262654, 525310, 1050622, 2101246, 4202494, 8404990, 16809982, 33619966, 67239934, 134479870, 268959742, 537919486, 1075838974, 2151677950, 4303355902, 8606711806

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

Table of n, a(n) for n=1..33.

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

Cf. A082215.

Sequence in context: A255047 A000225 A168604 * A117060 A178460 A351755

Adjacent sequences: A123118 A123119 A123120 * A123122 A123123 A123124

Keyword

nonn,base

Author

Dmitry Kamenetsky, Sep 29 2006

Extensions

More terms from Vincenzo Librandi, Sep 26 2015

Status

approved