A216959 -id:A216959 - cp's OEIS frontend

A122536 Number of binary sequences of length n with no initial repeats (or, with no final repeats).

2, 2, 4, 6, 12, 20, 40, 74, 148, 286, 572, 1124, 2248, 4460, 8920, 17768, 35536, 70930, 141860, 283440, 566880, 1133200, 2266400, 4531686, 9063372, 18124522, 36249044, 72493652, 144987304, 289965744

Offset: 1

Sarah Nibs, Sep 18 2006

nonn

An initial repeat of a string S is a number k>=1 such that S(i)=S(i+k) for i=0..k-1. In other words, the first k symbols are the same as the next k symbols, e.g., ABCDABCDZQQ has an initial repeat of size 4.

Equivalently, this is the number of binary sequences of length n with curling number 1. See A216955. - N. J. A. Sloane, Sep 26 2012

			a(4)=6: 0100, 0110, 0111, 1000, 1001 and 1011. (But not 00**, 11**, 0101, 1010.)

Allan Wilks, Table of n, a(n) for n = 1..200 (The first 71 terms were computed by _N. J. A. Sloane_.)
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, arXiv:1212.6102 [math.CO], 2012-2013.
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3.
Daniel Gabric, Jeffrey Shallit, Borders, Palindrome Prefixes, and Square Prefixes, arXiv:1906.03689 [cs.DM], 2019.
Sarah Nibs, Java program for this sequence and A003000
Index entries for sequences related to curling numbers

Twice A093371. Leading column of each of the triangles A216955, A217209, A218869, A218870. Different from, but easily confused with, A003000 and A216957. - N. J. A. Sloane, Sep 26 2012

See A121880 for difference from 2^n.

Conjecture:  a_n ~ C * 2^n where C is 0.27004339525895354325... [Chaffin, Linderman, Sloane, Wilks, 2012]
a(2n+1)=2*a(2n) = A211965(n+1), a(2n)=2*a(2n-1)-A216958(n) = A211966(n). - N. J. A. Sloane, Sep 28 2012
a(1) = 2; a(2n) = 2*[a(2n-1) - A216959(n)], n >= 1. - Daniel Forgues, Feb 25 2015

a(31)-a(71) computed from recurrence and the first 30 terms of A216958 by N. J. A. Sloane, Sep 28 2012, Oct 25 2012

A216958 Number of binary vectors v of length n with curling number 1 such that the concatenation v v with first term omitted also has curling number 1.

Original entry on oeis.org

2, 2, 4, 6, 10, 20, 36, 72, 142, 280, 560, 1114, 2222, 4436, 8864, 17718, 35420, 70824, 141624, 283210, 566394, 1132728, 2265390, 4530726, 9061318, 18122518, 36244908, 72489566, 144978870, 289957490, 579914470, 1159828430, 2319656332, 4639311620, 9278622168

Offset: 1

N. J. A. Sloane, Sep 27 2012

nonn

See A216730 for definitions.
I would very much like to have a formula or recurrence for this sequence.
Alternatively, the number of squares of length 2n over a binary alphabet having no proper prefix that is a square.  Here by a square I mean a word of the form xx, where x is any word. - Jeffrey Shallit, Nov 29 2013

			Taking the alphabet to be {2,3}, v = 32232 has curling number 1, but 2232.32232 has curling number 2, so is not counted here.

N. J. A. Sloane, Table of n, a(n) for n = 1..100 [Based on _Allan Wilks_'s b-file for A122536]
Daniel Gabric, Jeffrey Shallit, Borders, Palindrome Prefixes, and Square Prefixes, arXiv:1906.03689 [cs.DM], 2019.
Daniel Gabric, Jeffrey Shallit, Borders, palindrome prefixes, and square prefixes, Info. Proc. Letters 165 (2021), 106027.
Index entries for sequences related to curling numbers

Cf. A216730, A122536, A216959, A216960, A216961.

First column of A218875.

a(n) = 2*A122536(2n-1)-A122536(2n). - R. J. Mathar, Oct 31 2024

a(31)-a(35) from N. J. A. Sloane, Oct 25 2012

cp's OEIS Frontend

A122536 Number of binary sequences of length n with no initial repeats (or, with no final repeats).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions