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

Author

Dmitry Kamenetsky, Sep 29 2006

Keywords

• nonn
• base

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

Examples

			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 ...
		

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.

Crossrefs

Cf. A082215.

Programs

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

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

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

Extensions

More terms from Vincenzo Librandi, Sep 26 2015