A122536 -id:A122536 - cp's OEIS frontend

A121880 a(n) = 2^n - A122536(n).

0, 2, 4, 10, 20, 44, 88, 182, 364, 738, 1476, 2972, 5944, 11924, 23848, 47768, 95536, 191214, 382428, 765136, 1530272, 3061104, 6122208, 12245530, 24491060, 48984342, 97968684, 195941804, 391883608, 783776080, 1567552160, 3135122038, 6270244076

Offset: 1

N. J. A. Sloane, Sep 21 2006

nonn

Number of binary sequences of length n with curling number > 1. See A122536 for much more information.

Robert Price, Table of n, a(n) for n = 1..200
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.
Index entries for sequences related to curling numbers

Cf. A122536. Similar to but different from A094536.

A216960 a(n) = A122536(n) - A216958(n).

Original entry on oeis.org

0, 0, 0, 0, 2, 0, 4, 2, 6, 6, 12, 10, 26, 24, 56, 50, 116, 106, 236, 230, 486, 472, 1010, 960, 2054, 2004, 4136, 4086, 8434, 8254, 17018, 16828, 34184, 33992, 69056, 68314, 138754, 138020, 278174, 277452, 559152, 556246, 1121116, 1118170, 2245076, 2242058, 4501566, 4489798

Offset: 1

N. J. A. Sloane, Sep 27 2012

nonn

Cf. A122536, A216958, A216961.

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

More terms from Hakan Icoz, Dec 28 2021

A211975 A122536(2n)/2.

Original entry on oeis.org

1, 3, 10, 37, 143, 562, 2230, 8884, 35465, 141720, 566600, 2265843, 9062261, 36246826, 144982872, 579922629, 2319672806, 9278655812, 37114552436, 148458068139, 593831989359, 2375327391072, 9501308431593, 38005231461009, 152020921313377

Offset: 1

Omar E. Pol, Nov 30 2012

nonn

B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, arXiv:1212.6102, Dec 25 2012.
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.
Index entries for sequences related to curling numbers

Bisection of A093371.

Cf. A093370, A121880, A216955.

A218874 (A122536(n)-A003000(n))/2.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 4, 8, 18, 36, 73, 146, 295, 590, 1182, 2364, 4732, 9464, 18929, 37858, 75721, 151442, 302878, 605756, 1211504, 2423008, 4845968, 9691936, 19383784, 38767568, 77534894, 155069788, 310139104, 620278208, 1240555349

Offset: 1

N. J. A. Sloane, Nov 09 2012

nonn

If a formula or recurrence were known it would explain the mysterious sequence A122536.

200 terms are known from the b-files for A122536 and A003000.

B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, arXiv:1212.6102, Dec 25 2012.
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.
Index entries for sequences related to curling numbers

Cf. A122536, A003000.

A003000 Number of bifix-free (or primary, or unbordered) words of length n over a two-letter alphabet.

Original entry on oeis.org

1, 2, 2, 4, 6, 12, 20, 40, 74, 148, 284, 568, 1116, 2232, 4424, 8848, 17622, 35244, 70340, 140680, 281076, 562152, 1123736, 2247472, 4493828, 8987656, 17973080, 35946160, 71887896, 143775792, 287542736, 575085472, 1150153322, 2300306644, 4600578044, 9201156088

Offset: 0

N. J. A. Sloane

This is the number of binary words w of length n such that there is no nonempty word x, different from w, which is both a prefix and a suffix of w. - N. J. A. Sloane, Nov 09 2012
Many authors use the term "unbordered" for "bifix-free". The Lothaire (1997) reference refers to bifix-free words as primary words (Chapter 8). - David Callan, Sep 25 2006
Also the number of binary "prime palstars" of length 2n (Rampersad, Shallit, & Wang 2011). - Jeffrey Shallit, Aug 14 2014

			Bi-fix free words of lengths 1 through 4:
0, 1
10, 01
100, 110, 011, 001
1000, 1100, 1110, 0111, 0011, 0001.

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 28.
M. Lothaire, Combinatorics on Words, Cambridge University Press, NY, 1997, see p. 153.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..3323 (first 501 terms from T. D. Noe)
E. Barcucci, A. Bernini, S. Bilotta and R. Pinzani, Cross-bifix-free sets in two dimensions, arXiv preprint arXiv:1502.05275 [cs.DM], 2015.
S. Bilotta, E. Pergola and R. Pinzani, A new approach to cross-bifix-free sets, arXiv preprint arXiv:1112.3168 [cs.FL], 2011.
G. Blom, Problem 94-20: Overlapping binary sequences, SIAM Review 37 (1995), 619-620.
Joshua Cooper and Danny Rorabaugh, Asymptotic Density of Zimin Words, arXiv preprint arXiv:1510.03917 [math.CO], 2015-2016.
Daniel Gabric and Jeffrey Shallit, Borders, Palindrome Prefixes, and Square Prefixes, arXiv:1906.03689 [cs.DM], 2019.
O. Georgiou, C. P. Dettmann and E. G. Altmann, Faster than expected escape for a class of fully chaotic maps, arXiv preprint arXiv:1207.7000 [nlin.CD], 2012. - From _N. J. A. Sloane_, Dec 23 2012
D. J. Greaves and S. J. Montgomery-Smith, Unforgeable Marker Sequences.
L. J. Guibas and A. M. Odlyzko, Periods in Strings, Journal of Combinatorial Theory A 30 (1981) 19-42. Their L_n(0) is A003000(n).
H. Harborth, Endliche 0-1-Folgen mit gleichen Teilblöcken, J. für Reine Angewandte Math. 271 (1974), 139-154, see p. 143.
T. Harju and D. Nowotka, Border correlation of binary words.
P. Tolstrup Nielsen, A note on bifix-free sequences, IEEE Trans. Info. Theory IT-19 (1973), 704-706. [pdf]
Jakob Radoszewski, Wojciech Rytter, and Tomasz Waleń, Faster Algorithms for Ranking/Unranking Bordered and Unbordered Words, Int'l Symp. String Proc. Info. Retrieval (2024), Springer, Cham, LNCS Vol. 14899, 257-271.
N. Rampersad, J. Shallit, and M.-w. Wang, Inverse star, borders, and palstars, Info. Proc. Letters 111 (2011), 420-422. - _Jeffrey Shallit_, Aug 14 2014
N. Rampersad, J. Shallit, and M.-w. Wang, Inverse star, borders, and palstars, arXiv:1008.2440 [cs.FL], 2010.
D. Rorabaugh, Toward the Combinatorial Limit Theory of Free Words, arXiv preprint arXiv:1509.04372 [math.CO], 2015.
Sarah Nibs, Java program for this sequence and A122536.

Equals 2 * A045690 for n > 0. Complement gives A094536.

Cf. A019308, A019309, A094537, A242430.

A[0]:= 1:
for n from 1 to 100 do
if n::odd then A[n]:= 2*A[n-1] else A[n]:= 2*A[n-1]-A[n/2] fi
od:
seq(A[n],n=0..100); # Robert Israel, Aug 14 2014

a[0]=1;a[n_]:=a[n]=2*a[n-1]-(1+(-1)^n)/2*a[Floor[n/2]]; Table[a[n], {n, 0, 34}]
a[0]=1; a[n_]:=a[n]=2*a[n-1]-If[EvenQ[n], a[n/2], 0] (* Ed Pegg Jr, Jan 05 2005 *)

a(2*n+1) = 2*a(2*n), a(2*n) = 2*a(2*n-1) - a(n).
a(n)/2^n converges to A242430.
a(0)=1; a(n)=2*a(n-1)-(1/2)*(1+(-1)^n)*a([n/2]). - Farideh Firoozbakht, Jun 10 2004
G.f.: g(x) satisfies (1-2*x)*g(x) = 2 - g(x^2). - Robert Israel, Jan 12 2015

New description and reference from Jeffrey Shallit, Sep 15 1996
Additional comments from Torsten.Sillke(AT)lhsystems.com, Jan 17 2001
More terms from Farideh Firoozbakht, Jun 10 2004

A216955 Triangle read by rows: T(n,k) (n>=1, 1<=k<=n) = number of binary sequences of length n and curling number k.

Original entry on oeis.org

2, 2, 2, 4, 2, 2, 6, 6, 2, 2, 12, 12, 4, 2, 2, 20, 26, 10, 4, 2, 2, 40, 52, 20, 8, 4, 2, 2, 74, 110, 38, 18, 8, 4, 2, 2, 148, 214, 82, 36, 16, 8, 4, 2, 2, 286, 438, 164, 70, 34, 16, 8, 4, 2, 2, 572, 876, 328, 140, 68, 32, 16, 8, 4, 2, 2, 1124, 1762, 660, 286, 134, 66, 32, 16, 8, 4, 2, 2, 2248, 3524, 1320, 572, 268, 132, 64, 32, 16, 8, 4, 2, 2

Offset: 1

N. J. A. Sloane, Sep 26 2012

For definition of curling number see A216730.
"Binary" sequence means two-valued. It doesn't matter if the alphabet is {0,1} or {2,3}.
It appears that reversed rows converge to the sequence formed by the even terms of A090129. - Omar E. Pol, Nov 20 2012

			Triangle begins:
2,
2, 2,
4, 2, 2,
6, 6, 2, 2,
12, 12, 4, 2, 2,
20, 26, 10, 4, 2, 2,
40, 52, 20, 8, 4, 2, 2,
74, 110, 38, 18, 8, 4, 2, 2,
148, 214, 82, 36, 16, 8, 4, 2, 2,
286, 438, 164, 70, 34, 16, 8, 4, 2, 2,
...

N. J. A. Sloane, Table of n, a(n) for n = 1..5460
Benjamin Chaffin, John P. Linderman, N. J. A. Sloane and Allan Wilks, First 104 rows of A216955
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, arXiv:1212.6102, Dec 25 2012.
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.
Index entries for sequences related to curling numbers

Leading columns are A122536 (or A093371), A217211, A217212. Cf. A216956, A217943.

Extended to 104 rows by N. J. A. Sloane, Nov 15 2012

A093371 Start with any initial string of n numbers s(1), ..., s(n), with s(1) = 2, other s(i)'s = 2 or 3 (so there are 2^(n-1) starting strings). The rule for extending the string is this as follows: To get s(n+1), write the string s(1)s(2)...s(n) as xy^k for words x and y (where y has positive length) and k is maximized, i.e., k = the maximal number of repeating blocks at the end of the sequence. Then a(n) = number of starting strings for which k = 1.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 20, 37, 74, 143, 286, 562, 1124, 2230, 4460, 8884, 17768, 35465, 70930, 141720, 283440, 566600, 1133200, 2265843, 4531686, 9062261, 18124522, 36246826, 72493652, 144982872

Offset: 1

N. J. A. Sloane, Apr 28 2004

nonn

See A122536 for many more terms. - N. J. A. Sloane, Oct 25 2012

F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane and Allan Wilks, A Slow-Growing Sequence Defined by an Unusual Recurrence, J. Integer Sequences, Vol. 10 (2007), #07.1.2.
F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane and Allan Wilks, A Slow-Growing Sequence Defined by an Unusual Recurrence [pdf, ps].
Index entries for sequences related to curling numbers

Cf. A093370, A093369, A090822, A216955, A216956.
Equals A122536/2. - N. J. A. Sloane, Sep 25 2012
Different from, but easily confused with, A007148 and A045690.

a(n) = 2^(n-1) - A093370(n).

More terms from N. J. A. Sloane, Sep 26 2012

A093370 Start with any initial string of n numbers s(1), ..., s(n), with s(1) = 2, other s(i)'s = 2 or 3 (so there are 2^(n-1) starting strings). The rule for extending the string is this as follows: To get s(n+1), write the string s(1)s(2)...s(n) as xy^k for words x and y (where y has positive length) and k is maximized, i.e., k = the maximal number of repeating blocks at the end of the sequence. Then a(n) = number of starting strings for which k > 1.

Original entry on oeis.org

0, 1, 2, 5, 10, 22, 44, 91, 182, 369, 738, 1486, 2972, 5962, 11924, 23884, 47768, 95607, 191214, 382568, 765136, 1530552, 3061104, 6122765, 12245530, 24492171, 48984342, 97970902, 195941804, 391888040

