A135017 -id:A135017 - cp's OEIS frontend

A135473 a(n) = number of strings of length n that can be obtained by starting with abc and repeatedly doubling any substring in place.

0, 0, 1, 3, 8, 21, 54, 138, 355, 924, 2432, 6461, 17301, 46657, 126656, 345972, 950611, 2626253, 7292268, 20342805, 56993909, 160317859, 452642235, 1282466920, 3645564511, 10395117584, 29727982740, 85251828792, 245120276345, 706529708510, 2041260301955, 5910531770835, 17149854645474, 49859456251401, 145223624492108, 423722038708874, 1238318400527185

Offset: 1

Max Alekseyev, Jan 07 2008

nonn

The problem can be restated as follows: look at the language L over {1,2,3}* which contains 123 and is closed under duplication. What is the growth function of L (or its subword complexity function)?
It is known that the language L is not regular [Wang]
Several generalizations suggest themselves: What if we start with k different letters (here k=3)? What if we start with k different letters and fix the number of duplications d? See A137739, A137740, A137741, A137742, A137743, A137744, A137745, A137746, A137747, A137748.

			n=3: abc
n=4: aabc, abbc, abcc
n=5: aaabc, abbbc, abccc, aabbc, aabcc, abbcc, ababc, abcbc

D. P. Bovet and S. Varricchio, On the regularity of languages on a binary alphabet generated by copying systems, Information Processing Letters, 44 (1992), 119-123.
Juergen Dassow, Victor Mitrana and Gheorghe Paun: On the Regularity of Duplication Closure. Bulletin of the EATCS 69 (1999), 133-136.
Ming-wei Wang, On the Irregularity of the Duplication Closure, Bulletin of the EATCS, Vol. 70, 2000, 162-163.

Martin Fuller, Table of n, a(n) for n = 1..44
Index entries for doubling substrings

Cf. A135017, A135156, A135157, A135475, A135479, A130838.

Cf. also A137739, A137740, A137741, A137742, A137743, A137744, A137745, A137746, A137747, A137748.

Binomial transform of A135017. - Martin Fuller, Jun 06 2025

Empirically, grows like 3^n.

a(19) - a(33) from David Applegate, Feb 12 2008
Extended to 37 terms by David Applegate, Feb 16 2008
Thanks to Robert Mercas and others for comments and references - N. J. A. Sloane, Apr 26 2013

A135475 Sorted list of strings that can be obtained by starting with 123 and repeatedly doubling any substring in place.

Original entry on oeis.org

123, 1123, 1223, 1233, 11123, 11223, 11233, 12123, 12223, 12233, 12323, 12333, 111123, 111223, 111233, 112123, 112223, 112233, 112323, 112333, 121123, 121223, 121233, 122123, 122223, 122233, 122323, 122333, 123123, 123223, 123233, 123323, 123333, 1111123

Offset: 1

N. J. A. Sloane, Feb 22 2008, Mar 16 2008

The list contains A135473(n) strings of length n.

Alois P. Heinz, Table of n, a(n) for n = 1..10397 (strings with length <= 12)
Index entries for doubling substrings

Cf. A135473, A130838, A135479, A135017.

A135479 Sorted list of primitive strings that can be obtained by starting with 123 and repeatedly doubling any substring in place.

Original entry on oeis.org

123, 12123, 12323, 123123, 1212123, 1212323, 1232323, 12123123, 12312123, 12312323, 12313123, 12323123, 121212123, 121212323, 121232123, 121232323, 123123123, 123212323, 123232323, 1212123123, 1212312123, 1212312323, 1212313123, 1212323123, 1231212123

Offset: 1

N. J. A. Sloane, Feb 22 2008

The list contains A135017(n) strings of length n.

The subset of strings in A135475 that contain no repeated symbol.

Alois P. Heinz, Table of n, a(n) for n = 1..11498
Index entries for doubling substrings

A135156 a(n) = number of strings of length n that can be obtained by starting with abc and repeatedly doubling any substring of length >= 2 in place.

Original entry on oeis.org

1, 0, 2, 0, 3, 1, 4, 0, 5, 2, 6, 1, 7, 3, 8, 9, 9, 7, 10, 34, 11, 36, 12, 136, 13, 190, 14, 567, 15, 1018, 16, 2445, 17, 5474, 18, 11371, 19, 28233, 20, 57961, 21, 143391, 22, 308793, 23, 740519, 24, 1668316

Offset: 0

David Applegate and N. J. A. Sloane, Feb 15 2008

nonn

A "weakly primitive" version of A135473. Cf. A135017.

Differs from A135017 in that the strings may contain repeated letters.

Index entries for doubling substrings

cp's OEIS Frontend

A135473 a(n) = number of strings of length n that can be obtained by starting with abc and repeatedly doubling any substring in place.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A135475 Sorted list of strings that can be obtained by starting with 123 and repeatedly doubling any substring in place.

Views

Author

Keywords

Comments

Links

Crossrefs

A135479 Sorted list of primitive strings that can be obtained by starting with 123 and repeatedly doubling any substring in place.

Views

Author

Keywords

Comments

Links

A135156 a(n) = number of strings of length n that can be obtained by starting with abc and repeatedly doubling any substring of length >= 2 in place.

Views

Author

Keywords

Comments

Links