Offset: 1

N. J. A. Sloane, Apr 28 2004

nonn

			For n=2 there are 2 starting strings, 22 and 23 and only the first has k > 1.
For n=4 there are 8 starting strings, but only 5 have k > 1, namely 2222, 2233, 2322, 2323, 2333.

F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane and Allan Wilks, A Slow-Growing Sequence Defined by an Unusual Recurrence, J. Integer Sequences, Vol. 10 (2007), #07.1.2.
F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane and Allan Wilks, A Slow-Growing Sequence Defined by an Unusual Recurrence [pdf, ps].
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, arXiv:1212.6102 [math.CO], Dec 25 2012.
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.
Index entries for sequences related to Gijswijt's sequence
Index entries for sequences related to curling numbers

Cf. A090822, A093369, A093371, A121880, A122536.

Equals A121880(n)/2, or 2^(n-1) - A122536(n)/2.

a(n)/2^(n-1) seems to converge to a number around 0.73.

More terms from Sarah Nibs, via A122536, Sep 18 2006

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

A211027 Triangle of binary numbers >= 1 with no initial repeats.

Original entry on oeis.org

1, 10, 100, 101, 1000, 1001, 1011, 10000, 10001, 10010, 10011, 10110, 10111, 100000, 100001, 100010, 100011, 100101, 100110, 100111, 101100, 101110, 101111, 1000000, 1000001, 1000010, 1000011, 1000100, 1000101, 1000110, 1000111, 1001010, 1001011, 1001100, 1001101, 1001110, 1001111, 1011000, 1011001, 1011100, 1011101, 1011110, 1011111

Offset: 1

Omar E. Pol, Nov 30 2012

Triangle read by rows in which row n lists the binary numbers with n digits and with no initial repeats.

Also triangle read by rows in which row n lists the binary words of length n with no initial repeats and with initial digit 1. See also A211029.

			Triangle begins:
1;
10;
100, 101;
1000, 1001, 1011;
10000, 10001, 10010, 10011, 10110, 10111;
100000, 100001, 100010, 100011, 100101, 100110, 100111, 101100, 101110, 101111;
1000000, 1000001, 1000010, 1000011, 1000100, 1000101, 1000110, 1000111, 1001010, 1001011, 1001100, 1001101, 1001110, 1001111, 1011000, 1011001, 1011100, 1011101, 1011110, 1011111;

Alois P. Heinz, Rows n = 1..15, flattened
Index entries for sequences related to curling numbers

Column 1 is A011557. Row n has length A093371(n).

Cf. A122536, A211029, A211968, A211969, A216955.

s:= proc(n) s(n):= `if`(n=1, [[1]], map(x->
      [[x[], 0], [x[], 1]][], s(n-1))) end:
T:= proc(n) map(x-> parse(cat(x[])), select(proc(l) local i;
      for i to iquo(nops(l), 2) do if l[1..i]=l[i+1..2*i]
      then return false fi od; true end, s(n)))[] end:
seq(T(n), n=1..7);  # Alois P. Heinz, Dec 02 2012

T[n_] := If[n == 1, {1}, FromDigits /@ Select[Range[2^(n-1), 2^n-2] // IntegerDigits[#, 2]&, FindTransientRepeat[Reverse[#], 2][[2]] == {}&]];
Array[T, 7] // Flatten (* Jean-François Alcover, Feb 27 2021 *)

cp's OEIS Frontend

A121880 a(n) = 2^n - A122536(n).

Views

Author

Keywords

Comments

Links

Crossrefs

A216960 a(n) = A122536(n) - A216958(n).

Views

Author

Keywords

Links

Crossrefs

Extensions

A211975 A122536(2n)/2.

Views

Author

Keywords

Links

Crossrefs

A218874 (A122536(n)-A003000(n))/2.

Views

Author

Keywords

Comments

Links

Crossrefs

A003000 Number of bifix-free (or primary, or unbordered) words of length n over a two-letter alphabet.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A216955 Triangle read by rows: T(n,k) (n>=1, 1<=k<=n) = number of binary sequences of length n and curling number k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A211027 Triangle of binary numbers >= 1 with no initial repeats.

Views

Author